第六章 树
树：n(n >= 0)个节点的有限集。
tips：
1.度：结点拥有的子树数。
2.树的度：树内各结点的度的最大值。
3.树的深度（高度）：树中结点的最大层次。
树的三种不同的表示法：
(1).双亲表示法：以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。
(2).孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
(3)孩子兄弟表示法：设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟。
二叉树：n个结点(n >= 0)的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点：
（1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
（2）左子树和右子树有顺序，且不可颠倒。
（3）要区分是左子树还是右子树。
特殊二叉树：（1）斜树 （2）满二叉树 （3）完全二叉树
二叉树的性质（重点）
1.在二叉树的第i层上至多有2^(k-1)个结点.
2.深度为k的二叉树至多有2^k - 1个结点（k >= 1）
3.对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0 = n2+1
推导所用公式：n-1 = n1+2n2，n = n0+n1+n2
4.具有n个结点的完全二叉树的深度为[log2n] + 1（[x]表示不大于x的最大整数）。
5.如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i有：
（1）如果i = 1，则该结点i是二叉树的根，无双亲；如果i > 1,则其双亲是结点[i / 2]。
（2）如果2i > n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
（3）如果2i + 1 > n,则结点i无右孩子；否则其右孩子是结点2*i + 1。
