数据结构教学课件：第六讲3二叉树

1、F二叉树建立算法 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C D E G F A B C D E F G JD *crt_bt_pre(JD *bt) char ch; printf(ch=); scanf(%c,&ch); if(ch= ) bt=NULL; else bt=(JD *)malloc(sizeof(JD); bt-data=ch; bt-lchild=crt_bt_pre(bt-lchild); bt-rchild=crt_bt_pre(bt-rchild); return(bt);用递归的方法计算二叉树的节点数遍历算法相关的应用求二叉树中叶子节

2、点的数目求二叉树的深度二叉树左右子树互换u线索二叉树F定义： 前驱与后继前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为 线索线索：指向前驱或后继结点的指针称为 线索二叉树线索二叉树：加上线索的二叉链表表示的二叉树叫 线索化线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫F实现 在有n个结点的二叉链表中必定有n+1个空链域 在线索二叉树的结点中增加两个标志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驱 rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后继 结点定义：typedef struct node

3、int data; int lt, rt; struct node *lc, *rc;JD; lc lt data rt rcABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 11ABCDE A B D C ET中序序列：BCAED中序线索二叉树0000111111ABCDE A B D C ET后序序列：CBEDA后序线索二叉树0000111111ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 1头结点：lt=0, lc指向根结点rt=1, rc指向遍历序列中最后一个结点遍历序列中第

4、一个结点的lc域和最后一个结点的rc域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉树0000111111ABCDEt 0 1prpiP-AJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NUL

5、L) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); A B D C Ebt0000000000中序线索二叉树ABCDE A B D C Ebtt 0 1prpiP-AP-BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t;

6、else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000000000ABCDE A B D C Ebtt 0 1prP=NULLiP-AP-BJD *zxxsh(JD *bt) JD *p,*p

7、r,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-

8、rc=pr; return(t);0000000000ABCDE A B D C Ebtt 0 1prPiP-A输出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr;

9、if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00000000001ABCDE A B D C Ebtt 0 1prP输出:BiP-AP-CJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while

10、(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000100000ABCDE A B D C Ebtt 0 1prP=NULLiP-AP-C输出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)mal

11、loc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000100000Ch5

12、_20.cABCDE A B D C Ebtt 0 1prPiP-A输出: B C JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-

13、rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00001000001ABCDE A B D C Ebtt 0 1prP=NULLiP-A输出: B C JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si

14、+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000100010ABCDE A B D C Ebtt 0 1prPi输出: B C A JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t

15、-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00001000101 遍历中序线索二叉树在中序线索二叉树中

16、找结点后继的方法：（1）若rt=1, 则rc域直接指向其后继（2）若rt=0, 则结点的后继应是其右子树的左链尾（lt=1)的结点在中序线索二叉树中找结点前驱的方法：（1）若lt=1, 则lc域直接指向其前驱（2）若lt=0, 则结点的前驱应是其左子树的右链尾（rt=1)的结点ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 1n二叉树的应用u哈夫曼树(Huffman)带权路径长度最短的树F定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的 路径长度：路径上的分支数 树的路径长度：从树根到每一个结点的路径长度之和 树的带权路径长度：树中所有带权结点的路径长度之和结点到根的路径长度权值其中：记作：kknkkklwlwwpl1 Huffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd