5.11 本 章 小 结
5.11 本 章 小 结
本章的基本内容是：树的定义和表示；树的基本术语和存储结构；二叉树的定义、遍历、存储结构及其基本运算的实现；哈夫曼树的定义及其构造与编码。
树形结构是一种非常重要的层次型的一对多的非线性结构，在树形结构中，除了根节点外，每个节点只有一个直接前趋（为它的父节点），但可以有多个直接后继（为它的孩子节点）。
树的存储结构可以采用双亲表示法、孩子表示法和孩子兄弟表示法来表示。利用树能很好地描述现实问题中的分支关系和层次关系。
二叉树是一种特殊的树形结构，它的特点是每个节点最多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。要注意的是二叉树不是树的特例。
二叉树的遍历是指按一定的规则和次序访问树中的每个节点，且每个节点只能被访问一次。主要有先序遍历、中序遍历和后序遍历3种方法。
线索二叉树是二叉树链式存储的特殊形式，它充分利用了二叉树链式结构的空指针来指向节点的直接前趋和直接后继，这样就方便地解决了某一节点的直接前趋和直接后继问题。
哈夫曼树在现代通信中有较高的使用价值，应掌握它的构建方法及哈夫曼编码的应用。
5.12 练 习 题
1．选择题
（1）二叉树是非线性数据结构，所以 。
A．它不能用顺序存储结构存储
B．它不能用链式存储结构存储
C．顺序存储结构和链式存储结构都能存储
D．顺序存储结构和链式存储结构都不能使用
（2）具有n（n>0）个节点的完全二叉树的深度为 。
A．élog2(n)ù B．?log2(n)?
C．?log2(n)?+1 D．élog2(n)+1ù
（3）把一棵树转换为二叉树后，这棵二叉树的形态是 。
A．唯一的 B．有多种
C．有多种，但根节点都没有左孩子 D．有多种，但根节点都没有右孩子
（4）如下所示的4棵二叉树中， 不是完全二叉树。
A B C D
（5）在线索化二叉树中，t所指节点没有左子树的充要条件是 。
A．t->left == NULL B．t->ltag == 1
C．t->ltag ==1且t->left == NULL D．以上都不对
（6）设高度为h的二叉树上只有度为0和度为2的节点，则此类二叉树中所包含的节点数至少为 。
A．2h B．2h-1
C．2h +1 D．h+1
（7）已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是
。
A．acbed B．decab
C．deabc D．cedba
（8）如果T2是由有序树T转换而来的二叉树，那么T中节点的前序就是T2中节点的
。
A．前序 B．中序
C．后序 D．层次序
（9）如果T2是由有序树T转换而来的二叉树，那么T中节点的后序就是T2中节点的
。
A．前序 B．中序
C．后序 D．层次序
（10）某二叉树的前序遍历节点访问顺序是abdgcefh，中序遍历节点访问顺序是dgbaechf，则其后序遍历节点访问顺序是 。
A．bdgcefha B．gdbecfha
C．bdgaechf D．gdbehfca
（11）已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是 。
A．acbed B．decab
C．deabc D．cedba
（12）如果T2是由有序树T转换而来的二叉树，那么T中节点的前序就是T2中节点的 。
A．前序 B．中序
C．后序 D．层次序
（13）如果T2是由有序树T转换而来的二叉树，那么T中节点的后序就是T2中节点的 。
A．前序 B．中序
C．后序 D．层次序
（14）某二叉树的前序遍历节点访问顺序是abdgcefh，中序遍历节点访问顺序是dgbaechf，则其后序遍历节点访问顺序是 。
A．bdgcefha B．gdbecfha
C．bdgaechf D．gdbehfca
2．填空题
（1）指出树和二叉树的3个主要差别 、 、 。
（2）从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是 。
（3）深度为k的完全二叉树至少有 个节点，至多有 个节点，若按自上而下、从左到右的次序给节点编号（从1开始），则编最小的叶子节点的编号是
。
（4）一棵二叉树的第k层最多有 个节点；一棵有n个节点的满二叉树共有
个叶子和 个非终端节点。
（5）节点最少的树为 ，节点最少的二叉树为 。
（6）现有按中序遍历二叉树的结果是abc，问有 种不同形态的二叉树可以得到这一遍历结果。
（7）根据二叉树的定义，具有3个节点的二叉树有 种不同的形态。
（8）线索二叉树是一种 结构。
3．问答题
（1）一棵度为2的树与一棵二叉树有何区别？
（2）一棵树的边集为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,
<C,F>,<H,L>,<C,H>,<A,C>}，画出这棵树，并回答下列问题：
①哪个是根节点？
②哪个是叶子节点？
③哪个是节点G的双亲？
④哪些是节点G的祖先？
⑤哪些是节点G的孩子？
⑥哪些是节点E的子孙？
⑦哪些是节点E的兄弟？哪些是节点F的兄弟？
⑧节点B和N的层次号分别是什么？
⑨树的深度是多少？
⑩以节点C为根的子树的深度是多少？
（3）设一棵完全二叉树的层次遍历序列为：ABCDEFGHIJKL，请给出先序、中序和后序遍历序列。
（4）有一份电文中共使用了5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根节点的权小于等于右子树根节点的权的次序构造），并求出每个字符的哈夫曼编码。
（5）假设树根的层次（Level）为1，且整棵二叉树的层次为10，试回答下列问题：
①此棵二叉树总共有几个节点？
②第8层次最多有多少个节点？
③假设叶节点共有128个，则度为2的节点有多少个？
4．上机操作题
（1）设二叉树用二叉链表为存储结构，请编写一个复制一棵二叉树的算法。
（2）假设以二叉链表作为存储结构（每个节点的值均不相等），设计一个算法，求二叉树中值最大的节点指针。
（3）请编写一个算法，实现将以二叉链表存储的二叉树中所有节点的左、右孩子进行交换。
（4）假设以二叉链表作为存储结构（每个节点的值均不相等），设计一个算法，求二叉树中值为x的节点指针。
（5）假设以二叉链表作为存储结构，设计一个算法，删除并释放一棵二叉树的所有节点。