二叉树
是啥就不用多说了吧，，，
但有一个性质很重要:
记二叉树中，度为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
上面是一棵4层满二叉树
完全二叉树
满二叉树 完全二叉树 非完全二叉树.png
完全二叉树就是满二叉树按从右到左、从下到上的顺序删除若干叶子结点后形成的树
也就是说，完全二叉树的形态只有2种。当删除偶数个叶子结点时，形成上图第二棵树那样的完全二叉树；当删除奇数个叶子结点时，形成上图第三棵树那样的完全二叉树
满二叉树和完全二叉树的特性
实际上，满二叉树是特殊的完全二叉树，因此完全二叉树的特性更具有普适性。我们由一般到特殊进行研究，由完全二叉树到满二叉树这么个顺序去看看
完全二叉树几个必须记住的重要特性
完全二叉树.png
- 1.结点总数最多为2K-1，K为二叉树的层数（高度），当且仅当满二叉树时取等
- 2.第k层的结点数为2k-1（k<K）
- 3.每层最左边的结点的编号永远是2k-1，如上图完全二叉树中的A，B，D, H号节点。那么tips: 我们可以利用最后一层的排头兵快速求解树的高度
- 4.由3易得，结点数为n的完全二叉树的高度是 [ log2 n ] + 1， [ log2 n ] 指第二层到最后一层的高度，1指根结点所在的第一层
- 5.某结点的编号为i，则其左孩子编号为2*i，右孩子编号为2*i + 1
满二叉树自己的特点
- 结点总数为2K-1，K为满二叉树的层数（高度）
- 第k层的节点数为2k-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)
