c语言数据结构_第05讲 树

《c语言数据结构_第05讲 树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实用数据结构基础第6章树第6章树知识点树的基本概念与术语二叉树及二叉树的存储结构二叉树的遍历及线索二叉树一般树和二叉树的转换哈夫曼树及哈夫曼编码难点二叉树遍历算法的设计利用二叉树遍历算法，解决简单应用问题哈夫曼树的算法要求熟练掌握以下内容:树的基本概念和术语二叉树定义和存储结构二叉树遍历的概念和二叉树遍历的算法哈夫曼树的建立了解以下内容：树和二叉树之间的相互转换方法线索二叉树的概念哈夫曼编码第6章目录6-1树的定义和术语6-2二叉树6-3遍历二叉树和线索二叉树6-4二叉树的转换6-5二叉树树的应用6-6

2、哈夫曼树及其应用小结实验6树子系统习题66-1树的定义和术语6-1树的定义1．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。在任意一棵非空树T中：（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点；（2）当n>1时，除根结点之外的其余结点被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树，并且称为根的子树。树的定义采用了递归定义的方法，即在树的定义中又用到树的概念，这正好反映了树的固有特性。1234图6-1树结构示意图2．

3、树的其它表示法图6-1是树的结构表示法，是一种直观的画法，其特点是对树的逻辑结构的描述非常直观、清晰。是使用最多的一种描述方法。除此以外，还有以下几种描述树的方法：ABCHGFEDJI（1）嵌套集合法嵌套集合法，也称为文氏图法（VennDiagram），它是用集合以及集合的包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。图6-2(a)就是一棵树的嵌套集合表示。ABCEIJDFGH图6-2（a）嵌套集合表示(2)圆括号表示法圆括号表示法也称为广义表表示法，它是使用括号将集合层次与包

4、含关系显示出来。下式即是图6-1所示树的圆括号表示法：(A(B(D,E(I,J),F),C(G,H)))(3)凹入法凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点集合的包含关系，图6-1所示树的凹入法表示如图6-2(b)。树的凹入表示法主要用于树的屏幕显示和打印输出。ABCEDJFGH图6-2（b）凹入表示法I6-1-2基本术语（1）结点——树的结点包含一个数据及若干指向其子树的分支。（2）结点的度——结点所拥有的子树数称为该结点的度（Degree）。（3）树的度——树中各结点度的最大值

5、称为该树的度。（4）叶子（终端结点）——度为零的结点称为叶子结点。（5）分枝结点——度不为零的结点称为分支结点。（6）兄弟结点——同一父亲结点下的子结点称为兄弟结点。（7）层数——树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。（8）树的深度——树中结点的最大层数称为树的深度（或高度）。（9）森林——零棵或有限棵互不相交的树的集合称为森林。在数据结构中，树和森林并不象自然界里有一个明显的量的差别。任何一棵树，只要删去根结点就成了森林，见图6-3。(a)树(b)移去根结点后成为森林图6-3（

6、10）有序树和无序树——树中结点的各子树从左到右是有次序的（即不能互换位置），称这样的树为有序树；否则称为无序树。ABCHGFEDJIKJBCDEFGHIK6-2二叉树6-2-1二叉树的定义1．定义二叉树是有n（n>=0）个结点的有限集合。（1）该集合或者为空（n=0）；（2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；（3）左子树和右子树同样又都是二叉树。通俗地讲：在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是

7、特殊的有序树。2．二叉树的形态根据定义，二叉树可以有五种基本形态，如图6-4所示。(a)(b)(c)(d)(e)图6-4二叉树的基本形态其中：（a）空二叉树；（b）仅有根结点的二叉树；（c）右子树为空的二叉树；（d）左子树为空的二叉树；（e）左、右子树均非空的二叉树。ФLchildLchildRchildRchild3．二叉树的基本操作：（1）CreateBT（）：创建一棵二叉树。（2）ShowTree(BT*T)：按凹入法显示二叉树。（3）Preorder(BT*T)：按先序（根、左、右）遍历二叉树上

8、所有结点。（4）Inorder(BT*T)：按中序（左、根、右）遍历二叉树上所有结点。（5）Postorder(BT*T)：按后序（左、右、根）遍历二叉树上所有结点。（6）Levelorder(BT*T)：按层次遍历二叉树上所有结点。（7）Leafnum(BT*T)：求二叉树叶结点总数。（8）TreeDepth(BT*T)：求二叉树的深度。6-2-2二叉树的性质性质1一棵非空二叉树的第i层上最多有2i–1个结点（i≥1）。一棵非空二叉树的第