数据结构 叶乃文 郑晓红 第五章

《数据结构 叶乃文 郑晓红 第五章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章树和二叉树本章中主要介绍下列内容：树的逻辑定义和存储结构二叉树的逻辑定义、存储结构二叉树的基本操作算法树和二叉树的转换哈夫曼树及其应用退出5.1树5.2二叉树5.3哈夫曼树及其应用5.1树5.1.1树的定义和基本运算1.定义树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。图5-1KLMEFGHIJBCDAA(a)(b)(c)结点数据元素的内容及其指向其子树根

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

3、点。兄弟同一个双亲的孩子之间互为兄弟。堂兄弟双亲在同一层的结点互为堂兄弟。2.树的基本运算常用操作：（1）构造一个树CreateTree(T)（2）清空以T为根的树ClearTree(T)（3）判断树是否为空TreeEmpty(T)（4）获取给定结点的第i个孩子Child(T,node,i)（5）获取给定结点的双亲Parent(T,node)（6）遍历树Traverse(T)对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依5.1.2树的存储结构1.

4、双亲表示法树的双亲表示法主要描述的是结点的双亲关系。图5-3ABDCEFGHIJ类型定义：#defineMAX_TREE_NODE_SIZE100typedefstruct{TEntryTypeinfo;intparent;}ParentNode;typedefstruct{ParentNodeitem[MAX_TREE_NODE_SIZE];intn;//树中当前的结点数目}ParentTree;这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。算法实现举例：intParent(ParentTreeT,intnode){if(node<0

5、

6、node>=T.n)

7、return-2;elsereturnT.item[node].parent;}2.孩子表示法孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。举例：图5-4root0A214^1C^2B35^3E^4D6^5F^6G789^7H^8I^9J^在C语言中，这种存储形式定义如下：#defineMAX_TREE_NODE_SIZE10typedefstructChildNode{intchild;//该孩子结点在一维数组中的下标值structChileNode*next;//指向下一个孩子结点}CNode;typedefstruct{TEn

8、tryTypeinfo;//结点信息CNode*firstchild;//指向第一个孩子结点的指针}TNode;typedefstruct{TNodeitem[MAX_TREE_NODE_SIZE];intn,root;//n为树中当前结点的数目，root为根结点在一维数组中的位置}ChildTree;这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。获取给定结点第i个孩子的操作算法实现：intChild(Child

9、TreeT,intnode,inti){if(node<0

10、

11、node>=T.n)return-2；p=T.item[node].firstchild;j=1;while(p&&j!=i){p=p->next;j++;}if(!p)return-2;elsereturnp->child;}3.孩子兄弟表示法孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：其中，firstchild为指向该结点第一个孩子的