数据结构.第6章.树和二叉树.1.基本概念和二叉树.pptx

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

1、数据结构DataStructures张凯计算机学院软件工程系2011年3月12日树和森林第6章树和二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用第6章树和二叉树第6章树和二叉树计算机学院材冶学院机械学院计算机科学系计算机技术系软件工程系……武汉科技大学网络工程系第6章树和二叉树第6章树和二叉树树的逻辑定义§6.1树的基本概念树是由n(n≥0)个结点组成的有限集合T。在任意一个非空树中：有且仅有一个特定的结点称为根(root)；n>1时，其余结点可以分为m(m>0)个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，且称为根的子树。注意：1.树

2、的定义具有递归性，即树中有树。2.n=0个结点时为空树。树的逻辑定义§6.1树的基本概念其中A是根结点，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M}T1,T2,T3都是A的子树，且本身也是一棵树。ABCDEFGHIJKLM右图是具有13个结点的树树的逻辑定义§6.1树的基本概念其中A是根结点，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M}T1,T2,T3都是A的子树，且本身也是一棵树。ABCDEFGHIJKLM右图是具有13个结点的树树的表示方法图形表示法(分支

3、图表示法)嵌套集合表示法广义表表示法目录表示法左孩子－右兄弟表示法§6.1树的基本概念图形表示法(分支图表示法)§6.1树的基本概念ABCDEFGHIJKL广义表表示法§6.1树的基本概念(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边嵌套集合表示法GCABDHIJEKFL§6.1树的基本概念嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。凹入表示法§6.1树的基本概念凹入表示：类似书的编目A*****************B***************E*************F*

4、************K***********L***********C***************G*************D***************H*************I*************J*************左孩子－右兄弟表示法§6.1树的基本概念ACDEFGHIJKLB左孩子－右兄弟表示法§6.1树的基本概念ABCDEFGHIJKL树的基本术语§6.1树的基本概念——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的

5、所有结点——即该结点下层子树中的任一结点根叶子森林——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。有序树无序树树的基本术语§6.1树的基本概念——即树的数据元素——结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点结点的度树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（M

6、ax{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝结点的层次终端结点分支结点1334树结构和线性结构的比较§6.1树的基本概念第一个数据元素（无前驱）最后一个数据元素（无后继）其它元素（一个前驱、一个后继）根结点（无前驱）多个叶子结点（无后继）其它结点（一个前驱、多个后继）线性结构树结构树的抽象类型定义§6.1树的基本概念ADTTree{数据对象D：是具有相同特性的数据元素的集合数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}

7、!=Φ，则存在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-{，…，}有唯一的一个划分H1，H2，…，Hm(m>0)，对任意j≠k(1≤j，k≤m)，有Hj∩Hk=Φ，对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di,{Hi