06树与二叉树

1、作业要求： 五： 2、 3 六：2、3、6（1）、7、10 七：1、2 习题 6 一名词解释 （ 1）结点 （ 2）结点的度 （ 3）树的度 （ 4）二叉树 （ 5）哈夫曼树 二判断题（下列各题，正确的请在前面的括号内打；错误的打） （ ）（ 1）树结构中每个结点最多只有一个直接前趋。 （ ）（ 2）完全二叉树一定是满二叉树。 （ ）（ 3）由树转换成二叉树，其根结点的右子树一定为空。 （ ）（ 4）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 （ ）（ 5）在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结 点之后。 （ ）（ 6）一棵二叉树中序遍历序列的最后一个结

2、点，必定是该二叉树前序遍历的最后 一个结点。 （ ）（ 7）用一维数组来存储二叉树时，总是以前序遍历存储结点。 （ ）（ 8）已知二叉树的前序遍历和后序遍历不能惟一确定这棵二叉树，这是因为不知 道根结点是哪一个。 （ ）（ 9）二叉树按某种顺序线索后，任一结点均有指向其前趋和后继的线索。 （ ）（10 ）二叉树的前序遍历中，任意一个结点均处于其子树结点的前面。 三填空题 1结点的度是。 2叶子结点是结点。 3树的度是。 4树中结点的最大层次称为树的。 5对于二叉树来说，第 i 层上至多有 个结点。 6深度为 h 的二叉树至多有个结点。 7对于一棵具有 n 个结点的树，该树中所有结点的度数之和为

3、： 。 8在一棵二叉树中，度为 2 的结点有 5 个，度为 1 的结点有 6 个，则叶子结点数有 个。 9由一棵二叉树的前序序列和序列可惟一确定这棵二叉树。 10 有 20 个结点的完全二叉树，编码为 10 的结点的父结点的编号是 。 11有 20个结点的完全二叉树，编码为 10 的结点的左子树结点的编号是 12一棵含有 n 个结点的完全二叉树，它的高度是 。 2对于二叉树来说，第 K 层至多有（ B2K-1 ）个结点。 C 2K -1 D 2K-1-1 3结点前序为 ABC 的不同二叉树有（ ）种形态。 4某二叉树的先序遍历序列为： IJKLMNO 历序列为（ ，中序遍历序列为： JLKIN

4、MO ，则后序遍 A JLKMNOI B LKNJOMI CLKJNOMI DLKNOJMI 13树的存储结构有： 14 哈夫曼树是带权路径长度 的二叉树。 15 某二叉树的前序遍历序列为： DABEC ，中序遍历序列为： A DEBAC ，则后序遍历序列为： 。 给定右图所示的二叉树： B C 16 其前序遍历序列为： 。 17 其中序遍历序列为： 。 E F G 18 其后序遍历序列为： 。 19 结点最少的二叉树是 。 H 20前序为 A，B，C且后序为 C，B，A 的二叉树共有种。 四选择题 1深度为 h 的二叉树至多有（ ）个结点。 A2h B2h-1 C2h-1 D2h-1-1 5

5、某二叉树的后序遍历序列为： DABEC ，中序遍历序列为 : DEBAC ，则先序遍历序列 为（ ）。 AACBED B DECAB CDEABC DCEDBA 6具有 35 个结点的完全二叉树的深度为（） D都有可能 7二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法 （ ）。 A C B G F D E A C B F D E A C B D E A C B D 8根据树的定义，具有 3 个结点的树有（ ）种树型。 A2 B3 C4 D5 A 正确 C不确定 B错误 9下列 4 棵树，（ ）。 10树最适合用来表示（ A 有序数据元素B无序数据元素 C元素之间无联系的

6、数据D元素之间有分支层次的关系 11对于一棵满二叉树， m 个树叶， n 个结点，深度为 h，则（ A n=h+mB h+m=2nCm=h-1 12 一棵 n 个结点的二叉树，其空指针域的个数为（ A nB n+1Cn-1 ）。 ）。 Dn=2h- 1 D不确定 13任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ A 不发生改变B发生改变 14A ，B 为一棵二叉树上的两个叶子结点， A A 在 B 的右方 B A 是 B 的祖先 15 线索二叉树是一种（ ）结构。 A 物理B逻辑 五简答题 1什么是一般树？什么是二叉树？ ）。 C不能确定D以上都不对 在中序遍历时， A 在

7、 B 前的条件是 （ C A 在 B 的左方DA 是 B 的子孙 ）。 C逻辑和存储 D线性 *2 一棵度为 2 的树与一棵二叉树有何区别？ *3 已知一棵树边的集合如下，请画出此树，并回答问题。 L ，M），L，N，E，L，B，E，B，D，A ，B，G，J，G，K， C， G，C，F，H，I，C，H， A ， C （ 1）哪个是根结点？ （ 2）哪些是叶子结点？ （ 3）哪个是 G 的双亲？ （ 4）哪些是 G 的祖先？ （ 5）哪些是 G 的孩子？ （ 6）哪些是 E 的子孙？ （ 7）哪些是 E 的兄弟？哪些是 F 的兄弟？ （ 8）结点 B 和 N 的层次各是多少？ （ 9）树的深度是

8、多少？ （ 10 ）以结点 C 为根的子树的深度是多少？ （ 11）树的度数是多少？ 六应用题 1二叉树按中序遍历的结果为： ABC ，试问有几种不同形态的二叉树可以得到这一遍 历结果？并画出这些二叉树。 *2 分别画出具有 3 个结点的树和三个结点的二叉树的所有不同形态。 *3 已知一棵二叉树的后序遍历和中序遍历的序列分别为： A ，C，D，B，G，I，H，F，E 和 A ，B，C， D，E，F，G，H，I。 请画出该二叉树，并写出它的先序遍历的序列。 4已知一棵二叉树的先序遍历和中序遍历的序列分别为： A ，B，D，G，H，C，E，F，I 和 G，D，H，B，A ， 请画出此二叉树，并写出

9、它的后序遍历的序列。 5已知一棵二叉树的层次序列为： 请画出该二叉树。 6把下列一般树转换为二叉树 A B C D E F G H I J， E，C，I，F。 中序序列为 D B G E H J A C I F ， * （1） 1 A 2 B C D 3 5 F G E H I J 8 F A B I J G E A B E G F C D H I *7 把下列森林转换为二叉树 C D 6 7 并求它们的后缀表达式。 2） H 8把下列二叉树还原为森林 9画出下列表达式的标识符树， （ 1） -A+B -C+D （ 2）（A+B/C -D）*（E* （ F+G ） *10 给定一个权集 W=4 ，5， 7，8，6，12，18 ，请画出相应的哈夫曼树，并计算其 带权路径长度 WPL 。 11给定一个权集 W=3 ，15，17，14，6， 16，9， 2 ，请画出相应的哈夫曼树，并计 算其带权路径长度 WPL 。 七算法设计题 以二叉链表为存储结构，设二叉树 BT 结构为： typedef struct BT char data; BT *lchild; BT *