书中第10章10.4小节介绍了有根树，简单介绍了二叉树和分支数目无限制的有根树的存储结构，而没有关于二叉树的遍历过程。为此对二叉树做个简单的总结，介绍一下二叉树基本概念、性质、二叉树的存储结构和遍历过程，主要包括先根遍历、中根遍历、后根遍历和层次遍历。 　　二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。 　　由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示： （1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。备注:^表示此方 （2）深度为k的二叉树至多有2^k-1个节点（k>=1)。 （3）对任何一棵二叉树T，如果其终端结点数目为n0，度为2的节点数目为n2，则n0=n2+1。 满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。 完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。 可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。 （4）具有n个节点的完全二叉树的深度为log2n + 1。 　　可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法，因为其非常灵活，方便二叉树的操作。二叉树的二叉链表存储结构如下所示： 举例说明二叉链表存储过程，如下图所示： 从图中可以看出：在还有n个结点的二叉链表中有n+1个空链域。 　　遍历二叉树是按照指定的路径方式访问书中每个结点一次，且仅访问一次。由二叉树的定义，我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行，因此可以得到如下最基本的三种遍历方法： （1）先根遍历（先序遍历）：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。采用递归形式实现代码如下： （2）中根遍历（中序遍历）：如果二叉树为空，进行空操作；否则，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。递归过程实现代码如下： （3）后根遍历（后序遍历）：如果二叉树为空，进行空操作；否则，先后根遍历左子树，然后后根遍历右子树，最后访问根结点。递归实现代码如下： 　　写一个完整的程序练习二叉树的三种遍历，采用递归形式创建二叉树，然后以递归的形式遍历二叉树，后面会接着讨论如何使用非递归形式实现这三种遍历，程序采用C语言实现，完整程序如下： 　　现在来讨论一下如何采用非递归实现这以上三种遍历。将递归形式转换为非递归形式，引入了额外的辅助结构栈。另外在讨论一次二叉树的层次遍历，可以借助队列进行实现。具体讨论如下： （1）先根遍历非递归实现 　　先根遍历要求顺序是根左右，可以借助栈s来实现。先将根root入栈，然后循环判断s是否为空，非空则将结点出栈，记为节点p，然后依次先将结点p的右子树结点入栈，然后将结点p的左子树结点入栈，循环操作直到栈中所有元素都出栈为止，出栈顺序即是先根遍历的结果。采用C++中模板库stack实现先根遍历如下： （2）中根遍历非递归实现 　　中根遍历要求顺序是左根右，借助栈s实现。先将根root入栈，接着从根root开始查找最左的子孩子结点直到为空为止，然后将空节点出栈，再将左子树节点出栈遍历，然后判断该左子树的右子树节点入栈。循环此过程，直到栈为空为止。此时需要注意的是入栈过程中空结点也入栈了，用以判断左孩子是否结束和左孩子是否有右孩子结点。采用C++中模板库stack实现先根遍历如下： 另外一种简洁的实现方法如下： （3）后根遍历递归实现 　　后根遍历要求访问顺序是左右根，采用辅助栈实现时，需要一个标记，判断结点是否访问了，因为右子树是通过跟结点的信息得到的。实现过程是先将根结点及其左子树入栈，并初始标记为0，表示没有访问，然后通过判断栈是否为空和标记的值是否为1来判断是否访问元素。 采用C++模板库stack具体实现程序如下： 　　层次遍历要求从根向下、从左向右进行访问，可以采用队列实现。先将根入队，然后队列进程出队操作访问结点p，再将结点p的左子树和右子树结点入队，循环执行此过程直到队列为空。出队顺序即是层次遍历结果。采用C++的模板库queue实现如下：  综合上面的分析过程写个完整的程序测试二叉树遍历的非递归实现，采用C++语言，借助stack和queue实现，完整程序如下所示： 121 //将左子树结点入栈 150 //将结点左子树结点入栈 157 //输出访问的结点 164

——《数据结构题集》-严蔚敏.吴伟民版

      本习题文档的存放目录：数据结构\▼配套习题解析\▼06 树和二叉树

      文档中源码的存放目录：数据结构\▼配套习题解析\▼06 树和二叉树\▼习题测试文档-06

<A, C>}，请画出这棵树，并回答下列问题：

(2)哪些是叶子节点？

(3)哪个是结点G的双亲？

(4)哪些是结点G的祖先？

(5)哪些是结点G的孩子？

(6)哪些是结点E的子孙？

(7)哪些是结点E的兄弟？哪些是结点F的兄弟？

(8)结点B和N的层次号分别是什么？

(9)树的深度是多少？

(10)以结点C为根的子树的深度是多少？

6.2?一棵度为2的树与一棵二叉树有何区别？

6.3?试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

6.4?一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：

(1)各层的结点数目是多少？

(2)编号为p的结点的父结点（若存在）的编号是多少？

(3)编号为p的结点的第i个儿子结点（若存在）的编号是多少？

(4)编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？

6.5?已知一棵深度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？

6.6?已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子结点的书目。

6.7? 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？

6.8?证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：

6.9?试分别推导含有n个结点和含n0个叶子结点的完全三叉树的深度H。

6.10?对于那些所有非叶子结点均有非空左右子树的二叉树：

(1)试问：有n个叶子结点的树中共有多少个结点？

(2)试证明：，其中n为叶子结点的个数，li表示第i个叶子结点所在的层次（设根结点所在的层次为1）。

6.11?在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节的存储，每个信息域占k个字节的存储。试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？

6.12? 对题6.3所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

6.13?假设n和m为二叉树中两结点，用“1”、“0”或“Φ”（分别表示肯定、恰恰相反或者不一定）填写下标：

    注：如果（1）离a和b最近的共同祖先p存在，且（2）a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。

6.14?找出所有满足下列条件的二叉树：

(a)它们在先序遍历和中序遍历时，得到的结点访问序列相同；

(b)它们在后序遍历和中序遍历时，得到的结点访问序列相同；

(c)它们在先序遍历和后序遍历时，得到的结点访问序列相同。

6.15?请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。

6.16?将下列二叉链表改为先序线索链表（不画出树的形态）。

6.17?阅读下列算法，若有错，则改正之。

{　　//已知q是指向中序线索二叉树上某个结点的指针。

　　//本函数返回指向*q的后继的指针。

6.18?试讨论，能否在一棵中序全线索二叉树上查找给定结点*p在后序序列中的后继。

6.19? 分别画出和下列树对应的各个二叉树：

6.20?将下列森林转换为相应的二叉树，并分别按以下说明进行线索化：

(1)先序前驱线索化；

(2)中序全线索化前驱线索和后继线索；

(3)后序后继线索化。

6.21?画出和下列二叉树相应的森林：

6.22?对于6.19题中给出的各树分别求出以下遍历序列：

6.23?画出和下列已知序列对应的树T： 树的先根次序访问序列为GFKDAIEBCHJ; 树的后根次序访问序列为DIAEKFCJHBG。

6.24?画出和下列已知序列对应的森林F： 森林的先序次序访问序列为：ABCDEFGHIJKL； 森林的中序次序访问序列为：CBEFDGAJIKLH。

6.25?证明：在结点数多于1的哈夫曼树中不存在度为1的结点。

6.26?假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

6.27?假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。

6.28?假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。

6.29?假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。

6.30?证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之前，且在后序序列中u在v之后。

6.31?证明：由一棵二叉树的先序序列和中序序列可唯一确定这课二叉树。

6.32?证明：如果一棵二叉树的先序序列是u1，u2，…，un，中序序列是up1，up2，…，upn，则序列1,2，…，n可以通过一个栈得到序列p1，p2，…，pn；反之，若以上述中的结论作为前提，则存在一棵二叉树，若其前序序列是u1，u2，…，un，则其中序序列为up1，up2，…，upn。

6.33?假定用两个一维数组L[n+1]和R[n+1]作为有n个结点的二叉树的存储结构，L[i]和r[i]分别指示结点i（i=1,2,…,n）的左孩子和右孩子，0表示空。试写一个算法判别结点u是否为结点v的子孙。

6.34?同6.33题的条件。先由L和R建立一维数组T[n+1]，使T中第i（i=1,2,…,n）个分量指示结点i的双亲，然后写判别结点u是否为结点v的子孙的算法。

6.35?假设二叉树中左分支的标号为“0”，右分支的标号为“1”，并对二叉树增设一个头结点，令根结点为其右孩子，则从头结点到树中任一结点所经分支的序列为一个二进制序列，可认作是某个十进制数的二进制表示。例如，右图所示二叉树中，和结点A对应的二进制序列为“110”，即十进制整数6的二进制表示。已知一棵非空二叉树以顺序存储结构表示，试写一尽可能简单的算法，求出与在树的顺序存储结构中下标值为i的结点对应的十进制整数。

6.36?若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。

6.37?试利用栈的基本操作写出先序遍历的非递归形式的算法。

6.38?同6.37题条件，写出后序遍历的非递归算法（提示：为分辨后序遍历时两次进栈的不同返回点，需在指针进栈时同时将一个标志进栈）。

6.39?假设在二叉链表的结点中增设两个域：双亲域（parent）以指示其双亲结点；标志域（mark取值0、1、2）以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

6.40?若在二叉链表的结点中只增设一个双亲域以指示其双亲结点，则在遍历过程中能否不设栈？试以此存储结构编写不设栈进行中序遍历的递推形式的算法。

6.41?编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。

6.42?编写递归算法，计算二叉树中叶子结点的数目。

6.43?编写递归算法，将二叉树中所有结点的左、右子树相互交换。

6.44?编写递归算法：求二叉树中以元素值为x的结点为根的子树的深度。

6.46?编写复制一棵二叉树的非递归算法。

6.47?编写按层次顺序（同一层自左至右）遍历二叉树的算法。

6.48?已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

6.49?编写算法判别给定二叉树是否为完全二叉树。

6.50?假设以三元组（F，C，L/R）的形式输入一棵二叉树的诸边（其中F表示双亲结点的标识，C表示孩子结点标识，L/R表示C为F的左孩子或右孩子），且在输入的三元组序列中，C是按层次顺序出现的。设结点的标识是字符类型。F=‘^’时C为根结点标识，若C也为‘^’，则表示输入结束。例如，6.15题所示的二叉树的三元组序列输入格式为：

试编写算法，由输入的三元组序列建立二叉树的二叉链表。

6.51?编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。

6.52?一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一算法，求二叉树的繁茂度。

6.53?试编写算法，求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径（即列出从根结点到该叶子结点的结点序列），若这样的路径存在多条，则输出路径终点（叶子结点）在“最左”的一条。

6.54?假设以顺序表sa表示一棵完全二叉树，sa.elem[1..sa.last]中存放树中各结点的数据元素。试编写算法由此顺序存储结构建立该二叉树的二叉链表。

6.55?为二叉链表的结点增加DescNum域。试编写一算法，求二叉树的每个结点的子孙数目并存入其DescNum域。请给出算法的时间复杂度。

6.56?试写一个算法，在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继（假设二叉树的根结点未知）。并讨论实现此算法对存储结构有何要求？

6.57?试写一个算法，在后序后继线索二叉树中，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并未给出）。并讨论实现此算法对存储结构有何要求？

6.58?试写一个算法，在中序全线索二叉树的结点*p之下，插入一棵以结点*x为根、只有左子树的中序全线索二叉树，使*x为根的二叉树称为*p的左子树。若*p原来有左子树，则令它为*x的右子树。完成插入之后的二叉树应保持全线索化特性。

6.59?编写算法完成下列操作：无重复地输出以孩子-兄弟链表存储的树T中所有的边。输出的形式为(k1, k2), …, (ki, kj), …,其中，ki和kj为树结点中的结点标识。

6.60?试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。

6.61?试编写算法，求一棵以孩子-兄弟链表表示的树的度。

6.62?对以孩子-兄弟链表表示的树编写计算树的深度的算法。

6.63?对以孩子链表表示的树编写计算树的深度的算法。

6.64?对以双亲表表示的树编写计算树的深度的算法。

6.65?已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

6.66?假设有n个结点的树T采用了双亲表示法，写出由此建立树的孩子-兄弟链表的算法。

6.67?假设以二元组（F，C）的形式输入一棵树的诸边（其中F表示双亲结点的标识，C表示孩子结点标识），且在输入的二元组序列C中，C是按层次顺序出现的。F=‘^’时C为根结点标识，若C也为‘^’，则表示输入结束。例如，如下所示树的输入序列为：

    试编写算法，由输入的二元组序列建立该树的孩子-兄弟链表。

6.68?已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度（每层中自左至右输入），试写出构造此树的孩子-兄弟链表的算法。

6.69?假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母，试编写算法，按树形状打印二叉树的算法。例如：左下二叉树印为右下形状。

6.70?如果用大写字母标识二叉树结点，则一棵二叉树可以用符合下面语法图的字符序列表示。试写一个递归算法，由这种形式的字符序列，建立相应的二叉树的二叉链表存储结构。

6.71?假设树上每个结点所含的数据元素为一个字母，并且以孩子-兄弟链表为树的存储结构，试写一个按凹入表方式打印一棵树的算法。例如：左下所示树印为右下形状。

6.72?以孩子链表为树的存储结构，重做6.71题。 孩子-兄弟链表

6.73?若用大写字母标识树的结点，则可用带标号的广义表形式表示一棵树，其语法图如下所示：

    例如，6.71题中的树可用下列形式的广义表表示：

    试写一递归算法，由这种广义表表示的字符序列构造树的孩子-兄弟链表（提示：按照森林和树相互递归的定义写两个互相递归调用的算法，语法图中一对圆括号内的部分可看成为森林的语法图）。

6.74?试写一递归算法，以6.73题给定的树的广义表表示法的字符序列形式输出以孩子-兄弟链表表示的树。

6.75?试写以递归算法，由6.73题定义的广义表表示法的字符序列，构造树的孩子链表。

6.76?试写以递归算法，以6.73题给定的树的广义表表示法的字符序列形式输出以孩子链表表示的树。

树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。

在树结构中，每一个结点只有一个前件，称为父结点。如A即为结点B、C、D的父结点。

没有父结点的结点只有一个，称为根结点。如上图所示，结点A即为根结点。

每一个结点可以有多个后件，它们均称为该结点的子结点。如结点G、H、I是结点D的子结点。

没有后件的结点，称为叶子结点。上图中，叶子结点有：J、M、N、L、C、G、H、I。

在树结构中，一个结点所拥有的后件结点个数称为该结点的度。例如，结点D的度为3，结点E的度为1等，按此原则，所有叶子结点的度均为0。

在树中，所有结点中最大的度称为该树的度。上图所示的树中，所有结点中最大的度是3，所以该树的度为3。

树分层，根结点为第一层，往下依次类推。同一层结点的所有子结点均在下一层。如上图：A结点在第1层，B、C、D结点在第2层；E、F、G、H、I在第3层；J、K、L在第4层；M、N在第5层。

树的最大层次称为树的深度。上图树的深度为5。

在树中，某结点的一个子结点为根构成的树称作该结点的子树。叶子结点没有子树。

在计算机中，可以用树来表示算术表达式。原则如下：

（1）表达式中每一个运算符在树中对应一个结点，称为运算符结点

（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）

（3）运算对象中的单变量均为叶子结点

树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（即指针域）个数将随着树中该结点的度而定义。

如果在树中，每一个结点的子结点的个数不相同，因此在多重链中各结点的链域个数也不相同，会导致算法太复杂。因此，在树中，常采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的链域的个数。这样，管理相对简化了，但会造成空间的浪费，因为有许多的结点存在空链域。

2．二叉树及其基本性质

非空二叉树只有一个根结点

每一个结点最多只有两个子结点，且结点分左右。则一个结点最多可以有两棵子树，分别称为左子树和右子树

在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。

在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，则该结点为叶子结点。

性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。

性质2：深度为m的二叉树最多有2m-1个结点。

性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。

性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。

3）满二叉树与完全二叉树

除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树上的第k层上有2k-1个结点。如下即为一棵满二叉树。

特点：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干个结点。

即如果从根结点开始，对二叉树的结点自上而下、自左而右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，则是完全二叉树。

对于完全二叉树，叶子结点只能在层次最大的两层中出现；对于任何一个结点，若其右分支下的子树结点的最大层次为p，则其分支下的子孙结点的最大层次为p或p+1。

完全二叉树具有的性质：

性质5：具有n个结点的完全二叉树的深度为[log2n]+1

性质6：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1、2……、n给结点编号，对于编号为k（k=1,2,……n）的结点有如下结论：

① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。

② 若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（当然也没有右子结点）

③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。

二叉树的存储常采用链式存储结构。

存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。

即二叉树的存储结构中每一个存储结点都有两个指针域，因此，二叉树的链式存储结构也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。

如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是：

当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树。

二叉树的遍历即是不重复地访问二叉树的所有结点。

在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。

前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。

若二叉树为空，则结束返回。

否则：访问根结点?前序遍历左子树?前序遍历右子树

如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O

中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。

若二叉树为空，则结束返回。

否则：中序遍历左子树?访问根结点 ?中序遍历右子树

这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。

如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O

后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。

若二叉树为空，则结束返回。

否则：前序遍历左子树?前序遍历右子树?访问根结点

如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A