数据结构实用教程（c语言版）中ppt

《数据结构实用教程（c语言版）中ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）中第五章树第六章图第五章树树形结构的逻辑特征是：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，也就是说结构中的数据元素间存在着一对多的层次关系。本章首先简单介绍树的基本概念，然后重点讨论二叉树的逻辑结构、存储结构及其运算，线索二叉树和线索二叉链表以及如何利用线索来实现遍历运算，并分析树、森林与二叉树之间的相互转换问题，最后介绍二叉树和树的典型应用。主要内容：5．1树的定义5．2二叉树二叉树的定义及性质二叉树的存储二叉树的遍历及实现算法5．3线索二叉树中序线索

2、二叉树的定义中序线索二叉树上遍历的实现利用中序线索实现前序遍历和后序遍历5．4树和森林5．5哈夫曼树5．1树的定义一、树的定义1、树的二元组定义：设tree=（D，S），其中D是数据元素的集合，S是D中数据元素之间关系的集合。设关系r∈S，相对r，满足下列条件：（1）D中有且仅有一个开始结点，该结点被称为树的根（Root）；（2）除树根结点外，D中其余的结点有且仅有一个前趋结点；（3）从根到其余结点都有路径。则称tree是相对r的树形结构。如图所示的树：该树采用二元组表示如下：设tree=（D，S），r∈SD={A，B，C，D，E，F，G，

3、H，I}r={，，，，，，，}其中A是开始结点，即树的根；除根A外，其余的结点有且仅有一个前趋结点，但对于后继结点却没有限制，A有三个后继结点B、C和D，B和G分别有两个后继结点，D只有一个后继结点，剩下的结点E、F、C、H、I都没有后继，属于终端结点。树形结构与线性结构比较：在线性结构中，有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋和一个后继。在树形结构中也是有且仅有一个开始结点（称为根），但终端结点（称为叶子）可以为任意多个，其余的内

4、部结点都有且仅有一个前趋，但可以有任意多个后继。树形结构中放宽了对结点的后继的限制。线性结构中每个元素的后继最多为一个，而树形结构的后继可以为多个。若树中每个非终端结点的后继刚好为一个时，就是线性表，线性结构是树形结构的一种特殊形式。2、树的递归定义树是一种递归的数据结构，也可以用递归的形式来定义树，树的递归定义如下：树是n（n＞0）个结点的有限集合（记作T），它满足两个条件：（1）有且仅有一个特定的称为根的结点；（2）其余的结点可分为m（m≥0）个互不相交的有限集合T1，T2，…，Tm，其中每个集合又是一棵树，并称其为根的子树（Subtr

5、ee）。3、树的表示方法除了前面介绍的树形表示法和二元组表示法外，还有其他三种常用的表示方法：凹入表表示法、嵌套集合表示法和广义表表示法。其中，树形表示法是最常用的表示方法，本书主要采用树形表示法（由于连线的箭头全部向下，所以省略箭头）。4、树中常用的一些基本术语：（1）与层次相关的术语：在树中，有且仅有一个开始结点，称为根结点（Root），在树中处于最上层；除根结点外的其余所有结点都有且仅有一个前趋，每个结点的前趋结点称为该结点的父（双亲）结点（Parent），在树中处于该结点的上一层；树中的每个结点都可以有若干个后继结点，每个结点的后继

6、点称为该结点的子（孩子或子女）结点（Child），在树中处于该结点的下一层，它们是该结点的子树的根。没有后继的结点称为叶子结点（Leaf），叶子结点是树的终端结点，可以为多个。双亲相同的结点互称为兄弟（Silbing），在树中处于同一层。（2）树中结点之间具有分支：一个结点的子树的个数，称为该结点的度（Degree），树中度最大的结点的度数称为该树的度。（3）路径（Path）是树中结点的序列，设结点序列为b1，b2，……，bj，若序列中任意两个相邻结点都满足bi是bi+1的双亲，1≤i≤j-1，则称该结点序列为从b1到bj的路径。路径长度为

7、序列中结点总数减1，即所经过的边的数目。若树中存在一条从b到bj的路径，则称b是bj的祖先（Ancestor），而bj是b的子孙（Descendant）。（4）如果树中所有子树都看成是从左到右的次序排列（子树不能互换），则称此树为有序树（OrderedTree）。而不考虑子树排列顺序的树，称为无序树（UnorderedTree）。（5）森林（Forest）是m（m≥0）棵互不相交的树的集合。5．2二叉树一、二叉树的定义及性质1、二叉树（BinaryTree）是n（n≥0）个结点的有限集合，满足：当n=0时，为空二叉树。当n＞0时，是由一个根

8、结点和两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。在二叉树中，每个结点左子树的根为该结点的左孩子（LeftChild），右子树的根为该结点的右孩子（RightChi