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

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

1、第六章树和二叉树数据结构可分为线性结构和非线性结构两大类。前面几章主要研究的是线性结构。一般的，线性结构只能用来描述数据元素之间的线性顺序关系，而很难反映元素之间的层次(分支)关系。本章将要讨论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。树形结构，是一类非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。本章先介绍树

2、、二叉树的定义、性质及存储结构，重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系，最后介绍树的应用。引言内容提要6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用小结6.1树的定义和基本术语树(Tree)是包含n(n≧0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(Root)的结点；(2)当n>1时，其余的结点可分为m(m>0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(

3、Subtree)。树也可以这样定义：树是由根结点和若干棵子树构成的。可以看出，在树的定义中用了递归的概念，即在树的定义中又用到树的定义，它道出了树的固有特性，因此递归算法是树结构算法的显著特点。树的定义上图(a)是只有一个根结点的树；图(b)是有13个结点的树，其中A是根，其余结点分成三个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2和T3都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余结点分为两个互不相交的子集；T11={E，K，L}

4、，T12={F}。T11和T12都是B的子树。而T11中E是根结点，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树。数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ADTTree{基本操作：查找类插入类删除类Root(T)//求树的根结点查找类：Va

5、lue(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,va

6、lue)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树树的表示方法有四种，各用于不同的目的。(1)直观表示法：就是一棵树的直观表示。(2)广义表示法：下图(a)是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。(3)凹入表示法：下图(b

7、)用的是凹入表示法(类似书的编目)。树的凹入表示法主要用于树的屏幕和打印显示。(4）嵌套集合表示法：参见P120图6.2。表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生一个树结构。树的表示形式ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素及若干指向子树的分支拥有的子树数树中所有结点的度的最大

8、值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点(１)有确定的根；(２)树根和子树根