数据结构（c语言）中ppt

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

1、数据结构（C语言）中第5章树（时间：3次课，6学时）第5章树教学提示：在前面2～4章中介绍了线性表、栈、队列、数组、串等，它们的逻辑结构都是线性的，即数据之间存在着一对一的关系，表示数据的结点间具有惟一前驱和惟一后继。然而，在实际应用中常常遇到非线性关系。非线性结构的特征是结点间的关系不具有惟一性。本章介绍的树型结构，其结点间关系具有惟一的前驱而后继不惟一，即结点之间是一对多的关系。教学目标：通过本章的学习，用户应掌握树的逻辑结构、存储结构及其基本操作；学会利用树、二叉树的特性、遍历的递归算法以及哈夫曼算法解决实际问题。第5章树5.1树5.2二叉树5.3树和森林5.4上机实习5.5习题

2、5.1树5.1.1树的基本概念5.1.2树的表示5.1.3树的基本运算5.1.1树的基本概念图5.1树的逻辑结构示例5.1.1树的基本概念1.树的定义树是n(n≥0)个结点的有限集合。当n＝0时，为空树；当n>0时，该集合满足如下条件：①有且仅有一个称为根(root)的特定结点，它没有直接前驱，但有零个或多个直接后继。②其余n-1个结点可以划分成m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合Ti又是一棵树，称其为根的子树。2.关于树结构的基本术语结点：包含一个数据元素及若干指向其子树的分支信息。结点的度：一个结点所拥有的子树个数称为该结点的度。树的度：树中所有结点的

3、度的最大值。叶子结点(终端结点)：度为零的结点，即没有后继的结点。分支结点(非终端结点)：度不为零的结点。孩子结点：若某个结点为树或子树的根，这个结点的直接后继，称为该结点的孩子结点。5.1.1树的基本概念双亲结点：一个结点被称为其孩子结点(或后继结点)的双亲结点。兄弟结点：同一个双亲的结点之间互为兄弟结点。祖先结点：从树的根结点到达一个结点的路径上的所有结点都是该结点的祖先结点。子孙结点：结点为根的子树中的所有结点(包括直接后继和间接后继)都称为该结点的子孙结点。结点的层次：树具有一种层次结构，从根结点开始定义，根结点为第一层，根的孩子为第二层，以此类推。树的高度(深度)：树中所有结

4、点的层次的最大值。有序树：如果将树结点的各个子树看成从左到右是有次序的(不能互换)，即各子树之间是有先后次序的，则称之为有序树。反之，被称为无序树。森林：m(m≥0)棵互不相交的树的集合。5.1.2树的表示除了树的逻辑定义以外，树的表示法还有以下四种。对于以下逻辑结构的树：T=(K，L)K={A，B，C，D，E，F，G，H}L={，，，，，，}T是表示树形结构的二元组，其中，K是树中结点的有限集，L是树中结点之间关系的有限集。正是由于树结构在日常生活和计算机程序设计中应用非常广泛，使得树的表示方法多种多样。一般来说，

5、分等级的分类方案都可以用树结构表示。5.1.2树的表示图5.2树的四种表示5.1.3树的基本运算数据对象D：D是一个集合，且该集合中的所有元素具有相同的特性。数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，其中H是如下的二元关系：在D中存在惟一的称为根的数据元素root，它在关系H下没有前驱。除root以外，D中每个结点在关系H下都有且仅有一个前驱。基本操作：InitTree(Tree)：将Tree初始化为一棵空树。DestoryTree(Tree)：销毁树Tree。CreateTree(Tree)：创建树Tree。TreeEmpty(T

6、ree)：若Tree为空，则返回TRUE，否则返回FALSE。ROOT(Tree)：返回树Tree的根。5.1.3树的基本运算(2)Parent(Tree，x)：树Tree存在，x是Tree中的某个结点。若x为非根结点，则返回它的双亲。否则返回“空”。FirstChild(Tree，x)：树Tree存在，x是Tree中的某个结点。若x为非叶子结点，则返回它的第一个孩子结点，否则返回“空”。NextChild(Tree，x)：树Tree存在，x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则返回“空”。InsertChild(Tre

7、e，p，Child)：树Tree存在，p指向Tree中某一个结点，非空树Child与Tree不相交。将Child插入Tree中，作为p所指向结点的子树。DeleteChild(Tree，p，i)：树Tree存在，p指向Tree中某个结点，1≤i≤d，d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。TraverseTree(Tree，Visit())：树Tree存在，Visit()是对结点进行访问的函数。按某种次序对树Tree的