数据结构-第六章树和二叉树

《数据结构-第六章树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树6.1树的定义与基本概念6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5树、森林和二叉树的关系及转换6.6哈夫曼树与哈夫曼编码26.1树的定义与基本概念一、树的基本概念二、树的抽象数据类型定义：三、树的基本术语3一、树的基本概念树：是n(n≥0)个结点的有限集合T。当n=0时称为空树；当n>0时，该集合满足如下条件：其中必有一个称为根(root)的特定结点，它没有直接前驱，但有零个或多个直接后继。(2)其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1，T2，T3，…，Tm

2、，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。4ABCDEFGHIJMKLA()T1T3T2树根例如:B(E,F(K,L)),C(G),D(H,I,J(M))5数据对象D：一个集合，该集合中的所有元素具有相同的特性。数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H是如下的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。(2)除root以外，D中每个结点在关系H下都有且仅有一个前驱。二、树

3、的抽象数据类型定义6基本操作：InitTree（Tree）：将Tree初始化为一棵空树。(2)DestoryTree（Tree）：销毁树Tree。(3)CreateTree（Tree）：创建树Tree。(4)TreeEmpty（Tree）：若Tree为空，则返回TRUE，否则返回FALSE。(5)Root（Tree）：返回树Tree的根。(6)Parent（Tree，x）：树Tree存在，x是Tree中的某个结点。若x为非根结点，则返回它的双亲，否则返回“空”。7(7)FirstChild（Tree，x）：树Tree存

4、在，x是Tree中的某个结点。若x为非叶子结点，则返回它的第一个孩子结点，否则返回“空”。(8)NextSibling（Tree，x）：树Tree存在，x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则返回“空”。(9)InsertChild（Tree，p，Child）：树Tree存在，p指向Tree中某个结点，非空树Child与Tree不相交。将Child插入Tree中，做p所指向结点的子树。8(10)DeleteChild（Tree，p，i）：树Tree存在，p指向Tre

5、e中某个结点，1≤i≤d，d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。(11)TraverseTree（Tree，Visit（））：树Tree存在，Visit（）是对结点进行访问的函数。按照某种次序对树Tree的每个结点调用Visit（）函数访问一次且最多一次。若Visit（）失败，则操作失败。9结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点三、树的基本术语10DHIJM孩子结点、双亲结点、兄弟结点、堂兄弟结点、祖先

6、结点、子孙结点结点的层次:树的深度：ABCDEFGHIJMKL从根结点开始定义,根结点的层次为1，根的直接后继的层次为2，依此类推。树中叶子结点所在的最大层次11任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF12~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(

7、一个前驱、多个后继)对比树型结构和线性结构的结构特点136.2二叉树的类型定义二、二叉树的基本操作一、二叉树的定义三、二叉树的性质14二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分！15二、二叉树的基本操作：Initiate（bt）：将bt初始化为空二叉树。(2)Create（bt）：创建一棵非空二叉树bt。(3)Destory（bt）：销毁二叉树bt。(4)Empty（bt

8、）：若bt为空，则返回TRUE，否则返回FALSE。(5)Root(bt)：求二叉树bt的根结点。若bt为空二叉树，则函数返回“空”。(6)Parent（bt，x）：求双亲函数。求二叉树bt中结点x的双亲结点。若结点x是二叉树的根结点或二叉树bt中无结点x，则返回“空”。16(7)LeftChild（bt，x）：求左孩子。若结点x