[详细完整版]数据结构07.doc
版权申诉
73 浏览量
2022-07-11
13:42:42
上传
评论
收藏 53KB DOC 举报
数据结构 07
第七章 树和二叉树习题
7.1 画出由 4 个结点所构成的所有形态的树（假设是无序树）。
7.2 已知一棵树的度为 4，其中度为 4 的结点的数目为 3，度为 3 的结点的数目为 4，度
为 2 的结点的数目为 5，度为 1 的结点的数目为 2，请求出该树中的叶子结点的数目。
7.3 如果已知一棵二叉树有 20 个叶子结点，有 10 个结点仅有左孩子，15 个结点仅有右
孩子，求出该二叉树的结点数目。
7.4 已知某完全二叉树有 100 个结点，试用三种不同的方法求出该二叉树的叶子结点数。
7.5 如果已知完全二叉树的第 6 层有 5 个叶子，试画出所有满足这一条件的完全二叉树，
并指出结点数目最多的那棵完全二叉树的叶子结点数目。
7.6 在编号的完全二叉树中，判断编号为 i 和 j 的两个结点在同一层的条件是什么？
7.7 设计算法以求解编号为 i 和 j 的两个结点的最近的公共祖先结点的编号。
7.8 分别求出下图中二叉树的三种遍历序列。
○
A
○
A
○
A
○
A
○
B
○
G
○
B
○
B
○
B
○
C
○
E
○
H
○
I
○
C
○
C
○
C
○
D
○
F
○
J
○
D
○
D
○
D
○
E
○
E
○
E
7.9 分别描述满足下面条件的二叉树的特征：
（1）先序序列和中序序列相同。
（2）先序序列和后序序列相反。
7.10 证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两
个序列构造出相应的二叉树：
①先序：ABCDEFGHI ②先序：ABCDEFGHIJ
中序：ADECFBGIH 中序：BDECAGIJHF
7.11 证明：由二叉树的后序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两
个序列构造出相应的二叉树：
①后序：DCFEBIHGA ②后序：DECBGIHFA
中序：DCBFEAGHI 中序：DCEBAFHGI
7.12 已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构
造出该二叉树。
先序：A_CDEF_H_J
中序：C_EDA_GFI_
后序：C_ _BHGJI_ _
7.13 证明：任意一棵非空的二叉树的先序序列的最后一个结点一定是叶子结点。
7.14 用反例证明：由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。
7.15 设计算法以输出二叉树中先序序列的前 k（k>0）个结点的值。
7.16 设计算法按中序次序依次输出各结点的值及其对应的序号。例如，下图中的二叉
树的输出结果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I,9) (G,10)。
○
A
○
B
○
G
○
C
○
D
○
H
○
E
○
F
○
I
评论0
最新资源