数据结构严蔚敏第6章

第六章树和二叉树教学目的和要求1、熟练掌握二叉树的结构特点，了解相应的证明。2、熟悉二叉树的各种存储结构的特点及适用范围。3、掌握二叉树遍历的递归与非递归算法。4、掌握二叉线索树的相关算法。5、熟悉树的各种存储结构及特点，掌握树和森林与二叉树的方法。6、了解最优树的特性，掌握最优树和哈夫曼编码的方法。1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题树形结构全校学生档案管理的组织方式ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGA6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.1树的类型定义数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:基本操作：查找类插入类删除类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棵子树对比树型结构和线性结构的结构特点线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.2二叉树的类型定义二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的主要基本操作：查找类插入类删除类Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉树的重要特性性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤ji，命题成立；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij性质4：具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n2k即k-1≤log2nk因为k只能是整数，因此，k=log2n+1。性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。6.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;一、二叉树的顺序存储表示例如:ABCDEFABDCEF0123456789101112131401326顺序存储结构仅适用于完全二叉树！二、二叉树的链式存储表示1.二叉链表2．三叉链表3．双亲链表4．线索链表ADEBCFrootlchilddatarchild结点结构:1.二叉链表typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:ADEBCFroot2．三叉链表parentlchilddatarchild结点结构:typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指针structTriTNode*parent;//双亲指针}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:0123456B2C0A-1D2E3F4dataparent结点结构:3．双亲链表LRTagLRRRLtypedefstructBPTNode{//结点结构TElemTypedata;int*parent;//指向双亲的指针charLRTag;//左、右孩子标志域}BPTNodetypedefstructBPTree{//树结构BPTNodenodes[MAX_TREE_SIZE];intnum_node;//结点数目introot;//根结点的位置}BPTree6.4二叉树的遍历一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。对“二叉树”而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。二、先左后右的遍历算法先序（根）的遍历算法中序（根）的遍历算法后序（根）的遍历算法若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先序（根）的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中序（根）的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后序（根）的遍历算法：课堂提问：有以下结构的二叉树写出其先序、中序和后序遍历的序列ABCDE三、算法的递归描述voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//先序遍历二叉树if(T){visit(T-data);//访问结点Preorder(T-lchild,visit);//遍历左子树Preorder(T-rchild,visit);//遍历右子树}}四、中序遍历算法的非递归描述BiTNode*GoFarLeft(BiTreeT,Stack*S){if(!T)returnNULL;while(T-lchild){Push(S,T);T=T-lchild;}returnT;}voidInorder_I(BiTreeT,void(*visit)(TelemType&e)){Stack*S;t=GoFarLeft(T,S);//找到最左下的结点while(t){visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);elseif(!StackEmpty(S))//栈不空时退栈t=Pop(S);elset=NULL;//栈空表明遍历结束}//while}//Inorder_I五、遍历算法的应用举例1、统计二叉树中叶子结点的个数(先序遍历)2、求二叉树的深度(后序遍历)3、复制二叉树(后序遍历)4、建立二叉树的存储结构1、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。voidCountLeaf(BiTreeT,int&count){if(T){if((!T-lchild)&&(!T-rchild))count++;//对叶子结点计数CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);}//if}//CountLeaf2、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。首先分析二叉树的深度和它的左