天津科技大学数据结构树和二叉树课件

1、6.1 树的定义和基本术语6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码是一类重要的, 是以定义的。如家谱、行政组织机构等。源程序的语法结构等。ABCDEFGHIJA(a) (b) (c)树的例子:6.1 树的定义和基本术语树的定义和基本术语：n(n0)个结点组成的有限集合。若n=0

2、，则为；若n0，则满足如下两个条件：(1)有且仅有一个特定的；(2)当n1时，根结点以外的其它结点可分为m(m0) 个互不相交的有限集合T1, T2, Tm，其中每个集合本身又是一棵树，称其为根的。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ABCDEFGHIJ(A(B(E(K,L),F),C(G),D(H(M),I,J)嵌套括号表示法 I JFKLGMCCDBEA嵌套集合凹入表树形表示树的表示方法：树的表示方法：ABCDEFGHIJKLMABCDEFGHIJKLM 构造空树T。 求树T的根结点。 求树T中值为x的结点的双亲。 求树T中值为x的结点的第i个孩子。树T中将值

3、为x的结点作为值为y的结点的第i个孩子插入到树中。删除值为x的结点的第i个孩子。 遍历或访问树T。由n(n0)个结点构成的有限集合，此集合或者为空集，或者由一个根结点及两棵互不相交的左、右子树组成，并且左右子树都是二叉树。每个结点最多有两个孩子，即不存在度大于2的结点，有序树，其子树的顺序不能颠倒，即使只有一棵子树也要区分其是左子树还是右子树。 操作算法简单，且任何树都可与二叉树 相互转换，解决了树的存储结构及其运算中存在的复杂性。(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树 (e)根和左右子树图：二叉树的5种形式注：图(c) 和图(d)是不同的两棵二

4、叉树。AABABACB构造空二叉树T。 销毁二叉树T。 求T的根结点。求T中值为e的结点的双亲。求T中值为e的结点的左/右孩子。 求T中值为e的结点的左/右兄弟。 遍历二叉树T。 在T中，将值为y的结点作为值为x的结点的左/右孩子插入。 在T中，删除值为x的结点的左/右孩子。性质性质1：采用归纳法证明： i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现假定对所多的 j，1ji，命题成立，即第j层上至多有2j-1个结点。 由假设可知，第i1层上至多有2i-2个结点。 由于二叉树每个结点的度最大为2，所以在第i层上最大结点数为第i1层上最大结点数的二倍，即22i-22i-1。命题得到

5、证明。性质性质2：性质性质3： kikiii11k1122)(层上的最大结点数第设二叉树中度为1的结点数为n1，二叉树中总结点数为N。因为二叉树中所有结点均小于或等于2，所以：Nn0n1n2而二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：NB1。由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2*n2 NB1n12n21从而得到：n0+n1+n2=n1+2*n2+1n0n2+1两种特殊形态的二叉树：深度为k且具有2k-1个结点的二叉树。满二叉树结点：从根结点开始，自上而下、从左至右的顺序。如果一棵具有n个结点且深度为k的二叉树，其各结点都与深

6、度为k的满二叉树中编号为1 n的结点一一对应的二叉树。：(1)所有的叶子结点都出现在第k层或k-1层。(2)对任一结点，若其右子树的最大层次为l，则其左子树的最大层次为l或l1。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。(a)完全二叉树(b)非完全二叉树(c)非完全二叉树图:特殊形态的二叉树图:满二叉树245367124536124537123671性质4：。假设此二叉树的深度为k，则该二叉树的前k-1层为满二叉树，共有2k-1-1个结点；而该二叉树有k层，第k层至少有1个结点，最多有2k-1个结点。因此有：(2k-1-1)+1n(2k-1-1)+2k-1，即

7、 2k-1n2k-1，即。 2k-1n2k，同时取对数得： k-1log2ndata=c; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; /先序遍历Status PreOrderTraverse(BiTree T, Status (*Visit)(BiTree t)if(T) if(*Visit)(T) /访问结点if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit)return OK; return ERROR; else retur

8、n OK;/中序遍历Status InOrderTraverse(BiTree T, Status (*Visit)(BiTree t)if(T) if(InOrderTraverse(T-lchild, Visit) if(*Visit)(T) if(InOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK;/后序遍历Status PostOrderTraverse(BiTree T, Status (*Visit)(BiTree e) if(T) if(PostOrderTraverse(T-lchil

9、d,Visit) if(PostOrderTraverse(T-rchild,Visit) if(*Visit)(T) /访问结点return OK; return ERROR; else return OK;void PreOrderNRTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree p,s100; int top=0; /top为栈顶指针为栈顶指针 p=T; while( p | top0 ) while(p) (*Visit)(p); stop+=p; p=p-lchild; p=s-top; p=p-rchild; void In

10、OrderNRTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree p,s100; /s为一个栈 int top=0; p=T; while( p | top0 ) while(p) stop+=p; p=p-lchild; p=s-top; (*Visit)(p); p=p-rchild; void PostOrderNRTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree p,s1100; /s1栈存放结点 int b,top=0,s2100;/s2栈存放进栈标志 p=T; do while

11、(p) s1top = p; s2top+ = 0; /第一次进栈标志为0 p=p-lchild; if(top0) b=s2-top; p=s1top; if(b=0) s1top=p;s2top+=1; /第二次进栈标志为1 p=p-rchild; else (*Visit)(p); p=NULL; while(top0);/先序非递归遍历二叉树先序非递归遍历二叉树Status PreOrderNoRecursionTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree stackMaxSize,p; int top; if(T) top=0

12、; /根结点入栈根结点入栈 stacktop+=T; while(top0) /栈不为空时循环栈不为空时循环 p=stack-top;/退栈并访问该结点退栈并访问该结点 (*Visit)(p); if(p-rchild)/右孩子入栈右孩子入栈stacktop+=p-rchild; if(p-lchild)/左孩子入栈左孩子入栈stacktop+=p-lchild; return OK; 当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;其中: 0 lchild 域指示结点

13、的左孩子 ltag=ltag= 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag=rtag= 1 rchild 域指示结点的后驱 以这种结构构成的二叉链表作为二叉树的存储结构,叫做,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为.rchildrtagdataltaglchild/-二叉树的二叉线索存储表示-typedef enumLink,ThreadPointerTag; /Link:指针,Thread:线索typedef struct BiThrNode TElemType data; struct BiTreeNode *lchild,*r

14、child; PointerTag LTag, Rtag;BiTreeNode,*BiThrTree; 一般地，在二叉树的线索链表上添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点lchild域指针和最后一个结点rchild域的指针均指向头结点;就像为二叉树建立了一个双向线索链表。Status InorderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType)/T指向头结点,头结点的左链lchild指向根结点/中序遍历二叉线索树T的非递归算法

15、,对每个数据元素调用函数Visit P=Tlchild; while(p!=T) while(p LTag = Link) p=plchild; if(!Visit(p data) return ERROR; while(p RTag = =Thread&p rchild!=T) p=p rchild; Visit(p data); p= prchild; return OK;/InorderTraverse_ThrStatus InOrderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍历二叉树，并线索化，Thrt指向头结点 if(!(T

16、hrt =(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt LTag = Link; Thrt RTag = Thread; Thrt rchild = Thrt; if(!T) Thrt lchild = Thrt; else Thrt lchild=T; pre=Thrt; InThrTreading(T); pre rchild=Thrt; pre RTag =Thread; Thrt rchild=pre; return OK;/InOrderThreading void InThreading(BiThrTree p)

17、if(p) InThreading(p lchild); if(!p lchild)p LRag =Thread; p lchild=pre; if(!pre rchild) pre RRag =Thread;pre rchild=p; pre=p; InThreading(p rchild); 用数组存储树的结点,每个结点中附设一个字段指示其父结点的位置。012345678A-1B0C0D0E1F1G3H6I6ABCDEFHIG/-树的双亲表存储表示-#define MAX_TREE_SIZE 100typedef struct PTNode /树中结点的结构 TElemType data;

18、 int parent; /结点的双亲位置域PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int r,n; /根的位置和结点数PTree, *PPTree;：容易找到父结点及其所有的祖先；也能找到结点的子女和兄弟(比较麻烦)。但没有表示出结点之间的左右次序，所以无法求树中某个指定结点的最左子结点和右兄弟结点等基本运算。:按某种遍历次序在数组中存放结点。较常见的方法是依次存放树的先根序列。datachild1child2 childkA BCDEFG HIABCDEFHIG1.k叉树结点表示(固定长结点）datadegreechild1chil

19、d2 childkA 3 B 2C 0D 1E0F 0G 2 H 0I0ABCDEFHIG1.k叉树结点表示(固定长结点）2.变长结点表示012345678ABCDEFGHI78456ABCDEFHIG1.k叉树结点表示(固定长结点）2.变长结点表示3.孩子链表表示/-树的孩子链表存储表示-typedef struct EdgeNode/孩子链表中结点的结构 int child; struct EdgeNode *next;EdgeNode;typedef struct /结点表中结点的结构 TElemType data; struct EdgeNode *firstchild; /孩子链表头

20、指针CTNode;typedef struct /树结构 CTNode nodesMAX_TREE_SIZE; int r,n; /根的位置和结点数CTree, *PCTree;012345678ABCDEFGHI123 78 45 6 012345678-1A 0B 0C 0D 1E 1F 3G 5H 5I带双亲的带双亲的ABCDEFHIG data firstchildnextsiblingA B C D E F G H I ABCDEFHIG结点: 数据 孩子 兄弟 data firstchildnextsiblingA B C D E F G H I 结点: 数据 孩子 兄弟ABCDE

21、FHIG/-树的二叉链表(孩子兄弟)存储表示-typedef struct CSNodeTElemTypedata;struct CSNode*firstchild,*nextsibling;CSTree, *PCSTree;可以分为三步：(1)连线：相邻兄弟之间连线。 (2)抹线：抹掉双亲与孩子(除左孩子)之间的连线。 (3)旋转：将树作适当的旋转。例：画出如下图所示的树所对应的二叉树。123457681234576812345768(1)将森林中每一棵树分别转换成二叉树 (2)合并:使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子

22、树，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。ABCDEFGHIABCDEFGHIABCDEFGHI例：画出如下图所示的森林所对应的二叉树。(1) 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、 都与该结点的双亲结点连线。(2)删除原二叉树中所有双亲结点与右孩子结点的连线。(3)整理由(1)、(2)两步所得的树或森林，使之结构层次分明。ABCDEFGABCDEFGABCDEFGABCDEFG例：将如下图所示的二叉树还原为森林。 在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历， 即树和森林只有先根(序)遍历和后根(序)遍历

23、。(1)树的先序遍历 若树非空，则先访问根结点，然后依次先序遍历各子树。 (2)森林的先序遍历 若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、直到最后一棵树。(1)树的后序遍历 若树非空，则依次后序遍历各子树，最后访问根结点。 (2)森林的后序遍历 依次后序遍历森林中的每一棵树。 基本术语基本术语从树中某结点到其子孙结点之间的分支构成这两个结点之间的路径。路径上的分支数目。从根结点到第L层结点的路径长度为L-1。从树根到各结点的路径长度之和。完全二叉树是路径长度最短的二叉树。 若将树中各结点赋予一个具有某种含义的数值，则该数值称为该。从根

24、结点到该结点之间的路径长度与该结点的权的乘积。 所有叶子结点的带权路径长度之和，记为WPL=。 mkkklw1D到H的路径 DGHD到H路径的长为2 A到H的路径 ADGHA到H路径的长为3树的路径长度 =1+1+1+2+2+2+3+3=15n个结点的二叉树路径长度最小的是完全二叉树ABCDEFHIGABCDEFGHI每个叶子结点都带权的二叉树叫带权二叉树7524叶结点C的权为7，根结点A到C走7次的路径长度称为A到C的带权路径的长根到每个叶的带权路径的长的总和叫二叉树的带权路径的长本树带权路径的长=7*3+5*2+2*3+4*3=49 带权路径的长WPL= wklkk=1n n个叶子结点权值

25、分别为w1,w2,wn的二叉树中，带权路径长度WPL最小的二叉树。52745274WPL=49WPL=(7+5+2+4)*2 =3652475247WPL=36WPL=7+5*2+2*3+4*3 =35赫夫曼树带权路径长度的例子带权路径长度的例子将百分制转换成五级计分制 if(a60) b=E; else if(a70) b=D; else if(a80) b=C; else if(a90) b=B; else b=A;a60b=Ea70b=Da80b=Ca90b=Bb=A100个学生中5个不及格15个60几分40个70几分30个80几分10个90几分515403010需比较5+2*15+3*

26、40+4*30+4*10=315次a60b=Ea70b=Da80b=Ca90b=Bb=A5154030a80b=Ca90b=Bb=Aa60b=Ea70b=Dif(a80) if(a70) if(a60)b=E; else b=D; else b=C;else if(a n，则说明找到了合适的解 */if( i n)OutputBoardStatus();elsefor(j = 1; j = n)+total;OutPut();elsefor(j=0; j n; j+)chessij=1;if(CheckBoard()Queen(i+1,n);chessij=0;例如，如右图所示的树结构,可用二元组表示为：K=A，B，C，D，E，F，G，H，I，