数据结构树和二叉树

《数据结构树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.1树的定义和基本术语1.树的逻辑定义是由n(n≥0)个结点组成的有限集合T。在任意一个非空树中：有且仅有一个特定的称为根的结点；n>1时，其余结点可以分为m（m>0）个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，且称为根的子树。树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它说明了树的特性。如在右图中，是只有一个根结点的树是有13个结

2、点的树其中A是根，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M}；T1,T2,T3都是A的子树，且本身也是一棵树。则同理按此分析方式分析T1,T2,T3。AABCDEFGHIJKLM2.树的其它表示方法嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。广义表表示：根作为由子树森林组成的表的名字写在表的左边。凹入表示：类似书的编目。GCABDHIJEKFLA*****************B*****

3、***********E***************F***************K**************L**************C****************G***************D****************H***************I***************J***************(A(B(E,F(K,L)),C(G),D(H,I,J)))ABCDEFGHIJKL3.树的基本术语结点：数据元素+若干指向其子树的分支；结点的度：结点拥有的子树数；

4、树的度：树中所有结点的度的最大值；叶子结点：度为零的结点，或称为终端结点；分支结点：度大于零的结点，或称为非终端结点；结点的层次：假设根结点的层次为1,若某结点在第i层，则其子树的根在第i+1层；ABDEFHIJKM树的深度：树中叶子结点所在的最大层次；孩子结点：结点的子树的根；相应地该结点称为孩子的双亲结点；兄弟结点：同一个双亲的孩子之间称为兄弟结点；祖先：从根到该结点所经分支上的所有结点；子孙：子树中任一结点；ABDEFHIJKM3.树的基本术语有序树、无序树子树之间是否存在次序关系？将树中结点的各

5、子树看成从左至右是有次序的(即不能互换)称有序树，否则称无序树；森林：是m（m≥0）棵互不相交的树的集合。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林；ABDEFHIJKM3.树的基本术语4.树结构和线性结构的比较第一个数据元素（无前驱）最后一个数据元素（无后继）其它元素（一个前驱、一个后继）根结点（无前驱）多个叶子结点（无后继）其它结点（一个前驱、多个后继）线性结构树结构5.树的抽象类型定义ADTList{数据对象D：是具有相同特性的数据元素的集合数

6、据关系R：数据关系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；5.树的抽象类型定义ADTList{数据关系R：(3)对应于D-{root}的划分，H-{

7、，x1>，…，}有唯一的一个划分H1，H2，…，Hm(m>0)，对任意j≠k(1≤j，k≤m)有Hj∩Hk=Φ，对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di，{Hi})是一棵符合本定义的子树，称为根root的子树。基本操作：}ADTList树的基本操作1）Root(T);初始条件：树T存在；操作结果：返回T的根2）Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：返回cur_e的值3）Parent(T,cur_e);初始条件：树T存在，cur

8、_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则其函数值为“空”。4）TreeDepth(T);初始条件：树T存在；操作结果：返回T的深度。5）LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则其函数值为“空”6）RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cu