数据结构 第六章 树和二叉树

第六章树一．名词解释：1 树 2。

结点的度 3。

叶子 4。

分支点 5。

树的度6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树21 哈夫曼树二、填空题1、树（及一切树形结构）是一种“________”结构。

在树上，________结点没有直接前趋。

对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2、一棵树上的任何结点（不包括根本身）称为根的________。

若B是A的子孙，则称A是B的________3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。

4、二叉树第i(i>=1)层上至多有______个结点。

5、深度为k(k>=1)的二叉树至多有______个结点。

6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。

满二叉树也是______二叉树，但反之不然。

8、具有n个结点的完全二叉树的深度为______。

9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。

（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。

（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。

10.二叉树通常有______存储结构和______存储结构两类存储结构。

11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。

《数据结构》期末复习题及参考答案 - 第6章 树和二叉树一、 选择题1、在二叉树的第I 层(I≥1)上最多含有结点数为（ ）A. 2IB. 2I-1-1C. 2I-1D. 2I -12、深度为6的二叉树最多有( )个结点A ．64 B.63 C.32 D.313、一棵树高为K 的完全二叉树至少有( )个结点A.2k –1B.2k-1 –1C.2k-1D.2 k4、有关二叉树下列说法正确的是（ ）A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为25、n 个结点的线索二叉树上含有的线索数为（ ）A. 2nB. n －lC. n ＋lD. n6、线性表和树的结构区别在于（ ）A ．前驱数量不同，后继数量相同B ．前驱数量相同，后继数量不同C ．前驱和后继的数量都相同D ．前驱和后继的数量都不同7、已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，则其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE8、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)9、一棵具有 n 个结点的完全二叉树的树高度（深度）(符号⎣⎦x 表示取不大于x 的最大整数)是（ ）10、利用二叉链表存储树，则根结点的右指针是（）。

11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。

12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。

G
说明 1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2; 2）左、右子树不能颠例——有序树; 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;
结束
第 16 页
6.2 二 叉 树
A B D G (a) E C F F C
A B D G (b) E
(a)、(b)是不同的二叉树， (a)的左子树有四个结点， (b)的左子树有两个结点，
结束
第 17 页
6.2 二 叉 树
2． 二叉树的基本形态
φ
结束
第 18 页
6.2 二 叉 树
3．应用举例 例1 可以用二叉树表示表达式
+ a * /
e
f
b
c
d
a+b*(c-d)-e/f
结束
ห้องสมุดไป่ตู้
第 19 页
6.2 二 叉 树
例2 双人比赛的所有可能的结局
开始
甲
开局连赢两局 或五局三胜
乙
甲
甲 甲 乙
乙
对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事 二叉树是非线性结构，每个结点可能有两个后继，如 何访问二叉树的每个结点，而且每个结点仅被访问一次？
结束
第 32 页
6.3
一 二叉树的遍历方法
二叉树的遍历
二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树 令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： DLR，LDR，LRD，
3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一条从根到该结点的路径； 5）树是一种分枝结构

i 1 k ( 第 i 层的最大结点数 ) 2 2 1 i 1 i 1 k k
K
L
M
任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林

6.2 二叉树
定义
定义：二叉树是n(n0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子树 的互不相交的二叉树构成 二叉树，度为2的树? 特点
树和二叉树
树是一类重要的非线性数据结构，以分支 关系描述数据元素之间的层次结构 6.1 树 定义: 树(tree)是n(n≥0)个结点的有限集。在任意一棵非
空树中：
有且仅有一个特殊的结点，称为树的根结点(root)
当n>1时，除根结点之外的其余结点可分为
m(m>0)个 互不相交的有限集合T1,T2,……Tm，其 中每一个集合本身又是一棵树，称为根的子树 (subtree)
证明：用归纳法证明之 i=1时，只有一个根结点，2i-1 = 20 = 1； 假设对所有j(1j<i)命题成立，即第j层上至多有2j-1 个结 点,那么，第i-1层至多有2i-2个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即2i-2 2 = 2i-1 故命题得证 k 性质2：深度为k的二叉树至多有 2 1 个结点(k1) 证明：由性质1，可得深度为k 的二叉树最大结点数是
基本操作 P ：
插入类：
InitTree(&T) // 初始化臵空树 CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为 结点p的第i棵子树