第六章 树和二叉树.ppt

第六章树和二叉树,数据结构可分为线性结构和非线性结构两大类。前面几章主要研究的是线性结构。一般的，线性结构只能用来描述数据元素之间的线性顺序关系，而很难反映元素之间的层次(分支)关系。本章将要讨论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。树形结构，是一类非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。本章先介绍树、二叉树的定义、性质及存储结构，重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系，最后介绍树的应用。,引 言,内容提要,6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 赫夫曼树及其应用小结,6.1 树的定义 和基本术语,树(Tree)是包含n(n0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(Root)的结点；(2)当n1时，其余的结点可分为m(m0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(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，T12=F。T11和T12都是B的子树。而T11中E是根结点，K和L是E的两棵互不相交的子树，其本身又是只有一个根结点的树。,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm，其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,ADT Tree,基本操作：,查 找 类,插 入 类,删 除 类,Root(T)/求树的根结点,查找类：,Value(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,value)/给当前结点赋值,InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树,ClearTree(&T)/将树清空,删除类：,DestroyTree(&T)/销毁树的结构,DeleteChild(&T,&p,i)/删除结点p的第i棵子树,树的表示方法有四种，各用于不同的目的。(1)直观表示法：就是一棵树的直观表示。(2)广义表示法：下图(a)是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。(3)凹入表示法：下图(b)用的是凹入表示法(类似书的编目)。树的凹入表示法主要用于树的屏幕和打印显示。(4）嵌套集合表示法：参见P120图6.2。表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生一个树结构。,树的表示形式,A,B,C,D,E,F,G,H,I,J,M,K,L,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,树根,例如:,基 本 术 语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素及若干指向子树的分支,拥有的子树数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径：,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点,()有确定的根；()树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),6.2 二 叉 树,6.2.1 二叉树的定义 二叉树（Binary Tree）或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,