6第六章树和二叉树.

第六章树和二叉树ZhejiangUniversityofTechnology26.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5树和森林的表示方法6.6树和森林的遍历6.7哈夫曼树与哈夫曼编码ZhejiangUniversityofTechnology36.1树的类型定义ZhejiangUniversityofTechnology4数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ZhejiangUniversityofTechnology5ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:ZhejiangUniversityofTechnology6基本操作：查找类插入类删除类ZhejiangUniversityofTechnology7Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历ZhejiangUniversityofTechnology8InitTree(&T)//初始化空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树ZhejiangUniversityofTechnology9ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ZhejiangUniversityofTechnology10ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:ZhejiangUniversityofTechnology11树形图表示的例子ABKELFDHMJICG嵌套集合表示法ABCDEKLFGHIJM凹入表示法（A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表表示法ABCDEFGHIJMKLZhejiangUniversityofTechnology12基本术语ZhejiangUniversityofTechnology13结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJMZhejiangUniversityofTechnology14孩子、双亲兄弟、堂兄弟祖先、子孙结点的层次:树的深度：ABCDEFGHIJMKL根结点的层次为1，第l层结点的子树根结点的层次为l+1树中叶子结点所在的最大层次ZhejiangUniversityofTechnology15有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。ZhejiangUniversityofTechnology16任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLFZhejiangUniversityofTechnology17对比树型结构和线性结构的结构特点ZhejiangUniversityofTechnology18线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)ZhejiangUniversityofTechnology196.2二叉树的类型定义ZhejiangUniversityofTechnology20二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树ZhejiangUniversityofTechnology21二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树ZhejiangUniversityofTechnology22二叉树的主要基本操作：查找类插入类删除类ZhejiangUniversityofTechnology23Root(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());ZhejiangUniversityofTechnology24InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ZhejiangUniversityofTechnology25ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ZhejiangUniversityofTechnology26二叉树的重要特性ZhejiangUniversityofTechnology27性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤ji，命题成立；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。ZhejiangUniversityofTechnology28性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。ZhejiangUniversityofTechnology29性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。ZhejiangUniversityofTechnology30两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。12345678910111213141512345678910ZhejiangUniversityofTechnology31性质4：具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n2k即k-1≤log2nk因为k只能是整数，因此，k=log2n+1。ZhejiangUniversityofTechnology32性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。ZhejiangUniversityofTechnology336.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示ZhejiangUniversityofTechnology34#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;一、二叉树的顺序存储表示ZhejiangUniversityofTechnology35例如:ABDCEF0123456789101112130ABCDEF141326ZhejiangUniversityofTechnology36二、二叉树的链式存储表示1.二叉链表2.三叉链表ZhejiangUniversityofTechnology37ADEBCFrootlchilddatarchild结点结构:1.二叉链表ZhejiangUniversityofTechnology38typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:ZhejiangUniversityofTechnology39二叉排序树它或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树。ZhejiangUniversityofTechnology40例1：向一个二叉排序树b中插入一个结点s分析：（1）若b是空树，则将s所指结点作为根结点插入；（2）若s-data等于b的根结点的数值域，则返回（3）若s-data小于b的根结点的数值域，则把s所指结点插入到左子树中，否则插入到右子树中。ZhejiangUniversityofTechnology41voidinsert(BiTree&b,BiTree&s){if(b==NULL)b=s;elseif(s-data==b-data)return;elseif(s-datab-data)insert(b-left,s);else//if(s-datab-data)insert(b-right,s);}//注意，这里使用了递归调用实现。ZhejiangUniversityofTechnology42例2：根据用户输入的正整数，创建一个二叉排序树，以-1作为结束标志。分析：（1）已有一个空树（2）新生成一个树节点s（3）用户输入的数据赋给s-data（4）s的左子树、右子树初始为空（5）插入节点sZhejiangUniversityofTechnology43voidcreat(BiTree&b){intx;BiTrees;b=NULL;do{scanf(%d,&x);s=(bnode*)malloc(sizeof(bnode));s-data=x;s-left=NULL;s-right=NULL;insert(b,s);}while(x!=-1);}ZhejiangUniversityofTechnology44ADEBCFroot2．三叉链表parentlchilddatarchild结点结构:ZhejiangUniversityofTechnology45typedefstructTriTNode{