数据结构 第六章-树和二叉树.ppt

《数据结构 第六章-树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A线性结构B非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.6赫夫曼树及其应用6.6.1最优二叉树(赫夫曼树)6.6.2赫夫曼编码树形结构是一类重

2、要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGA6.1树的定义和基本术语树(Tree)是n(n>0)个结点的有限集合T，它满足如下条件：有且仅有一个称为根(Root)的结点。其余结点可划分为m(m>=0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树，并称其为根的子树(SubTree)。这是一个递归定义。有时n=0也称为空树。ACGT2DHIT3JMBELKT1F树的表示方法1）树

3、形图法2）嵌套集合法3）广义表形式4）凹入表示法(A(B,C(E,F),D(G)))ABCDEFGABCEFDGABDGEFC线性结构（一对一关系）树结构（一对多关系）第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个终端结点(无后继)其它数据元素              树中其它结点(一个前驱、一个后继)      (一个前驱、多个后继)树形结构和线性结构的比较树结构的基本术语结点(node)——表示树中的元素，包括数据元素及若干指向其子树的分支。结点的度(degree)——结点拥有的

4、子树数。叶子(leaf)或终端结点——度为0的结点。分支结点——度大于零的结点。树的度——树中所有结点的度的最大值。孩子(child)——结点的子树的根。双亲(parents)——孩子结点的上层结点。兄弟(sibling)——同一双亲的孩子。堂兄弟——其双亲在同一层的结点互为堂兄弟。结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…。深度(depth)——树中结点的最大层次数。森林(forest)——m(m0)棵互不相交的树的集合。ABCDEFGHIJKLM树的抽象数据类型定义：ADT

5、Tree｛数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树;若D仅含一个数据元素，则R为空集，否则R＝｛H｝，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D－｛root｝≠Ф，则存在D－｛root｝的一个划分D1,D2,...,Dm（m＞0），对任意j≠k（1≤j,k≤m）有Dj∩Dk=φ，且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di，有∈H;（3）对应于D－｛root｝的划分，H－｛

6、>，....，｝有唯一的一个划分H1,H2,...,Hm（m＞0），对任意j≠k（1≤j,k≤m）有Hj∩Hk=Ф，且对任意的i（1≤i≤m），Hi是Di上的二元关系，（Di,{Hi}）是一棵符合本定义的树，称为根root的子树。树的抽象数据类型定义--基本操作（之一）InitTree(&T)；操作结果：构造空树T。DestroyTree(&T)；初始条件：树T存在。操作结果：销毁树T。CreateTree(&T，definition)；初始条件：definition给出树T的定义。操作结果

7、：按definition构造树T。ClearTree(&T)；初始条件：树T存在。操作结果：将树T清为空树。树的抽象数据类型定义--基本操作（之二）TreeEmpty(T)初始条件：树T存在。操作结果：若T为空树，则返回TURE，否则FALSE。TreeDepth(T)初始条件：树T存在。操作结果：返回T的深度。Root(T)初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。树的抽象数据类型定义--基本操作（之三

8、）Assign(T，cur_e，value)初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。Parent(T，cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T，cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点