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

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

1、知识回顾线性表一般的线性表特殊的线性表：栈、队列线性表的扩展：数组、广义表特点：有序前趋、后继1第六章树和二叉树2树是以分支关系定义的层次结构。树结构在客观世界广泛存在:在自然科学，如地理学领域，水系、地貌（等高线）、行政区划等都具有树结构关系；在社会人文领域，人类社会构成、组织机构等也具有树结构关系。树型结构：非线性数据结构3要求1.熟练掌握二叉树的结构特性。2.熟悉二叉树的各种存储结构的特点及适用范围。3.掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。4.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5.熟悉树的各种存储结构

2、及其特点，掌握树和森林与二叉树的转换方法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。46.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树与其应用主要内容56.1.1树的定义6树（tree）是n(n≥0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。7A只有根结点的树ABCDEFGHIJKLM有子树的树根子树8树的表示法图形表示法嵌套集合表示法广义表表示法凹入表示法左

3、孩子－右兄弟表示法9图形表示法教师学生其他人员2001级2002级2003级2004级……西安石油大学计算机系电信系自控系……叶子根子树10嵌套集合表示法11(A(B(E(K,L),F),C(G),D(H(M),I,J))约定：根作为由子树森林组成的表的名字写在表的左边广义表表示法12凹入表示法又称目录表示法13ABCDEFGHIJKLMdata左孩子右兄弟左孩子－右兄弟表示法多叉树转为了二叉树14数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有

4、限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ADTTree{15基本操作：查找类插入类删除类16Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历17InitTree(&T)

5、//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树18ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树19ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:20(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：

6、子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。21对比树型结构和线性结构的结构特点22~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)对比树型结构和线性结构的结构特点236.1.2基本术语24结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM25子孙:以某结点为根的子树中的任一结点。AB

7、CDEFGHIJMKL孩子:结点的子树的根。双亲:该结点称为孩子的双亲。兄弟:同一个双亲的孩子之间互称兄弟。祖先:从根到该结点所经分支上的所有结点26有序树：子树之间存在确定的次序关系无序树：子树之间不存在确定的次序关系树的深度：树中结点的最大层次堂兄弟:其双亲在同一层的结点结点的层次:假设根结点的层次为1，第l层的结点的子树根结点的层次为l+127ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F