第6章 树型结构.ppt

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

1、第6章树数据结构（C描述）6.9二叉树的应用——哈夫曼树6.8树和森林6.7线索二叉树6.4遍历二叉树6.3二叉树的定义及存储结构6.1树的基本概念目录6.2树的存储结构6.5二叉排序树6.6平衡二叉树在许多领域许多问题不能或难用线性结构表示（哈夫曼编码、判定问题），故研究非线性的数据结构。树是一种应用十分广泛的非线性数据结构。6.1树的基本概念6.1.1树的定义树的定义树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则称为非空树，在任一棵非空树中：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可

2、以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，且每个集合Ti（i=0,1,…,m-1）本身又是一棵树，称为根的子树。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。从定义中看出树结构具有以下特点：（1）有且仅有一个结点没有直接前驱，即根结点。（2）除根结点之外，其余所有结点有且仅有一个直接前趋结点。（3）包括根结点在内，每个结点可以有多个直接后继结点。从此可见，树型结构的特点是，数据元素之间存在着一对多的关系。树的结构参见图6-1。在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中

3、T0={B，E，F，J，K，L}，T1={C，G}，T2={D，H，I，M}而T0，T1，T2又可以分解成若干棵不相交子树。如：T0可以分解成T00，T01两个不相交子集，T00={E，J，K，L}，T01={F}，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000={J}，T001={K}，T002={L}。6.1.2基本术语1.树的结点指树中的一个数据元素，一般用一个字母表示。2.结点的度一个结点包含子树的数目，称为该结点的度。3.树叶（叶子）度为0的结点，称为叶子结点或树叶，也叫终端结点。4.分支结点（非终端结点）除叶子结点外的所有结点，为分支

4、结点。通常又将除根结点之外的分支结点称为内部结点。6.双亲结点若结点X有子女Y，则X为Y的双亲结点。7.祖先结点8.子孙结点某一结点的子女的子女为该结点子孙。5.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子。如图6-1（c）中A的孩子为B，C，D。10．结点的层次从根结点开始定义，根为第一层，根的孩子为第二层，依次类推。11.树的高度（深度）树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.树的度树中结点度的最大值称为树的度。9.兄弟结点具有同一个双亲的结点，称为兄弟结点。13.有序树若一棵树中所有子树从左到右的排序是

5、有顺序的，不能颠倒次序。称该树为有序树。14.无序树若一棵树中所有子树的次序无关紧要，则称为无序树。15．森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。树与森林的关系6.1.3树的表示1．树形结构表示法（掌握）具体参见图6-1。2.凹入法表示法具体参见图6-33.嵌套集合表示法具体参见图6-4。4.广义表表示法对图7-1（c）的树结构，广义表表示法可表示为：A（B（E（J，K，L），F），C（G），D（H（M），I））6.2树的存储结构仅考虑链式存储结构，有两种：多重链表表示法、二重链表表示法6.2.1多重链表表示法每个结点由一个数据域和若干

6、个指针域组成，其中，每个指针域指向该结点的一个孩子。一棵树中不同结点的度数可能不同，每个结点设置的指针域的数目可能就有所不同。通常有下面的两种方案：1、定长结点的多重链表表示法取树的度数作为每个结点的指针域的个数。缺点：由于树中多数结点的度可能小于树的度，因而这种方法将会导致许多结点的部分指针域为空，造成空间的浪费。2、不定长结点的多重链表示法树中每个结点都取自己的度数作为指针域的个数，显然，对于叶结点就不必设指针域。另外，每个结点除了数据域、指针域外，还应设一个度数域用来指出该结点的度数，即指出该结点中指针域的个数。6.2.2二重链表表示法这种方法是对树中的每个结点设三个域

7、：数据域和2个指针域，第一个指针域给出该结点的第一个孩子（即最左边子树的根结点，长子）的地址，第二个指针域给出该结点的右边第一个兄弟结点（次弟）的地址。树的三重链表表示，增加了一个指针域即给出该结点的双亲结点的地址。6.3二叉树在树型结构中，有一类简单而又重要的树，它的每个结点最多只有2棵子树，这种树被称为二叉树。6.3.1二叉树的定义1．二叉树的定义和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树