数据结构(C语言版)6、树和二叉树

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

1、第6章树和二叉树本章中主要介绍下列内容：树的逻辑定义和基本术语二叉树的逻辑定义及存储结构二叉树的基本操作算法（*遍历算法）树、森林和二叉树的转换哈夫曼树及其应用6.树的逻辑定义和基本术语6.1树6.2二叉树6.3树、森林与二叉树的转换6.3哈夫曼树及其应用6.1树_TREE6.1.1树的定义和基本运算mathematicalconcept->Abstractdatatype->Datastructure->Implementation->Application1.定义:树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有

2、一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。图6-1EFGHIJBCDAAKLM(a)(b)(c)结点(node/vertex)数据元素的内容及其指向其子树根的分支统称为结点。结点的度(degree)结点的分支数。终端结点（叶子leaf）度为0的结点。非终端结点度不为0的结点。结点的层次(level)树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度树中所有结点度的最大值。树的深度depth树中所有结点层次的最大值。有序树(orderedtree)、无序树如果

3、树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林(forest)是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子child、双亲parent结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。结点的子孙descendant以某结点为根的子树中的所有结点都被称为是该结点的子孙。结点的祖先ancestor从根结点到该结点路径上的所有结点。兄弟sibling同一个双亲的孩子之间互为兄弟。堂兄弟双亲在同一层的结点互为堂兄弟。2.树的基本运算常用操作：（1）构造一个树CreateTree(T)（

4、2）清空以T为根的树ClearTree(T)（3）判断树是否为空TreeEmpty(T)（4）获取给定结点的第i个孩子Child(T,node,i)（5）获取给定结点的双亲Parent(T,node)（6）遍历树Traverse(T)对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依6.1.2树的存储结构应用一段连续的存储空间存储树，要求存储结构能表示逻辑结构，即满足树的定义，即同一结点有多个不同的后继，或多个结点具有同一前驱，并且不存在相交的子树。

5、1.双亲表示法:树的双亲表示法主要描述的是结点的双亲关系，不但要存储树中结点数据元素本身的值，而且要存储结点双亲所在的位置。如图2所示：图6-2根结点A存储于第0位置，无双亲，故双亲的存储位置标志设置为-1,结点BCD依次存储于123位置，其双亲所在位置是0;…….类型定义：#defineMAX_TREE_NODE_SIZE100typedefstructParentNode{EelemTypeinfo;//树中数据元素数据类型intparent;//其双亲结点的存储位置};typedefstructParentTree{ParentNodeitem[MAX_TREE_NODE_S

6、IZE];intn;//树中当前的结点数目};这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。算法实现举例,求双亲结点所在位置：intParent(ParentTreeT,intnode)//返回第node个结点的双亲所在的位置{if(node<0

7、

8、node>=T.n)return-1;else{printf(“parentelemis:%?”,T.item[parent].info);returnT.item[node].parent;}}item[0]item[1]item[…]item[10]info值‘A’parent值-1info值‘B’paren

9、t值0Info？Parent？info值‘J’parent值6双亲表示法数据类型进一步解释：ParentTree数据类型有两个域，即ParentTree.item[]和ParentTree.n;每一个item[i]有两个域，即数据元素的数值info和双亲所在位置parent;结合图6-2存储示意图如下：ParentTree.n=10//树中有10个结点ParentTree.item[]域示意图如下：2.孩子表示法孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子