当前位置:首页 >> 学科竞赛 >> 树




? ? ? ?

树的基本概念和表示 二叉树 遍历二叉树 哈夫曼树

4.1树的基本概念及表示
1.树的定义
树是由 D ( D≥0 )个结点组成的有限集合。若 D=0 ,称为空树;若 D>0,则: (1)有一个特定的称为根(root)的结点。它只有直接后继,但没 有直接前驱; (2

)除根结点以外的其它结点可以划分为 m(m≥0)个互不相交的 有限集合T0,T1,…,Tm-1,每个集合Ti(i=0,1,…,m-1)又是一棵树, 称为根的子树,每棵子树的根结点有且仅有一个直接前驱,但可以 有0个或多个直接后继。 由此可知,树的定义是一个递归的定义,即树的定义中又用到了树 的概念。 树的结构参见图4-1。

A B C F G H
D

E

I

L K (a)空树 (b)仅含有根结点的树 (c) 含有多个结点的树

?

A

J

M

图4-1 树的示意图

在图4-1(c)中,树的根结点为A,该树还可以分为三个互不相交子集T0,

T1,T2,具体请参见图4-2,其中T0={B,E,F,J,K,L},T1={C,
G},T2={D,H,I,M},其中的T0,T1,T2都是树,称为图4-1(C) 中树的子树,而T0,T1,T2又可以分解成若干棵不相交子树。如T0可以 分解成T00,T01两个不相交子集,T00={E,J,K,L},T01={F},而 T00又可以分为三个不相交子集T000,T001,T002,其中,T000={J}, T001={K},T002={L}。

? 2.相关定义
1)结点

指树中的一个数据元素,一般用一个字母表示。具有同一个双 亲的结点,称为兄弟结点。 节点的前驱称为父节点,节点的 后继称为子节点。不再有后继的节点称为树叶
2)度 节点的度:一个结点包含子树的数目,称为该结点的度。 树的度:树中结点度的最大值称为树的度。

3)树的高度(深度) 树中结点所处的最大层数称为树的高度,如空树的高度为 0 , 只有一个根结点的树高度为1。

4)层数 根结点的层数为1,其它结点的层数为从根结点到该结点所经过 的分支数目再加1。 5)有序树 若一棵树中所有子树从左到右的排序是有顺序的,不能颠倒次 序。称该树为有序树。

6)无序树 若一棵树中所有子树的次序无关紧要,则称为无序树。

7)森林(树林)

若干棵互不相交的树组成的集合为森林。一棵树可以 看成是一个特殊的森林。

3.树的表示
树的二种表示方法 1)树形图(如图4—1所示) 2)广义表 按照“根——左——右”的规律将树中的节点分别放入括号之中。具体 做法 是:在一对括号中先写根节点,在根节点后面的一对括号内按从左到右 的顺序写各个子树,同层子树用逗号隔开。对图4-1(c)的树结构,广 义表表示法可表示为: A (A(B(E(J,K,L),F),C(G),D(H(M),I)))
B C F G H
D

E

I

L K (a)空树 (b)仅含有根结点的树 (c) 含有多个结点的树

?

A

J

M

图4-1 树的示意图

练一练
如下图所示:用广义表表示,并指出它的度和深度

(A(B(E,F(K,L)),C(G),D(H,I,J(M)))) 深度:4 度:3

4.2二叉树
1)二叉树的定义
和树结构定义类似,二叉树的定义也可以递归形式给出:

二叉树是D(D≥0)个结点的有限集,它或者是空集(D=0),或 者由一个根结点及两棵不相交的左子树和右子树组成。
二叉树的特点是每个结点最多有两个孩子,或者说,在二叉树中, 不存在度大于2的结点,并且二叉树是有序树(树为无序树),其 子树的顺序不能颠倒,因此,二叉树有五种不同的形态,参见图 4-5 。

? (a)

L

R

L

R

(b) (c) (d) 图 4-5 二叉树的五种不同的形态

(e)

4.2.2 二叉树的性质
性质1 若二叉树的层数从1开始,则二叉树的第k层结点数,最多为 2k-1个(k>0)。

可以用数学归纳法证明之。
性质2 深度(高度)为k的二叉树最大结点数为2k-1(k>0)。 证明: 深度为k的二叉树,若要求结点数最多,则必须每一层的 结点数都为最多,由性质1可知,最大结点数应为每一层最大结 点数之和。既为 20+21+…+2k-1=2k-1。

性质3 对任意一棵二叉树,如果叶子结点个数为D0,度为2的 结点个数为D2,则有D0=D2+1。
证明:设二叉树中度为1的结点个数为D1,根据二叉树的定义可 知,该二叉树的结点数D=D0+D1+D2。又因为在二叉树中,度为0 的结点没有孩子,度为1的结点有1 个孩子,度为2的结点有2个结 孩子,故该二叉树的孩子结点数为 D0*0+D1*1+D2*2 ,而一棵二 叉树中,除根结点外所有都为孩子 结点,故该二叉树的结点数应 为孩子结点数加1即:D=D0*0+D1*1+D2*2+1因此,有 D=D0+D1+D2=D0*0+D1*1+D2*2+1,最后得到D0=D2+1。

满二叉树 深度为k具有2k-1个结点的二叉树,称为满二叉树。 从上面满二叉树定义可知,必须是二叉树的每一层上的结点数都 达到最大,否则就不是满二叉树。

完全二叉树 如果一棵具有D个结点的深度为k的二叉树,它的每一 个结点都与深度为k的满二叉树中编号为1~ D的结点一一对应,则 称这棵二叉树为完全二叉树。 从完全二叉树定义可知,结点的排列顺序遵循从上到下、从左到 右的规律。所谓从上到下,表示本层结点数达到最大后,才能放 入下一层。从左到右,表示同一层结点必须按从左到右排列,若 左边空一个位置时不能将结点放入右边。

从满二叉树及完全二叉树定义还可以知道,满二叉树一定是一棵 完全二叉树,反之完全二叉树不一定是一棵满二叉树。满二叉树 的叶子结点全部在最底层,而完全二叉树的叶子结点可以分布在 最下面两层。深度为4的满二叉树和完全二叉树如图4-6所示。

A B C E I J K L F
M

A B G N
O D

C E F G

D

H

H

(a)满二叉树 (b)完全二叉树 图 4-6 满二叉树和完全二叉树示意图

性质4 具有D个结点的完全二叉树高度为?log2(D)?+1 或 ?log2 (D+1)? 。
(注意?x?表示取不大于x的最大整数,也叫做对x下取整) 证明:设该完全二叉树高度为 k,则该二叉树的前面k-1层为满二叉 树,共有2k-1-1 个结点,而该二叉具有k层,第k层至少至少有 1 个结 点,最多有2k-1个结点。因此有下面的不等式成立: (2k-1 –1) +1 ≤D ≤(2k-1-1)+2k-1,即有 2k-1≤D≤2k-1。由式子后半部分可知, D≤2k-1…① 由式子前半部分可知 2k-1≤D…② 由①有 D+1≤2k ,同时取对数得: log2(D+1)≤k 故 k≥log2(D+1),即 k=?log2(D+1)?。即得到第二个结论。

由②有2k-1≤D,同时取对数得:k≤log2D+1即 k=?log2 D?+1,即第一个结 论成立,证毕。

4.3二叉树树的遍历
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做 一次且仅做一次访问。 从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这 三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三 个操作: ? ⑴访问结点本身(D), ? ⑵遍历该结点的左子树(L), ? ⑶遍历该结点的右子树(R) 以上三种操作有六种执行次序: DLR、LDR、LRD、DRL、RDL、RLD。
前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。

4.3.1前根遍历(DLR)
所谓前根遍历,就是根结点最先遍历,其次左子树,最后右 子树。

1.递归遍历 前根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则

(1)输出根结点;
(2)前根遍历左子树; (3)前根遍历右子树;

a
c b d e

f

(1)先访问根节点 a (2)前序遍历a的左子树(b,d,e,f) 先访问根节点 b; 前序遍历左子树d; 前序遍历右子树(e,f);为ef 前序遍历左子树的结果为bdef (3)前序遍历a的右子树c 所以左图二叉树遍历的结果为 abdefc

4.3.2中根遍历(LDR)
所谓中根遍历,就是左子树最先遍历,其次是根,最后右子 树。

1.递归遍历
中根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则

(1)中根遍历左子树;
(2)遍历根; (3)中根遍历右子树;

a
c b d e

(1)中序遍历a的左子树(dbfe) (2) 再访问根节点 a (3)中序遍历a的右子树c 所以左图二叉树遍历的结果为 dbfeac

f

4.3.3后根遍历(LRD)
所谓后根遍历,就是左子树最先遍历,其次是右子树根,最 后根。

1.递归遍历 后根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则

(1)后根遍历左子树;
(2)后根遍历右子树; (3)遍历根;

a
c b d e 请你后根遍历左图

f

dfebca

另外,在编译原理中,有用二叉 树来表示一个算术表达式的情形。 在一棵二叉树中,若用操作数代表树叶,运算符代表非叶子结点, 则这样的树可以代表一个算术表达式。若按前序、中序、后序对 该二叉树进行遍历,则得到的遍历序列分别称为前缀表达式(或称 波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图4-12。

图4-12所对应的前缀表达式: -*abc。 图 4-12 所 对应 的 中 缀 表 达 式 : a*b-c。 图4-12所对应的后缀表达式: ab*c-。
a * b

c

图 4-12 表达式 a*b-c 代表的二叉树

4.3.4遍历算法应用举例
例4-5 由二叉树的前序序列和中序序列建立该二叉树 分析:若二叉树的任意两个结点的值都不相同,则二叉树的前 序序列和中序序列能唯一确定一棵二叉树。另外,由前序序列 和中序序列的定义可知,前序序列中第一个结点必为根结点, 而在中序序列中,根结点刚好是左、右子树的分界点,因此, 可按如下方法建立二叉树:

1.在前序中找出根

2. 在中序序列中查找根结点的位置,并以此为界将中序序列 划分为左、右两个序列(左、右子树);

3.对左、右子树的前序序列和中序序列递归地实施同样方法,直 到所得左、右子树为空。 假设前序序列为ABDGHCEFI,中序序列为GDHBAECIF则得 到的二叉树如下页所示

A

1。A为根结点 A BDGH CEFI GDHB A ECIF

BD GH

CE FI

2. B为左子树的根结点 B DGH GDH B 3. D为左子树的左子树的根结点
DH G

A B

CE FI

A B D G H

CE FI

4。C为右子树的根结点
C E E C FI
B D G H A C E FI

IF

5。F为右子树的右 子树的根结点
D G

A B E H I C F

4.4 哈夫曼树
1.基本术语
1)路径和路径长度

在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通 路,称为路径。通路中分支的数目称为路径长度。
若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L1。 2)结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结 点的权。 结点的带权路径长度为:从根结点到该结点之间的路径长度与该结 点的权的乘积。

3)树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记 n 为wpl= ? wi,其中 D 为叶子结点数目,wi为第i 个叶子结点的权 li i ?1i 个叶子结点的路径长度。 值,li 为第

4.4.2 哈夫曼树构造
1.哈夫曼树的定义 在一棵二叉树中,若带权路径长度达到最小,称这样的二叉 树为最优二叉树,也称为哈夫曼树(HuffmaD tree)。

(1) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树 的左、右子树,且新树的根结点权值为其左、右子树根结点权值 之和; (2)从森林中删除选取的两棵树,并将新树加入森林; (3)重复(1)、(2)步,直到森林中只剩一棵树为止,该树即为我们所 求得的哈夫曼树。 下面给出哈夫曼树的构造过程,假设给定的叶子结点的权分别为 1,5,7,3,则构造哈夫曼树过程如图4-29所示。 从图4-29可知,D 个权值构造哈夫曼树需D-1次合并,每次合并,森 林中的树数目减1,最后森林中只剩下一棵树,即为我们求得的哈夫 曼树。

1

5

7

3

5

7 1

4 3

(a) 初如森林

(b) 一次合并后的森林

7 4 1

9 5 3 1 7

16 9 4 3 5

(c) 二次合并后的森林

(d) 三合并后的森林

图 4-29 哈夫曼树的构造过程

练习
1.一个高度为H的二叉树最小元素数目是() (A)2h+1 (B)h (C)2h-1 (D)2h (E)2h 2.表达式(1+34)*5-56/7 的后缀表达式为( )。 A) 1+34*5-56/7 B) -*+1 34 5/56 7 C) 1 34 +5*56 7/- D) 1 34 5* +56 7/3.一棵二叉树的中序遍历序列为DGBAECHF,后 序遍历序列为:GDBEHFCA,则前序遍历的序列 是( )。 (A)ABCDFGHE (B) ABDGCEFH (C) ACBGDHEFD (D) CEFHBGD 4.求叶节点权值分别为2,2,3,3,5的最优二叉树, 并求出所有叶节点带权路径长度之和。

1.B

2C 3B

15 6

3

3

WPL=2*3+2*3+5*2+3*2+3*2 =34


更多相关文档:

pascal-树

pascal-_IT/计算机_专业资料。pascal-信息学奥赛之 数据结构―― 1 及其应用 ? 的定义是由 n (n >= 0)个结点组成的有限集合。如果 n = 0,...

树的尺寸大小

的尺寸大小: 大乔木高 20 米以上,冠尺寸 5—6m 孤植树冠尺寸 7—8m, 小乔木高 5~10 米,冠尺寸 3—5m, 花灌木高小于 5 米,冠尺寸 ...

四季的树

春天1、发芽的:杨、槐、柳、枣、 2、开花的:迎春花、玉兰、桃、杏、梨、李、樱花 3、结果的:枇杷、山茶、苦茶、樱桃、桃、...

读书报告之《树王》

读书报告之《王》_语文_高中教育_教育专区。关于阿城的王,文章部分内容是摘选得来。读书报告之《王》高一(2)班 于子豪 一.内容概要《王》是阿城的小说...

数据结构 树 考试习题

设有如图所示,则结点c的度为 ___ ,层次为 ___ ,的度为 ___,的高度为___。 为2, 的度为3,高度为4 结点c的度为2, 层次 7.深度为k的完...

常用花、树的英文单词

常用花、的英文单词_英语学习_外语学习_教育专区。rose 玫瑰花 凤仙花 tulip ['tju:lip] 郁金香 美人蕉 balsam ['b?:ls?m] ? lily 百合花 canna ['k?...

决策树分类的定义以及优缺点

决策分类的定义以及优缺点_数学_自然科学_专业资料。算法设计、数据挖掘的主要算法。决策分类决策( Decision Tree )又称为判定,是运用于分类的一种结构...

决策树

二、决策的学习决策的建构的主要步骤有三:第一是选择适当的算法训练样本建构决策 ,第二是适当的修剪决策,第三则是从决策中萃取知识规则。 (一)决策...

实验六、分类和回归树节点(C&RT)

实验报告 2、生成模型和节点以便评分 使用决策时,共有几个选项可用于生成或导出会话结果。其中两个常用 的选项为根据当前生成模型或根据当前生成选择节点。 ...

事件树分析法

事件分析法_经管营销_专业资料。事件分析(Event Tree Analysis,简称ETA)起源于决策分析(简称DTA),它是一种按事故发展的时间顺序由初始事件开始推论可能的后果...
更多相关标签:
树叶 | 树简笔画 | 树的图片 | 美人树 | 树的种类 | 猴面包树 | 面包树 | 枫树 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com