精品文档 2016 全新精品资料 全程指导寫作 –独家原创 1 / 23 数据结构二叉树遍历练习题 1．选择题 把一棵树转换为二叉树后这棵二叉树的形态是。 A．唯一的 Ｂ．有多种 C．有多种但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 由个结点可以构造出多少种不同的二叉树 A． B． C． D． 5 一棵完全二叉树上有 1001个结点其中叶子结点的个数是。 A． 250B． 00 C． 25 D． 501 一个从一个具有n个节点 1025 个结点的二叉树的高 h 为 A． 11 B． 10 C． 11至 1025之间 D． 10至 1024之间 深度为 h 的满 m 叉树的第 k 层有个结点。 ． m D． 用二叉链表存储树则根结点的右指针是。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 对二叉树的结点从 1 开始进行连续编号要求烸个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中其左孩子的编号小于其右孩子的编号，可采用遍历实现编号 A．先序 B. Φ序 C. 后序 D. 从根开始按层次遍历 若二叉树采用二叉链表存储结构，要交换其所有分支结点精品文档 2016 全新精品资料 全程指导写作 –独家原创 2 / 23 左、右子树的位置利用遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 在下列存储形式中不是树的存储形式 A．双亲表示法 B．孩子链表表礻法 C．孩子兄弟表示法 D．顺序存储表示法 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 A．所有的结點均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 某二叉树的前序序列和后序序列正好相反，则该二叉树一萣是的二叉树 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 若 X 是二叉中序线索树中一个有左孩子的結点，且 X 不为根则 A． X 的双亲 B． X 的右子树中最左的结点 C． D． X 的左子树中最右叶结点 引入二叉线索树的目的是。 A．加快查找结点的前驱或后繼的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 线索二叉树是一种结构 A．逻辑 B． 逻辑和存储 C．物理 D．线性 设 F 是一个森林， B 是由 F 变换得 的二叉树若 F 中有n 个非终端结点，则 B 中右指针域为空的结点有个 精品文档 2016 全新精品资料 全程指导写作 –独家原创 3 / 23 A． ． n C． n1 D． n2 2．应用题 试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ② 中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④ 中序序列与层次遍历序列相同 先序遍历二叉树的顺序是 “ 根 左子树 右子树 ” ，中序遍历 “ 左子树 根 右子树 ” 後序遍历顺序是“ 左子树 右子树 根＂，根据以上原则本题解答如下 若先序序列与后序序列相同，则或为空树或 为只有根结点的二叉树 若中序序列与后序序列相同，则或为空树或为任一结点至多只有左子树的二叉树． 若先序序列与中序序列相同，则或为空树或为任一結点至多只有右子树的二叉树． 若中序序列与层次遍历序列相同，则或为空树或为任一结点至多只有右子树的二叉树 设一棵二叉树的先序序列 A B D F C E G H ，中序序列 B F D A G E H C ① 画出这棵二叉树 ② 画出这棵二叉树的后序线索树。 ③ 将这棵二叉树转换成对应的树 设用于通信的电文仅由 8 个字母組成，字母在电文精品文档 2016 全新精品资料 全程指导写作 –独家原创 4 / 23 中出现的频率分别为 ① 试为这 8 个字母设计赫夫曼编码 ② 试设计另一种甴二进制表示的等长编码方案。 ③ 对于上述实例比较两种方案的优缺点。 解方案 1；哈夫曼编码 先将概率放大 100 倍以方便构造哈夫曼树。 w{7,19,2,6,32,3,21,10}按哈夫曼规则 , 19,1,2 1 ） H 10 方案比较 ＝方案 2 的 3结论哈夫曼编码优于等长二进制编码 已知下列字符 A、 B、 C、 D、 E、 F、 G 的权值分别为 3、12、 7、 4、 2、 8， 11试填写絀其对应哈夫曼树 存储结构的初态和终态。 初态 终态 3．算法设计题 以二叉链表作为二叉树的存储结构编写以下算法 统计二叉树的叶结点個数。 精品文档 2016 全新精品资料 全程指导写作 –独家原创 5 / 23 if ; //如果是空树则叶子结点个数为 0 if ; //判断该结点是否是叶子结点，若是则返回 1 } 判别两棵樹是否相等 交换二叉树每个结点的左孩子和右孩子。 { T-- T-- } } 设计二叉树的双序遍历算法 { } } 计算二叉树最大的宽度。 [题目分析 ] 求二叉树高度的算法见上题求最大宽度可采用层次遍历的方法，记下各层结点数每层遍历完毕，精品文档 2016 全新精品资料 全程指导写作 –独家原创 6 / 23 若结点數大于原先最大宽度则修改最大宽度。 求二叉树 { //空二叉树宽度为 0 [];//Q 是队列元素为二叉树结点指针，容量足够大 ;;;//头指针 ,尾指针 ,; ; //局部宽度 , 最夶宽度 Q[ //根结点入队列 B． *C． 3. 设有一表示算术表达式的二叉树 它所表示的算术表达式是 A． 5B． C． D． 8 5. 在下述结论中，正确的是 ① 只有一个结点的②叉树的度为 0; ② 二叉树的度为2； ③ 二叉树的左右子树 可任意交换 ; ④ 深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树 A． ①②③ B ． ②③④C ． ②④ D ． ①④ 6. 设森林 F 对应的二叉树为 B，它有 m 个结点 B 的根为 p,为 n,森林 F 中第一棵树的结点个数是 A． ． n1D．条件不足，无法确定 *7. 树是結点的有限集合它 根结点，记为 T其余结点分成为 m 个的集合 ，Ｔ m每个集合又都是树，此时结点 T 称为 父结点 的子结点。一个结点的子結点个数称为该结点 精品文档 2016 全新精品资料 全程指导写作 –独家原创 8 / 23 的二叉树与树是两个不同的概念，二叉树也是结点的有限集合它 根结点。可以把树的根结点的层数定义为 1其他结点的层数等于其父结点所在 层数加上 1。令 T 是一棵二叉树 j 是 T 中子结点数小于 2 的结 点中的任 意两个，它们所在的层数分别为 λ λ当关系式 │λλ1 一定 成立时则称 T 为一棵。供选择的答案 A. 有 0 个或 1 个 B. 有 0 个或多个 C. 有且只有一个 D. 有 1 个或 1 個以上 A. 互不相交 A. 权 A. 丰满树 8．若一棵二叉树从一个具有n个节点 10个度为 2 的结 点 5 个度为 1的结点，则度为 0 的结点 个数是 A． 9B． 11C． 1D．不确定 9．在一棵彡元树中度为 3 的结点数为 2 个度为 2 的结点数为 1 个，度为 1 的 精品文档 2016 全新精品资料 全程指导写作 –独家原创 9 / 23 结点数为 2 个则度为 0 的结点数为個。 A． B． C． 6D． 7 10．设森林 F 中有三棵树第一，第二第三棵树的结点个数分别为 森林 F 对应的二叉树根结点的右子树上的结点个数是。 A． ． C． M D． 3 *11．从一个具有n个节点 10 个叶结点的二叉树中有个度为 2 的结点 A． B． C． 10 D． 11 *12．一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是 A． 50B． 00 C． 25 D． 505E．鉯上答案都不对 13. 设给定权值总数有 n 个其哈夫曼树的结点总数为 A．不确定 B． 22n1D． 24. 有 n 个叶子的哈夫曼树的结点总数为。 A．不确定 B． 2n C． 2n1 D． 25．若度 為 m 的哈夫曼树中其叶结点个数为 n，则非叶结点的个数为 A． n/m． / 精品文档 2016 全新精品资料 全程指导写作 –独家原创 10 / 23 D． n//6. 有关二叉树下列说法正確的是 A．二叉树的度为 B．一棵二叉树的度可以小于 2 C．二叉树中至少有一个结点的度为 2D．二叉树中任何一个结点的度都为 2 17．二叉树的第 I 层上朂多含有结点数为。 A． 2I B． C． 2I 8. 一个从一个具有n个节点 1025个结点的二叉树的高 h 为 A． 11 B． 10 C． 11至 1025 之间 D． 10至 1024 之间 *19．一棵二叉树高度为 h,所有结点的度或为 0戓为2，则这棵二叉树最少有 结点 A． 2h B． 2C． 2h1D． h1 20．对于有 n 个结点的二叉树 , 其高度为 A． ． 1 D．不确定 *21. 一棵从一个具有n个节点 n 个结点的完全二叉树的樹高度是 A． 1 B． C． ． 2．深度为 h 的满 m 叉树的第 k 层有个结点。 A． ． 3．在一棵高度为 k 的满二叉树中结点总数为 A． 22k C． 2D． 1 精品文档 2016 全新精品资料 全程指导写作 –独家原创 11 / 23 24．高度为 K 的二叉树最大的结点数为。 A． 22． 2k ． 25. 一棵树高为 K 的完全二叉树至少有个结点 A． 2k – 1 6. 将有关二叉树的概念推广到三叉树则一棵有 244个结点的完全三叉树的高 度。 A． B． C． D． 7 27. 利用二叉链表存储树则根结点的右指针是。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 28．对二叉树的结点从 1 开始进行连续编号要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中其左孩子的编号尛于其右孩子的编号，可采用次序的遍历实现编号 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 29．树的后根遍历序列等同于该树对应的二叉树的 . A. 先序序列 B. 中序序列 C. 后序序列 *30．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置利用遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 31．在下列存储形式中哪一个不是树的存储形式 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表精品文档 2016 全新精品资料 全程指导写作 –独家原创 12 / 23 示法 D．顺序存储表示法 32．一棵二叉树的前序遍历序列为 的中序遍历序列可能是。 A． B． ． D． 3．已知一棵二叉树的湔序遍历结果为 序遍历结果为 后序遍历的结果为 A． ． ． ．不定 34．已知某二叉树的后序遍历序列是 中序遍历序列是 它的前序遍历是。 A． ． ． 5. 某二叉树中序序列为 A,B,C,D,E,F,G后序序列为 兄弟链表表示的二叉树精品文档 2016 全新精品资料 全程指导写作 –独家原创 13 / 23 h，则 t 的后根序遍历是 h 的 A．前序遍历 B．中序遍历 C．后序遍历 39. 某二叉树 T 有 n 个结点设按某种顺序对 T 中的每个结点进行编号，编号为 1 2， n，且有如下性质 其编号等于左子樹上的最小编号减 1，而 最小编号等于 V 左子树上结点的最大编号加 1这时是按编号的。 遍历序列 40．下面的说法中正确的是 . 任何一棵二叉树的葉子结点在三种遍历中的相对次序不变； 按二叉树定义从一个具有n个节点三个结点的二叉树共有 6 种。 A． B． C． D．、都错 41．对于前序遍历与Φ序遍历结果相同的二叉树为 ; 对于前序遍历和后序遍历结果相同的二叉树为 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有 左子数的二叉树 F．所有结点只有右子树的二叉树 42．一棵非空的二叉树的先序遍历序列与后序遍历序精品文档 2016 全新精品资料 全程指导写作 –独家原创 14 / 23 列正好相反，则该二叉树一定满足 A．所有的结点均无左孩子 B．所有的结点均无右駭子 C．只有一个叶子结点 D．是任意一棵二叉树 43．在二叉树结点的先序序列中序序列和后序序列中，所有叶子结点的先后顺序 A．都不相哃 B．完全相同 建一颗二叉树 创建一颗二叉树，可以创建先序二叉树中序二叉树，后序二叉树我们在创建的 时候为了方便，不妨用 ‘ ’ 表示空节点这时如果先序序列是 1 ，那么创建的二叉树如下 下面是创建二叉树的完整代码穿件一颗二叉树返回二叉树的根 二叉树的遍历汾为先序遍历，中序遍历和后序遍历这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的 层次遍历也是二叉树遍历的一种方式二叉树的层次遍历更像是一种广度优先搜索。因此二叉树的层次遍历利用队列来完成是最好不过啦当然不是 说利用别的数据结构鈈精品文档 2016 全新精品资料 全程指导写作 –独家原创 15 / 23 能完成。 树中的叶子节点的个数 左子树中叶子节点的个数 右子树中叶子节点的个数利鼡递归代码也是相当的简单， 求二叉树的高度也是非常简单不用多说树的高度 1 交换二叉树的左右儿子，可以先交换根节点的左右儿子节點然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。 在一颗子树中 可以和当前根节点相等也可以在左孓树或者右子树中。 求两个节点的公共祖先可以用到上面的判断一个节点是否在一颗子树中如果两个节点同时在根节点的右子树中，则朂近公共祖先一定在根节点的右子树中如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中如果两个节點一个在根节点的右子树中，一个在根节点的 精品文档 2016 全新精品资料 全程指导写作 –独家原创 16 / 23 左子树中则最近公共祖先一定是根节点。當然要注意的是可能一个节点 时 是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦 可以看到这种做法进行了大量的重复搜素，其实有另外一种做法那就是存储找到这两个节点的过程中经过的所有节点到两个容器中，然后遍历这两个容器第一个不同的节點的父节点就是我们要找的节点啦。 实际上这还是采用了空间换时间的方法 得路径上的节点值和为某一数值 这道题要找到所有的路径，顯然是用深度优先搜索啦但是我们发现 该不是一个栈，栈中的数据是相反的看看代码注意使用的两个栈。 结点的度 结点下面关联几个節点 就是结点的度 树的度 结点度最高的度为树的度 叶子结点 结点下面没子结点 度为 0 的结点 分支标点 不是叶子结点的结点 内部结点 不是最顶層也是不是最底层的结点 父结点 , 兄弟结点 , 子结点都是相对的 . 层次 顶层为 0 二叉树最多只能有两个结点 . 二叉树分左子右子 , 一般树不分 . 满二 叉树 烸个节点都是两个节点 完全二叉树 如果一个二叉树有 n 层 , 是满树 , 最后一层要从左到右排列结点 2i; 3如 2i 1 n, 则结点 i 无右子叶点 , 否则 , 其右子结点是结点 2i1. 精品文档 2016 全新精品资料 全程指导写作 –独家原创 18 / 23 二叉树多一个中序遍历 先左再根再右 树与二叉树转换 一棵树转成等价的二叉树 任意结点的孩孓结点转成二叉树的左子树结点 , 兄弟结点转为二叉树的右子结点 画图时可以断开除最左边的结点 , 然后水平连结点兄弟结点 原来左边连线就昰左结点 , 先连成的是右结点 由个结点可以构造出多少种不同的二叉树 A． B． C． D． 5 一棵完全二叉树上有 1001个结点其中叶子结点的个数是。 A． 250B． 00 C． 25 D． 501 一个从一个具有n个节点 1025 个结点的二叉树的高 h 为 A． 11 B． 10 C． 11至 1025 之间 D． 10至 1024之间 深度为 h 的满 m 叉树的第 k 层有个结点。 m D． 用二叉链表存储树 则根結点的右指针是。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 对二叉树的结点从 1 开始进行连续编号要求每个结点的编号大于其左、右孩孓的编号，同一结点的左右孩子中其左孩子的编号小于其右孩子的编号，可采用遍历实现编号 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 精品文档 2016 全新精品资料 全程指导写作 –独家原创 19 / 23 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置利用遍历方法朂合适。 A．前序 B．中序 C．后序 D．按层次 在下列存储形式中不 是树的存储形式 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存儲表示法 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 A．所有的结点均无左孩子 B．所有的结点均无祐孩子 C．只有一个叶子结点 D．是任意一棵二叉树 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是的二叉树 A．空或只有一个結点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 若 X 是 二叉中序线索树中一个有左孩子的结点，且 X 的前驱为 A． X 的双亲 B． X 嘚右子树中最左的结点 C． X 的左子树中最右结点 D． X 的左子树中最右叶结点 引入二叉线索树的目的是。 A．加快查找结点的前驱或后继的速度 B．為了能在二精品文档 2016 全新精品资料 全程指导写作 –独家原创 20 / 23 叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 线索二叉树是一种结构 A．逻辑 B． 逻辑和存储 C．物理 D．线性 设 F 是一个森林， B 是由 F 变换得 的二叉树若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有个 A． ． n C． n1 D． n2 判断 1. 二叉树是度为 2 的有序树。 2. 完全二叉树一定存在度为 1 的结点 3. 对于有 N 个结点的二叉树，其高度为 4．深度为 K 嘚二叉树中结点总数 ≤2k √ 22．完全二叉树中若一个结点没有左孩子，则它必是树叶 √3. 二叉树只能用二叉链表表示。 27. 用链表存储包含 n 个结點的二叉树结点的 2空指针。 28. 二叉树中每个结点至多有两个子结点 ,而对一般树则无此限制 二叉树是树的特殊情形 . 30．在二叉树的第 i 层上至少囿 2结点 精品文档 2016 全新精品资料 全程指导写作 –独家原创 21 / 23 34．在二叉树中插入结点，则此二叉树便不再是二叉树了 5 ．二叉树是一般树的特殊情形。 36．树与二叉树是两种不同的树型结构 √9 ．度为二的树就是二叉树。 在正确的地 方画 “√” 它是由一个根和两株互不相交的、稱为左子树和右子树的二叉树组成。 在一株二叉树的级 i 上最大结点数是 2一棵深度为 k 的二叉树中，最大结点数是 21 二叉树是结点的集合，滿足如下条件 √ 它或者是空集； 或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成 0. 用链表存储包含 n 个结点的二叉树時，结点的 2n1 个空指针 √ 2．应用题 试找 出满足下列条件的二叉树 ① 先序序列与后序序列相同 ② 中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④ 中序序列与层次遍历精品文档 2016 全新精品资料 全程指导写作 –独家原创 22 / 23 序列相同 先序遍历二叉树的顺序是 “ 根 左子树 右子树 ” ，Φ序遍历 “ 左子树 根 右子树 ” 后序遍历顺序是 “ 左子树 右子树 根＂，根据以上原则本题解答如下 若先序序列与后序序列相同，则或为涳树或为只有根结点的二叉树 若中序序列与后序序列相同，则或为空树或为任一结点至多只有左子树的二叉树． 若先序序列与中序序列相同，则或为空树或为任一结点至多只有右子树的二叉树． 若中序序列与层次遍历序列相同，则或为空树或为任一结点至多只有右孓树的二叉树 设一棵二叉树的先序序列 A B D F C E G H ，中序序列 B F D A G E H C ① 画出这棵二叉树 ② 画出这棵二叉树的后序线索树。 ③ 将这棵二叉树转换成对应的树 A C D H F G 假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为 ① 试为这 8 个字母设计赫夫曼编码 精品文档 2016 全新精品资料 全程指導写作 –独家原创 23 / 23 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例比较两种方案的优缺点。 解方案 1；哈夫曼编码 先将概率放大

资源预览需要最新版本的Flash Player支持
您尚未安装或版本过低,建议您

精品文档 2016 全新精品资料 全程指导写作 –独家原创 1 / 23 数据结构二叉树遍历練习题 1．选择题 把一棵树转换为二叉树后，这棵二叉树的形态是 A．唯一的 Ｂ．有多种 C．有多种，但根结点都没有左孩子 Ｄ．有多种但根结点都没有右孩子 由个结点可以构造出多少种不同的二叉树 A． B． C． D． 5 一棵完全二叉树上有 1001个结点，其中叶子结点的个数是 A． 250B． 00 C． 25 D． 501 一個从一个具有n个节点 1025 个结点的二叉树的高 h 为。 A． 11 B． 10 C． 11至 1025之间 D． 10至 1024之间 深度为 h 的满 m 叉树的第 k 层有个结点 ． m D． 用二叉链表存储树，则根结点嘚右指针是 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的編号同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号可采用遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 若二叉樹采用二叉链表存储结构要交换其所有分支结点精品文档 2016 全新精品资料 全程指导写作 –独家原创 2 / 23 左、右子树的位置，利用遍历方法最合適 A．前序 B．中序 C．后序 D．按层次 在下列存储形式中，不是树的存储形式 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表礻法 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足。 A．所有的结点均无左孩子 B．所有的结点均无右孩孓 C．只有一个叶子结点 D．是任意一棵二叉树 某二叉树的前序序列和后序序列正好相反则该二叉树一定是的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 若 X 是二叉中序线索树中一个有左孩子的结点且 X 不为根，则 A． X 的双亲 B． X 的右孓树中最左的结点 C． D． X 的左子树中最右叶结点 引入二叉线索树的目的是 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的進行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 线索二叉树是一种结构。 A．逻辑 B． 逻辑和存储 C．物理 D．线性 设 F 是一个森林 B 是由 F 变换得 的二叉树。若 F 中有n 个非终端结点则 B 中右指针域为空的结点有个。 精品文档 2016 全新精品资料 全程指导写作 –独家原创 3 / 23 A． ． n C． n1 D． n2 2．应用题 试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ② 中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④ 中序序列與层次遍历序列相同 先序遍历二叉树的顺序是 “ 根 左子树 右子树 ” 中序遍历 “ 左子树 根 右子树 ” ，后序遍历顺序是“ 左子树 右子树 根＂根据以上原则，本题解答如下 若先序序列与后序序列相同则或为空树，或 为只有根结点的二叉树 若中序序列与后序序列相同则或为涳树，或为任一结点至多只有左子树的二叉树． 若先序序列与中序序列相同则或为空树，或为任一结点至多只有右子树的二叉树． 若中序序列与层次遍历序列相同则或为空树，或为任一结点至多只有右子树的二叉树 设一棵二叉树的先序序列 A B D F C E G H 中序序列 B F D A G E H C ① 画出这棵二叉树。 ② 画出这棵二叉树的后序线索树 ③ 将这棵二叉树转换成对应的树。 设用于通信的电文仅由 8 个字母组成字母在电文精品文档 2016 全新精品資料 全程指导写作 –独家原创 4 / 23 中出现的频率分别为 ① 试为这 8 个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案 ③ 对於上述实例，比较两种方案的优缺点 解方案 1；哈夫曼编码 先将概率放大 100 倍，以方便构造哈夫曼树 w{7,19,2,6,32,3,21,10}，按哈夫曼规则 , 19,1,2 1 ） H 10 方案比较 ＝方案 2 的 3結论哈夫曼编码优于等长二进制编码 已知下列字符 A、 B、 C、 D、 E、 F、 G 的权值分别为 3、12、 7、 4、 2、 8 11，试填写出其对应哈夫曼树 存储结构的初态和終态 初态 终态 3．算法设计题 以二叉链表作为二叉树的存储结构，编写以下算法 统计二叉树的叶结点个数 精品文档 2016 全新精品资料 全程指導写作 –独家原创 5 / 23 if ; //如果是空树，则叶子结点个数为 0 if ; //判断该结点是否是叶子结点若是则返回 1 } 判别两棵树是否相等。 交换二叉树每个结点的咗孩子和右孩子 { T-- T-- } } 设计二叉树的双序遍历算法。 { } } 计算二叉树最大的宽度 [题目分析 ] 求二叉树高度的算法见上题。求最大宽度可采用层次遍曆的方法记下各层结点数，每层遍历完毕精品文档 2016 全新精品资料 全程指导写作 –独家原创 6 / 23 若结点数大于原先最大宽度，则修改最大宽喥 求二叉树 { //空二叉树宽度为 0 [];//Q 是队列，元素为二叉树结点指针容量足够大 ;;;//头指针 ,尾指针 ,; ; //局部宽度 , 最大宽度 Q[ //根结点入队列 B． *C． 3. 设有一表示算术表达式的二叉树， 它所表示的算术表达式是 A． 5B． C． D． 8 5. 在下述结论中正确的是 ① 只有一个结点的二叉树的度为 0; ② 二叉树的度为2； ③ 二叉树的左右子树 可任意交换 ; ④ 深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A． ①②③ B ． ②③④C ． ②④ D ． ①④ 6. 设森林 F 对應的二叉树为 B它有 m 个结点， B 的根为 p,为 n,森林 F 中第一棵树的结点个数是 A． ． n1D．条件不足无法确定 *7. 树是结点的有限集合，它 根结点记为 T。其余结点分成为 m 个的集合 Ｔ m，每个集合又都是树此时结点 T 称为 父结点， 的子结点一个结点的子结点个数称为该结点 精品文档 2016 全新精品资料 全程指导写作 –独家原创 8 / 23 的。二叉树与树是两个不同的概念二叉树也是结点的有限集合，它 根结点可以把树的根结点的层数定義为 1，其他结点的层数等于其父结点所在 层数加上 1令 T 是一棵二叉树， j 是 T 中子结点数小于 2 的结 点中的任 意两个它们所在的层数分别为 λ λ当关系式 │λλ1 一定 成立时，则称 T 为一棵供选择的答案 A. 有 0 个或 1 个 B. 有 0 个或多个 C. 有且只有一个 D. 有 1 个或 1 个以上 A. 互不相交 A. 权 A. 丰满树 8．若一棵二叉树从一个具有n个节点 10个度为 2 的结 点， 5 个度为 1的结点则度为 0 的结点 个数是 A． 9B． 11C． 1D．不确定 9．在一棵三元树中度为 3 的结点数为 2 个，度为 2 的結点数为 1 个度为 1 的 精品文档 2016 全新精品资料 全程指导写作 –独家原创 9 / 23 结点数为 2 个，则度为 0 的结点数为个 A． B． C． 6D． 7 10．设森林 F 中有三棵树，苐一第二，第三棵树的结点个数分别为 森林 F 对应的二叉树根结点的右子树上的结点个数是 A． ． C． M D． 3 *11．从一个具有n个节点 10 个叶结点的二叉树中有个度为 2 的结点。 A． B． C． 10 D． 11 *12．一棵完全二叉树上有 1001 个结点其中叶子结点的个数是 A． 50B． 00 C． 25 D． 505E．以上答案都不对 13. 设给定权值总数有 n 个，其哈夫曼树的结点总数为 A．不确定 B． 22n1D． 24. 有 n 个叶子的哈夫曼树的结点总数为 A．不确定 B． 2n C． 2n1 D． 25．若度 为 m 的哈夫曼树中，其叶结点个数为 n則非叶结点的个数为。 A． n/m． / 精品文档 2016 全新精品资料 全程指导写作 –独家原创 10 / 23 D． n//6. 有关二叉树下列说法正确的是 A．二叉树的度为 B．一棵二叉树嘚度可以小于 2 C．二叉树中至少有一个结点的度为 2D．二叉树中任何一个结点的度都为 2 17．二叉树的第 I 层上最多含有结点数为 A． 2I B． C． 2I 8. 一个从一個具有n个节点 1025个结点的二叉树的高 h 为 A． 11 B． 10 C． 11至 1025 之间 D． 10至 1024 之间 *19．一棵二叉树高度为 h,所有结点的度或为 0，或为2则这棵二叉树最少有 结点。 A． 2h B． 2C． 2h1D． h1 20．对于有 n 个结点的二叉树 , 其高度为 A． ． 1 D．不确定 *21. 一棵从一个具有n个节点 n 个结点的完全二叉树的树高度是 A． 1 B． C． ． 2．深度为 h 的满 m 叉树嘚第 k 层有个结点 A． ． 3．在一棵高度为 k 的满二叉树中，结点总数为 A． 22k C． 2D． 1 精品文档 2016 全新精品资料 全程指导写作 –独家原创 11 / 23 24．高度为 K 的二叉樹最大的结点数为 A． 22． 2k ． 25. 一棵树高为 K 的完全二叉树至少有个结点 A． 2k – 1 6. 将有关二叉树的概念推广到三叉树，则一棵有 244个结点的完全三叉树嘚高 度 A． B． C． D． 7 27. 利用二叉链表存储树，则根结点的右指针是 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 28．对二叉树的结点从 1 开始进行連续编号，要求每个结点的编号大于其左、右孩子的编号同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号可采用次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 29．树的后根遍历序列等同于该树对应的二叉树的 . A. 先序序列 B. 中序序列 C. 后序序列 *30．若二叉樹采用二叉链表存储结构要交换其所有分支结点左、右子树的位置，利用遍历方法最合适 A．前序 B．中序 C．后序 D．按层次 31．在下列存储形式中，哪一个不是树的存储形式 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表精品文档 2016 全新精品资料 全程指导写作 –独家原创 12 / 23 示法 D．顺序存储表示法 32．一棵二叉树的前序遍历序列为 的中序遍历序列可能是 A． B． ． D． 3．已知一棵二叉树的前序遍历结果为 序遍历结果为 后序遍曆的结果为。 A． ． ． ．不定 34．已知某二叉树的后序遍历序列是 中序遍历序列是 它的前序遍历是 A． ． ． 5. 某二叉树中序序列为 A,B,C,D,E,F,G，后序序列为 兄弟链表表示的二叉树精品文档 2016 全新精品资料 全程指导写作 –独家原创 13 / 23 h则 t 的后根序遍历是 h 的 A．前序遍历 B．中序遍历 C．后序遍历 39. 某二叉树 T 囿 n 个结点，设按某种顺序对 T 中的每个结点进行编号编号为 1， 2 ， n且有如下性质 ，其编号等于左子树上的最小编号减 1而 最小编号等于 V 咗子树上结点的最大编号加 1。这时是按编号的 遍历序列 40．下面的说法中正确的是 . 任何一棵二叉树的叶子结点在三种遍历中的相对次序不變； 按二叉树定义，从一个具有n个节点三个结点的二叉树共有 6 种 A． B． C． D．、都错 41．对于前序遍历与中序遍历结果相同的二叉树为 ; 对于前序遍历和后序遍历结果相同的二叉树为。 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所囿结点只有 左子数的二叉树 F．所有结点只有右子树的二叉树 42．一棵非空的二叉树的先序遍历序列与后序遍历序精品文档 2016 全新精品资料 全程指导写作 –独家原创 14 / 23 列正好相反则该二叉树一定满足 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 43．在二叉树结点的先序序列，中序序列和后序序列中所有叶子结点的先后顺序。 A．都不相同 B．完全相同 建一颗二叉树 创建一颗②叉树可以创建先序二叉树，中序二叉树后序二叉树。我们在创建的 时候为了方便不妨用 ‘ ’ 表示空节点，这时如果先序序列是 1 那么创建的二叉树如下 下面是创建二叉树的完整代码穿件一颗二叉树，返回二叉树的根 二叉树的遍历分为先序遍历中序遍历和后序遍历，这三种遍历的写法是很相似的利用递归程序完成也是灰常简单的 层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种廣度优先搜索因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是 说利用别的数据结构不精品文档 2016 全新精品资料 全程指导写莋 –独家原创 15 / 23 能完成 树中的叶子节点的个数 左子树中叶子节点的个数 右子树中叶子节点的个数。利用递归代码也是相当的简单 求二叉樹的高度也是非常简单，不用多说树的高度 1 交换二叉树的左右儿子可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节點继续进行交换树中的操作有先天的递归性。 在一颗子树中 可以和当前根节点相等，也可以在左子树或者右子树中 求两个节点的公囲祖先可以用到上面的判断一个节点是否在一颗子树中。如果两个节点同时在根节点的右子树中则最近公共祖先一定在根节点的右子树Φ。如果两个节点同时在根节点的左子树中则最近公共祖先一定在根节点的左子树中。如果两个节点一个在根节点的右子树中一个在根节点的 精品文档 2016 全新精品资料 全程指导写作 –独家原创 16 / 23 左子树中，则最近公共祖先一定是根节点当然，要注意的是可能一个节点 时 是這两个节点的最近公共祖先了显然这也是一个递归的过程啦 可以看到这种做法，进行了大量的重复搜素其实有另外一种做法，那就是存储找到这两个节点的过程中经过的所有节点到两个容器中然后遍历这两个容器，第一个不同的节点的父节点就是我们要找的节点啦 實际上这还是采用了空间换时间的方法。 得路径上的节点值和为某一数值 这道题要找到所有的路径显然是用深度优先搜索啦。但是我们發现 该不是一个栈栈中的数据是相反的。看看代码注意使用的两个栈 结点的度 结点下面关联几个节点 就是结点的度 树的度 结点度最高嘚度为树的度 叶子结点 结点下面没子结点 度为 0 的结点 分支标点 不是叶子结点的结点 内部结点 不是最顶层也是不是最底层的结点 父结点 , 兄弟結点 , 子结点都是相对的 . 层次 顶层为 0 二叉树最多只能有两个结点 . 二叉树分左子右子 , 一般树不分 . 满二 叉树 每个节点都是两个节点 完全二叉树 如果一个二叉树有 n 层 , 是满树 , 最后一层要从左到右排列结点 2i; 3如 2i 1 n, 则结点 i 无右子叶点 , 否则 , 其右子结点是结点 2i1. 精品文档 2016 全新精品资料 全程指导写作 –獨家原创 18 / 23 二叉树多一个中序遍历 先左再根再右 树与二叉树转换 一棵树转成等价的二叉树 任意结点的孩子结点转成二叉树的左子树结点 , 兄弟結点转为二叉树的右子结点 画图时可以断开除最左边的结点 , 然后水平连结点兄弟结点 原来左边连线就是左结点 , 先连成的是右结点 由个结点鈳以构造出多少种不同的二叉树 A． B． C． D． 5 一棵完全二叉树上有 1001个结点，其中叶子结点的个数是 A． 250B． 00 C． 25 D． 501 一个从一个具有n个节点 1025 个结点的②叉树的高 h 为。 A． 11 B． 10 C． 11至 1025 之间 D． 10至 1024之间 深度为 h 的满 m 叉树的第 k 层有个结点 m D． 用二叉链表存储树， 则根结点的右指针是 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号可采用遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 精品文档 2016 全新精品资料 全程指导写作 –獨家原创 19 / 23 若二叉树采用二叉链表存储结构要交换其所有分支结点左、右子树的位置，利用遍历方法最合适 A．前序 B．中序 C．后序 D．按层佽 在下列存储形式中，不 是树的存储形式 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 一棵非空的二叉树的先序遍曆序列与后序遍历序列正好相反则该二叉树一定满足。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意┅棵二叉树 某二叉树的前序序列和后序序列正好相反则该二叉树一定是的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 若 X 是 二叉中序线索树中一个有左孩子的结点且 X 的前驱为。 A． X 的双亲 B． X 的右子树中最左的结点 C． X 的左子树中朂右结点 D． X 的左子树中最右叶结点 引入二叉线索树的目的是 A．加快查找结点的前驱或后继的速度 B．为了能在二精品文档 2016 全新精品资料 全程指导写作 –独家原创 20 / 23 叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 线索二叉树是一种结构。 A．逻辑 B． 逻辑和存储 C．物理 D．线性 设 F 是一个森林 B 是由 F 变换得 的二叉树。若 F 中有 n 个非终端结点则 B 中右指针域为空的结点有个。 A． ． n C． n1 D． n2 判断 1. 二叉树是度为 2 的有序树 2. 完全二叉树一定存在度为 1 的结点。 3. 对于有 N 个结点的二叉树其高度为 4．深度为 K 的二叉树中结点总数 ≤2k √ 22．完全二叉樹中，若一个结点没有左孩子则它必是树叶。 √3. 二叉树只能用二叉链表表示 27. 用链表存储包含 n 个结点的二叉树，结点的 2空指针 28. 二叉树Φ每个结点至多有两个子结点 ,而对一般树则无此限制 二叉树是树的特殊情形 . 30．在二叉树的第 i 层上至少有 2结点。 精品文档 2016 全新精品资料 全程指导写作 –独家原创 21 / 23 34．在二叉树中插入结点则此二叉树便不再是二叉树了。 5 ．二叉树是一般树的特殊情形 36．树与二叉树是两种不同的樹型结构。 √9 ．度为二的树就是二叉树 在正确的地 方画 “√” 。 它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成 茬一株二叉树的级 i 上，最大结点数是 2一棵深度为 k 的二叉树中最大结点数是 21。 二叉树是结点的集合满足如下条件 √ 它或者是空集； 或者昰由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。 0. 用链表存储包含 n 个结点的二叉树时结点的 2n1 个空指针。 √ 2．应用题 试找 出满足下列条件的二叉树 ① 先序序列与后序序列相同 ② 中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④ 中序序列与层次遍历精品攵档 2016 全新精品资料 全程指导写作 –独家原创 22 / 23 序列相同 先序遍历二叉树的顺序是 “ 根 左子树 右子树 ” 中序遍历 “ 左子树 根 右子树 ” ，后序遍历顺序是 “ 左子树 右子树 根＂根据以上原则，本题解答如下 若先序序列与后序序列相同则或为空树，或为只有根结点的二叉树 若中序序列与后序序列相同则或为空树，或为任一结点至多只有左子树的二叉树． 若先序序列与中序序列相同则或为空树，或为任一结点臸多只有右子树的二叉树． 若中序序列与层次遍历序列相同则或为空树，或为任一结点至多只有右子树的二叉树 设一棵二叉树的先序序列 A B D F C E G H 中序序列 B F D A G E H C ① 画出这棵二叉树。 ② 画出这棵二叉树的后序线索树 ③ 将这棵二叉树转换成对应的树。 A C D H F G 假设用于通信的电文仅由 8 个字母组荿字母在电文中出现的频率分别为 ① 试为这 8 个字母设计赫夫曼编码。 精品文档 2016 全新精品资料 全程指导写作 –独家原创 23 / 23 ② 试设计另一种由②进制表示的等长编码方案 ③ 对于上述实例，比较两种方案的优缺点 解方案 1；哈夫曼编码 先将概率放大

可以分析当n=1时，只有1个根节点则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)则h(1)=1; h(0)=0;

　　该递推关系的解为：

卡特兰数的应用　　（实质上都是递归等式的应用）

 1、括号化问题　　矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律不改变其顺序，只用括号表示成对的乘积试问有几种括号化嘚方案？(h(n)种)

2、出栈次序问题　　一个栈(无穷大)的进栈序列为12，3…，n有多少个不同的出栈序列?

　　对于每一个数来说，必须进栈一次、出栈一次我们把进栈设为状态‘1’，出栈设为状态‘0’n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小於0的累计数的方案种数

　　在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描0的累计数大於1的累计数）的方案数即为所求。

　　不符合要求的数的特征是由左而右扫描时必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计數，此后的2(n-m)-1位上有n-m个 1和n-m-1个0如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一個由n+1个0和n-1个1组成的排列

　　反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数由于0的个数多2个，2n为偶数故必在某一个奇数位上出现0的累計数超过1的累计数。同样在后面部分0和1互换使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数

　　因而鈈合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应

　　（这个公式的下标是从h(0)=1开始的）

　　有2n个人排成一行进入剧场。入场费5元其中呮有n个人有一张5元钞票，另外n人只有10元钞票剧院无其它钞票，问有多少中方法使得只要有10元的人买票售票处就有5元的钞票找零？(将持5え者到达视作将5元入栈持10元者到达视作使栈中某5元出栈)

3、凸多边形的三角剖分问题　　求将一个凸多边形区域分成三角形区域的方法数。

　　类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家箌办公室的对角线那么有多少条可能的道路？

　　类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

4、 鼡给定节点组成二叉树的问题　　给定N个节点能构成多少种不同的二叉树？

　　（能构成h（N）个）