二叉树

是啥就不用多说了吧，，，
但有一个性质很重要:

记二叉树中，度为0的结点数为n[0]，度为1的结点数为n[1]，度为2的结点数为n[2]，那么总有n[0] = n[2] + 1
设该二叉树总共有n个结点，结点等式为：n = n[0] + n[1] + n[2])
同时，该二叉树总共会有n-1条边，其中度为2的结点延伸出两条边，度为1的结点延伸出一条边，度为0的结点不延伸，边等式为：n -1 = 2*n[2] + 1*n[1] + 0*n[0]
结点等式和边等式联立可知 n[0] = n[2] + 1

满二叉树

满二叉树就是每一层都长到爆满的二叉树，如图：

4层满二叉树.png

完全二叉树

满二叉树 完全二叉树 非完全二叉树.png

完全二叉树就是满二叉树按从右到左、从下到上的顺序删除若干叶子结点后形成的树

也就是说，完全二叉树的形态只有2种。当删除偶数个叶子结点时，形成上图第二棵树那样的完全二叉树；当删除奇数个叶子结点时，形成上图第三棵树那样的完全二叉树

满二叉树和完全二叉树的特性

实际上，满二叉树是特殊的完全二叉树，因此完全二叉树的特性更具有普适性。我们由一般到特殊进行研究，由完全二叉树到满二叉树这么个顺序去看看

完全二叉树几个必须记住的重要特性

完全二叉树.png

• 1.结点总数最多为2^K-1，K为二叉树的层数（高度），当且仅当满二叉树时取等
• 2.第k层的结点数为2^k-1（k<K）
• 3.每层最左边的结点的编号永远是2^k-1，如上图完全二叉树中的A，B，D, H号节点。那么tips: 我们可以利用最后一层的排头兵快速求解树的高度
• 4.由3易得，结点数为n的完全二叉树的高度是 [ log2 n ] + 1， [ log2 n ] 指第二层到最后一层的高度，1指根结点所在的第一层
• 5.某结点的编号为i，则其左孩子编号为2*i，右孩子编号为2*i + 1

满二叉树自己的特点

• 结点总数为2^K-1，K为满二叉树的层数（高度）
• 第k层的节点数为2^k-1（k <= K）

访问二叉树的3种方式

前序遍历DLR

def preOrder(Tree node):
    if node == None:
        return
    visit(node.data)
    preOrder(node.leftchild)
    preOrder(node.rightchild)

中序遍历LDR

def inOrder(Tree node):
    if node == None:
        return 
    preOrder(node.leftchild)
    visit(node.data)
    preOrder(node.rightchild)

后序遍历LRD

def postOrder(Tree node):
    if node == None:
        return 
    preOrder(node.leftchild)
    preOrder(node.rightchild)
    visit(node.data)