数据结构--第6章 树

数据结构-习题-第六章-树和二叉树E F D G A B / + + * - C * 第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/EC ．-+*ABC/DE D. -+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ）【南京理工大学1999 一、20（2分）】A. A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D.A*B+C/D*E+F-G4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T。

其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。

6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。

如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。

(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。

结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。

4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。

它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。

因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。

例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。

b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。

ElemType data ; struct CSnode *firstchild, *nextsibing ; }CSNode;
6.4.1 树的存储结构
R AB C D EG F
R⋀
A
⋀D
⋀B
⋀E ⋀
C⋀
⋀G
⋀F ⋀
6.4.2 树、森林和二叉树的转换
1. 树转换为二叉树 将树转换成二叉树在“孩子兄弟表示法”中已 给出，其详细步骤是： ⑴ 加线。在树的所有相邻兄弟结点之间加一 条连线。 ⑵ 去连线。除最左的第一个子结点外，父结点 与所有其它子结点的连线都去掉。 ⑶ 旋转。将树以根结点为轴心，顺时针旋转 450，使之层次分明。
B C
D
A E
L HK
M
技巧：无左孩子 者即为叶子结点
6.4.3 树和森林的遍历
1. 树的遍历 由树结构的定义可知，树的遍历有二种方法。 ⑴ 先序遍历：先访问根结点，然后依次先序 遍历完每棵子树等。价于对应二叉树的先序遍历
⑵ 后序遍历：先依次后序遍历完每棵子树，然 后访问根结点。等价于对应二叉树的中序遍历
0 R -1 1A 0 2B 0 3C 0
}Ptree ; R
4D 1 5E 1
AB C
6F 3
7G 6
DE
F
8H 6
9I 6
G H I 10~MAX_Size-1 ... ...
6.4.1 树的存储结构
2. 孩子表示法
每个结点的孩子结点构成一个单链表，即有n 个结点就有n个孩子链表；
n个孩子的数据和n个孩子链表的头指针组成一 个顺序表； 结点结构定义： 顺序表定义：
typedef struct PTNode { ElemType data ;

第6章 树 例如，设有序表为(21, 25, 28, 33, 36, 43)，若要在表中 查找元素36，通常的做法是从表中第一个元素开始，将待查元素 与表中元素逐一比较进行查找，直到找到36为止。粗略地说，如 果表中每个元素的查找概率是相等的，则平均起来，成功查找一 个元素需要将该元素与表中一半元素作比较。如果将表中元素组 成图6－3所示的树形结构，情况就大为改观。我们可以从根结点 起，将各结点与待查元素比较，在查找成功的情况下，所需的最 多的比较次数是从根到待查元素的路径上遇到的结点数目。当表 的长度n很大时，使用图6－3所示的树形结构组织表中数据，可 以很大程度地减少查找所需的时间。为了查找36，我们可以让36 与根结点元素28比较，36比28大，接着查右子树，查找成功。显 然，采用树形结构能节省查找时间。
第6章 树
E
E
A
F
B
G
CD
LJ
M
N
T1
X
YZ
U T2
B
F
A
DC
G
JL
T3 N
M
(a)
(b)
图6－2 树的例子
(a) 树T1和T2组成森林；(b) 树T3
第6章 树
6.2 二 叉 树
二叉树是非常重要的树形数据结构。很多从实际问题中抽 象出来的数据都是二叉树形的，而且许多算法如果采用二叉树 形式解决则非常方便和高效。此外，以后我们将看到一般的树 或森林都可通过一个简单的转换得到与之相应的二叉树，从而 为树和森林的存储及运算的实现提供了有效方法。
第6章 树
图6－1描述了欧洲部分语言的谱系关系，它是一个后裔图， 图中使用的描述树形结构数据的形式为倒置的树形表示法。在 前几章中，我们学习了多种线性数据结构，但是一般来讲，这 些数据结构不适合表示如图6－1所示的层次结构的数据。为了 表示这类层次结构的数据，我们采用树形数据结构。在本章中 我们将学习多种不同特性的树形数据结构，如一般树、二叉树、 穿线二叉树、堆和哈夫曼树等。