数据结构二叉树遍历练习题

精品文档 2016 全新精品资料 全程指导写作 独家原创 1 / 23 数据结构二叉树遍历练习题 1选择题 把一棵树转换为二叉树后，这棵二叉树的形态是。 A唯一的 有多种 C有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子 由个结点可以构造出多少种不同的二叉树？ A B C D 5 一棵完全二叉树上有 1001个结点，其中叶子结点的个数是。 A 250B 00 C 25 D 501 一个具有 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 n+1 D n+2 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 /根结点入队列 p=Q; ; /同层元素数加 1 Q+p-+p-， if , 更新当前最大宽度 ; / 第六章 树和二叉树 一、选择题 1已知一算术表达式的中缀形式为 A+B*，后缀形式为 ，其前 缀形式为 A *C/B. * 精品文档 2016 全新精品资料 全程指导写作 独家原创 7 / 23 C -+*E D. -+A*E 2算术表达式 a+b*转为后缀表达式后为 A ab+ 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 n+1D条件不足，无法确定 *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若一棵二叉树具有 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具有 10 个叶结点的二叉树中有个度为 2 的结点。 A B C 10 D 11 *12一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是 A 50B 00 C 25 D 505E以上答案都不对 13. 设给定权值总数有 n 个，其哈夫曼树的结点总数为 A不确定 B 22n+1D 24. 有 n 个叶子的哈夫曼树的结点总数为。 A不确定 B 2n C 2n+1 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. 一个具有 1025个结点的二叉树的高 h 为 A 11 B 10 C 11至 1025 之间 D 10至 1024 之间 *19一棵二叉树高度为 h,所有结点的度或为 0，或为2，则这棵二叉树最少有 结点。 A 2h B 2C 2h+1D h+1 20对于有 n 个结点的二叉树 , 其高度为 A ?+1 D不确定 *21. 一棵具有 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，后序序列为 B,D,C,A,F,G,E 则前序序列是： A E,G,F,A,C,D, E,A,C,B,D,G,F C E,A,G,C,F,B,D D上面的都不对 36. 上题的二叉树对应的森林包括多少棵树 A C D概念上是错误的 37二叉树的先序遍历和中序遍历如下： 先序遍历：序遍历 : 该二叉树根的右 子树的根是： A、 G D、 H 38将一棵树 t 转换为孩子 兄弟链表表示的二叉树精品文档 2016 全新精品资料 全程指导写作 独家原创 13 / 23 h，则 t 的后根序遍历是 h 的 A前序遍历 B中序遍历 C后序遍历 39. 某二叉树 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，编号为 1， 2， ? ， n，且有如下性质： ，其编号等于左子树上的最小编号减 1，而 最小编号等于 V 左子树上结点的最大编号加 1。这时是按编号的。 遍历序列 40下面的说法中正确的是 . 任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； 按二叉树定义，具有三个结点的二叉树共有 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 层下面依次加一层 树的结点总数 =总度数 +1 精品文档 2016 全新精品资料 全程指导写作 独家原创 17 / 23 1 | 24 | 10 树的遍历 : 前序遍历 : 根 -最左子结点 -再最左边 后序遍历 : 先子节点 , 再根节点 层次遍历 : 是分层一个一个来 . 前 : 1, 10 后 :, 10, 1 层 : 1, 10 二叉树 : 二叉树最多只能有两个结点 . 二叉树分左子右子 , 一般树不分 . 满二 叉树 : 每个节点都是两个节点 完全二叉树 : 如果一个二叉树有 n 层 , 是满树 , 最后一层要从左到右排列结点 2i; 3)如 2i + 1 n, 则结点 i 无右子叶点 , 否则 , 其右子结点是结点 2i+1. 精品文档 2016 全新精品资料 全程指导写作 独家原创 18 / 23 二叉树多一个中序遍历 :先左再根再右 树与二叉树转换 :一棵树转成等价的二叉树 任意结点的孩子结点转成二叉树的左子树结点 , 兄弟结点转为二叉树的右子结点 画图时可以断开除最左边的结点 , 然后水平连结点兄弟结点 原来左边连线就是左结点 , 先连成的是右结点 由个结点可以构造出多少种不同的二叉树？ A B C D 5 一棵完全二叉树上有 1001个结点，其中叶子结点的个数是。 A 250B 00 C 25 D 501 一个具有 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 n+1 D n+2 判断 1. 二叉树是度为 2 的有序树。 2. 完全二叉树一定存在度为 1 的结点。 3. 对于有 N 个结点的二叉树，其高度为 4深度为 K 的二叉树中结点总数 2k 22完全二叉树中，若一个结点没有左孩子，则它必是树叶。 3. 二叉树只能用二叉链表表示。 27. 用链表存储包含 n 个结点的二叉树，结点的 2空指针。 28. 二叉树中每个结点至多有两个子结点 ,而对一般树则无此限制 二叉树是树的特殊情形 . 30在二叉树的第 i 层上至少有 2结点。 精品文档 2016 全新精品资料 全程指导写作 独家原创 21 / 23 34在二叉树中插入结点，则此二叉树便不再是二叉树了。 5 二叉树是一般树