第3章 二叉树
3.1 二叉树基础知识
二叉树（Binary Tree）也称为二分树、二元树、对分树等，它是n(n≥0)个有限元素的集合，该集合或者为空或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。
在二叉树中，一个元素也称为一个结点。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。
以下是一些常见的二叉树的基本概念：
（1）结点的度。结点所拥有的子树的个数称为该结点的度。
（2）叶子结点。度为0的结点称为叶子结点，或者称为终端结点。
（3）分支结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点。
（4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
（5）路径、路径长度。如果一棵树的一串结点n1，n2，…，nk有如下关系：结点ni是ni+1的父结点（1≤i<k），就把n1，n2，…，nk称为一条由n1～nk的路径。这条路径的长度是k-1。
（6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
（7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
（8）树的深度。树中所有结点的最大层数称为树的深度。
（9）树的度。树中各结点度的最大值称为该树的度，叶子结点的度为0。
（10）满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。
（11）完全二叉树。一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
二叉树的基本性质如下：
性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
性质2：一棵深度为k的二叉树中，最多具有2k-1个结点，最少有k个结点。
性质3：对于一棵非空的二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个，即如果叶子结点数为n0，度数为2的结点数为n2，则有n0=n2+1。
证明：用n0表示度为0（叶子结点）的结点总数，用n1表示度为1的结点总数，n2表示度为2的结点总数，n表示整个完全二叉树的结点总数。则n=n0+n1+n2，根据二叉树和树的性质，可知n=n1+2*n2+1（所有结点的度数之和+1=结点总数），根据两个等式可知n0+n1+n2=n1+2*n2+1，所以，n2=n0-1，即n0=n2+1。所以，答案为1。
性质4：具有n个结点的完全二叉树的深度为‘log2 n’+1。
证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2k-1-1<n≤2k-1或2k-1≤n<2k ，三遍同时取对数，于是有k-1≤log2 n<k ，因为k是整数，所以，k=「log2 n」+1。
性质5：对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：①如果i>1，则序号为i的结点的双亲结点的序号为i/2（其中“/”表示整除）；如果i=1，则序号为i的结点是根结点，无双亲结点。②如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。③如果2i+1≤n，则序号为i的结点的右孩子结点的序号为2i+1；如果2i+1>n，则序号为i的结点无右孩子。
此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i-1)/2，左孩子的编号为2i+1，右孩子的编号为2i+2。
例题1：一棵完全二叉树上有1001个结点，其中叶子结点的个数是多少？
分析：二叉树的公式：n=n0+n1+n2=n0+n1+(n0-1)=2*n0+n1-1。而在完全二叉树中， n1只能取0或1。若n1=1，则2*n0=1001，可推出n0为小数，不符合题意；若n1=0，则2*n0-1=1001，则n0=501。所以，答案为501。
例题2：如果根的层次为1，具有61个结点的完全二叉树的高度为多少？
分析：根据二叉树的性质，具有n个结点的完全二叉树的深度为 +1，因此，含有61个结点的完全二叉树的高度为 +1，即应该为6层。所以，答案为6。
例题3：在具有100个结点的树中，其边的数目为多少？
分析：在一棵树中，除了根结点之外，每一个结点都有一条入边，因此，总边数应该是100-1，即99条。所以，答案为99。
二叉树有顺序存储和链式存储两种存储结构，本章涉及的算法都采用的是链式存储结构，本章示例代码用到的二叉树的结构如下：
