第六章树与二叉树ppt课件.ppt

《第六章树与二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前面讨论的数据结构都属于线性结构，而实际中的许多问题若采用非线性结构来表示会显得更加明确和方便。所谓非线性结构是指在该类结构中至少存在一个数据元素，它具有两个或两个以上的前驱或后继。树形结构就是其中一类十分重要的非线性结构，它可以用来描述客观世界中广泛存在的、呈现层次结构的关系。如：家庭、行政区（国家-省-县-区）、社会机构（公司-处-科室）、物种分类（门-纲-类-科-目-种）、书籍目录（书-章-节-小节）……第6章树和二叉树本章中主要介绍下列内容：树的逻辑定义和存储结构二叉树的逻辑定义、存储结构二叉树的基本操作算法树和二叉树的转换哈夫曼树及其应用6.1

2、树6.1.1树的定义和基本运算1.定义树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，在任意一棵非空树中：（1）有且仅有一个特定的结点被称为根，（2）当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，其中每个子集又是一棵树。由此可以看出，树的定义是递归。如下图：KLMEFGHIJBCDAA(a)(b)(c)空树为只有一个根结点的树一般的树。下面是对“一般的树”的分析是有13个结点的树。其中A是根。其余结点分成三个互不相交的子集：T1={B，E，F，K，L}T2={C

3、，G}T3={D，H，I，J，M}T1，T2，T3都是根A的子树，且本身也是一棵树。如T1：T1的根为B，其余结点分为两个互不相交的子集：T11={E}，T12={F，K，L}。T11和T12都是B的子树。1.1、树在具体应用中的几种不同表现形式，它们各自适应于不同的场合。（1）树形。（2）文氏图。是以嵌套集合的形式表示的。所谓嵌套集合，是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。B（3）凹入表：类似书的编目。（4）嵌套括号：是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。表示方法的多样性，正说明了树结构在

4、日常生活及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可导致一个树结构。（A（B（E，F（K，L）），（（G），D（H（M），I，J）））1.2、树的逻辑结构：对于树，更常见的一种逻辑表示方法是给出树中元素的集合以及这个集合上的关系。如上例可描述为：T=（N，R），其中：结点集合N={A,B,D,E,F,G,H,I,J,K,L,M}N上的关系R={,,,,,,,,,,,}1.3、基本术语：结点数

5、据元素的内容及其指向其子树根的分支统称为结点。结点的度结点的分支数。终端结点（叶子）度为0的结点。非终端结点（分支结点）度不为0的结点。结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度树中所有结点度的最大值。树的深度树中所有结点层次的最大值。有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子、双亲结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。子孙以某结点为根的子树中

6、的所有结点都被称为是该结点的子孙。祖先从根结点到该结点路径上的所有结点。兄弟同一个双亲的孩子之间互为兄弟。堂兄弟双亲在同一层的结点互为堂兄弟。2.树的基本运算（1）从树的定义可知，每棵树是由一个根和若干棵子树形式，并且子树的棵数不是固定的，所以，其操作要比线性结构复杂得多。（2）树的应用广泛，在不同的软件系统中树的基本操作集不尽相同。常用操作：（1）构造一个空树InitTree(T)（2）将树T清为空树ClearTree(T)（3）判断树是否为空TreeEmpty(T)（4）获取给定结点的第i个孩子Child(T,cur_e,i)（5）获取给定结点的双亲

7、Parent(T,cur_e)（6）遍历树Traverse(T)：访问每个结点一次且仅一次。对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历方法有两种，一种是按深度方向遍历（先根、中根、后根）；另一种是按宽度方向遍历。另外还有如下常用操作：1.DestroyTree(T)销毁树T2.CreatTree(T,definition)按定义definition构造树3.TreeDepth(T)返回树T的深度4.Root(T)返回树T的根5.Value(T,cur_e)返回树中结点cur_e的值6.Assign(T,cur_e,v

8、alue)将树中结点cur_e赋值为value7.LeftChild(T,cur