数据结构--树和二叉树

第六章树和二叉树第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4遍历的应用6.5*线索二叉树（简单介绍）6.6树和森林6.7哈夫曼树及应用第六章树和二叉树6.1树的有关概念1.树的概念2.树的应用3.树的表示4.树的有关术语5树的基本操作6.1树的有关概念1．树的定义定义：树是n个结点的有限集合。在任一棵非空树中：（1）有且仅有一个称为根的结点；。（2）其余结点可分为m个互不相交的有限集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。6.1树的有关概念从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构JIACBDHGFE6.1树的有关概念2．树的应用1）树可表示具有分枝结构关系的对象例1．家族族谱例2．单位行政机构的组织关系、系统功能模块图6.1树的有关概念2）树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………6.1树的有关概念3、树的基本术语1）结点的度：结点所拥有的子树的个数。2）树的度：树中各结点度的最大值。CGBDEFKLHMIJADA=3DB=2DC=1DG=0DTree=36.1树的有关概念3）叶子结点：度为0的结点，也称为终端结点。4）分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA叶子结点：{K,L,F,G,M,I,J}分支结点：{A,B,C,D,E,H}6.1树的有关概念5）孩子、双亲：树中结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；6）兄弟：具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA孩子结点：{B,C,D}双亲结点：{A}兄弟结点：{E，F}6.1树的有关概念7）路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲，则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA结点序列：{nA,nB,nE,nK}路经长度=36.1树的有关概念8）祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。CGBDEFKLHMIJA6.1树的有关概念9）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。10）树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC6.1树的有关概念11）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的（即不能互换），称这棵树为有序树；反之，称为无序树。ACBGFEDACBGFED数据结构中讨论的一般都是有序树6.1树的有关概念12）森林：m(m≥0)棵互不相交的树的集合。CBDEFKLHJA树中每一个结点的子树的集合即为森林。6.1树的有关概念树结构和线性结构的比较线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多6.1树的有关概念4、树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）InitTree(&T);//构造空树T2）DestroyTree(&T);//销毁树T3）CreateTree(&T,definition);//按definition构造树T4）ClearTree(&T);//将树T清为空树5）TreeEmpty(T);//判断树T是否为空树6）TreeDepth(T);//求树的深度7）Root(T);//返回树T的根值6.1树的有关概念8）Value(T,&cur_e);//求树T中结点cur_e的值9）Assign(T,cur_e,value);//把value赋值给树T的cur_e结点10）Parent(T,cur_e);//求树T中非根结点cur_e的双亲11）LeftChild(T,cur_e);//求树T中非叶子结点cur_e的左孩子12）RightSibling(T,cur_e);//求树T中cur_e结点的右兄弟13）InsertChild(&T,&p,i,c);//在树中插入一个结点14）DeleteChild(&T,&p,i);//删除树中某一个结点15）TraverseTree(T,Visit());//按某种次序访问树中每个结点6．2二叉树树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。6.2二叉树一二叉树的概念1二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明：1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠例——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;ABCDEFG6.2二叉树2．二叉树的基本形态Ф空二叉树只有一个根结点右子树根结点只有右子树左子树根结点只有左子树左子树右子树根结点同时有左右子树6.2二叉树二、二叉树性质性质1在二叉树的第i层上最多有2i-1个结点（i=1）证明：当i=1时，第1层只有一个根结点，结点数=20=1，结论显然成立。假设j=i-1时，结论正确，即第j层最多有2i-2，所以当j=i时，第i层最多有2*2i-2=2i-1；结论正确6.2二叉树性质2一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。证明：由性质1可知，深度为k的二叉树中结点个数最多==2k-1；kii1)(层上结点的最大个数第每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。6.2二叉树证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：n＝n0＋n1＋n2在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：n＝n1＋2n2＋1因此可以得到：n0＝n2＋1。A15234678910BCDEFGHIJ性质3在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1。6.2二叉树两种特殊的二叉树●满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；A15234678910BCDEFGHIJKLMNO1112131415满二叉树的特点：1.叶子只能出现在最下一层；2.只有度为0和度为2的结点。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多6.2二叉树●完全二叉树深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点都一一对应时，称之为完全二叉树。A15234678910BCDEFGHIJA15234678910BCDEFGHIJKLMNO11121314156.2二叉树在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点6.2二叉树完全二叉树的特点1.叶子结点只能出现在最下两层；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。3.深度为k的完全二叉树在k-1层上一定是满二叉树。A1523467910BCDEFGHIJK11L12M13N14O1586.2二叉树性质4具有n个结点的完全二叉树的深度为log2n+1。A15234678910BCDEFGHIJ6.2二叉树性质5对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点，有：（1）如果i＞1，则结点i的双亲结点的序号为i/2（取整）；如果i＝1，则结点i是根结点，无双亲结点。A15234678910BCDEFGHIJ6.2二叉树（2）如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。A15234678910BCDEFGHIJ6.2二叉树（3）如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点i无右孩子。A15234678910BCDEFGHIJ6.2二叉树对一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。18910456723性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。6.2二叉树三．二叉树存贮结构1二叉树的顺序结构二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系——父子关系。如何利用数组下标来反映结点之间的逻辑关系?完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。6.2二叉树完全二叉树的顺序存储A15234678910BCDEFGHIJ以编号为下标ABCDEFGHIJ数组下标123456789106.2二叉树二叉树的顺序存储ABCDFGE按照完全二叉树编号ABCDFGE123561013ABC∧DE∧∧∧F∧∧G数组下标12345678910111213以编号为下标6.2二叉树二叉树的顺序存储结构一般仅存储完全二叉树和满二叉树。6.2二叉树2二叉树的链式存储结构1）基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。结点结构：lchilddatarchild其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。6.2二叉树二叉树的二叉链表存储表示：TypedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;6.2二叉树2）二叉链表二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域ABCDEFGGFEDBA∧∧∧∧∧∧∧∧C在n个结点的二叉树中，有n+1个空链域。6.2二叉树3）三叉链表三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域结点结构：lchilddataparent其中，data：数据域，存放该结点的数据信息；parent:双亲指针域，存放指向指向双亲节点的指针；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。rchild6.2二叉树ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧第六章树和二叉树6.3二叉树的遍历一.二叉树的遍历方法二.遍历的递归算法6.3二叉树的遍历一、二叉树的遍历方法二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历操作的结果？非线性结构线性化抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。前序遍历中序遍历后序遍历层序遍历对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事。二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每