树的遍历
在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，常用的有：
A、先序（根）遍历：先访问根结点，
再从左到右按照先序思想遍历各棵子树。
如上图先序遍历的结果为：125634789；
B、后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。如
上图后序遍历的结果为：562389741；
C、层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的
次序。
如上图层次遍历的结果为：123456789；
D、叶结点遍历：有时把所有的数据信息都存放在叶结点中，而其余
结点都是用来表示数据之间的某种分支或层次关系，这种情况就 用这种方法。如上图按照这个思想访问的结果为：56389；
大家可以看出，AB两种方法的定义是递归的，所以在程序实现时往往也是采用递归的思想。既通常所说的“深度优先搜索”。如用先序遍历编写的过程如下：
C方法应用也较多，实际上是我们讲的“广度优先搜索”。思想如下：若某个结点被访问，则该结点的子结点应记录，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点。为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下：
第二节 二叉树----二叉树基本概念
* 【性质1】在二叉树的第i层上最多有2i-1个结点（i>=1）。
证明：很简单，用归纳法：当i=1时，2i-1=1显然成立；现在假设第i-1层时命题成立，即第i-1层上最多有2i-2个结点。由于二叉树的每个结点的度最多为2，故在第i层上的最大结点数为第i-1层的2倍，
即
2*2的i-2次方=2的i-1次方（作者不会写LaTeX数学公式）
* 【性质2】深度为k的二叉树至多有2k–1个结点（k>=1）。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
2的0次方+2的1次方+2的2次方+2的3次方+.......2的k-1次方=2的k次方-1
* 【特别】一棵深度为k且有2k–1个结点的二叉树称为满二叉树。如下图A为深度为4的满二叉树，这种树的特点是每层上的结点数都是最大结点数。
可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右，由此引出完全二叉树的定义，深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
下图B就是一个深度为4，结点数为12的完全二叉树。它有如下特征：叶结点只可能在层次最大的两层上出现；对任一结点，若其右分支下的子孙的最大层次为m，则在其左分支下的子孙的最大层次必为m或m+1。下图C、D不是完全二叉树，请大家思考为什么？
* 【性质3】对任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数n0、1度结点n1和2度结点数n2之和：
n=no+n1+n2 ……(式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 ……(式子2)
由式子1和式子2得到：
no=n2+1
【性质4】具有n个结点的完全二叉树的深度为floor(log2n)+1
证明：假设深度为k，则根据完全二叉树的定义，前面k-1层一定是满的，所以n>2k–1-1。但n又要满足n<=2k -1。所以，2k–1–1<n<=2k -1。变换一下为2k–1<=n<2k。
以2为底取对数得到：k-1<=log2n<k。而k是整数，所以k= floor(log2n)+1。
【性质5】对于一棵n个结点的完全二叉树，对任一个结点(编号为i)，有：
①如果i=1,则结点i为根,无父结点；如果i>1,则其父结点编号为i/2。
如果2i>n，则结点i无左孩子（当然也无右孩子，为什么？即结点i为叶结点）；否则左孩子编号为2i。
②如果2i+1>n，则结点i无右孩子；否则右孩子编号为2i+1。
证明：我们只要验证一下即可。总结如图：
Xylophone
