二叉树

参考：微信公众号--小鹿动画学编程

满二叉树：叶子节点全都在最底层，除叶子节点外，每个节点都有左右两个节点。
平衡（完全）二叉树：左右子数高度差,小于等于1，叶子节点都在底下两层，最后一层叶子节点靠左排列。

二叉树存储方式有两种：
1.链式存储：每个节点都由数据域和两个指针域组成，数据域存储数据，指针域存储左右两个子节点信息.

image.png

2.数据存储：顺序存储就是用数组来存储, 根节点存储在下标 i = 1 的位置；左子节点存储在下标i * 2 = 2的位置，右子节点存储在i * 2 + 1 =3的位置

image.png

二叉树遍历方式：
共有四种遍历方式，分别为前序遍历、中序遍历、后序遍历、按层遍历。

所谓前序，中序，后序是针对根节点而言，根在前就是前序，根在在中间是中序，根在最后值后序，(Note：中序和后序都是从左子节点叶子开始从下往上遍历，而且遍历左子节点顺序不同）

前序遍历：根左右（每次遍历都严格按此顺序），先遍历根节点，后遍历左子节点，最后遍历右子节点，如果左子节点是个子树，就遍历整个子树后再遍历右子节点（这点容易理解为按层左右遍历），遍历中也是#遵循先取子树所有的左，然后再取右的原则#。
整体的前序遍历为：A->B->D->F->E->C->H。

image.png

中序遍历：左根右 （每次遍历都严格按此顺序），先遍历左子节点，后遍历根节点，最后是右子节点。

后序遍历：左右根（每次遍历都严格按此顺序），先遍历左子结点，后遍历右子节点，最后遍历根节点。

增删改查：

package tree

type TreeNode struct {
    Data interface {}
    LeftNode *TreeNode
    RightNode *TreeNode
}

type Tree struct {
    RootNode *TreeNode
}
func add(root NodeTree,a int) bool{  //增
    n := NodeTree{a,nil,nil}
    nodelist := []NodeTree{root}
    for {
        for _,v := range nodelist{
            if &v==nil{
                v=n
                return true
            }

            if v.leftnode==nil{
                v.leftnode=&n
                return true
            }

            if v.rightnode==nil{
                v.rightnode=&n
                return true
            }
            nodelist =append(nodelist,*v.leftnode)
            nodelist =append(nodelist,*v.rightnode)
        }
    }
    return false

}

func gettreehight(node *NodeTree) int{  //求二叉树高度
    if node==nil{
        return 0
    }
    return max(Maxhigh(node.leftnode),Maxhigh(node.rightnode))
}
func isBalanced(root *TreeNode) bool{
    if root == nil{
        return true
    }
    if isBalanced(root.LeftNode)==false{
        return false
    }
    if isBalanced(root.RightNode)==false{
        return false
    }
    if abs(maxDepth(root.LeftNode)-maxDepth(root.RightNode))>1{
        return false
    }
    return true

}

func abs(x int) int{
    if x<0{
        return -x
    }
    return x

}

func maxDepth(root *TreeNode) int{
    if root==nil{
        return 0
    }
    return max(maxDepth(root.LeftNode),maxDepth(root.RightNode))+1

}

func max(x,y int) int{
    if x>=y {
        return x
    }
    return y
}