遐想网络纯净驱动版A五章树ppt课件

1、第五章第五章 树树 树是一类重要的非线性数据构造，是以分支关系定义的层次构造5.1 树的定义定义定义：树(tree)是n(n0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n1时，其他结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点根树中各子树是互不相交的集合A只需根结点的树ABCDEFGHIJKLM有子树的树根子树l根本术语l结点(node)表示树中的元素，包括数据项及假设干指向其子树的分支l结点的度(degree)结点拥有的子树数l叶子(leaf)度为0的结点l孩子(ch

2、ild)结点子树的根称为该结点的孩子l双亲(parents)孩子结点的上层结点叫该结点的l兄弟(sibling)同一双亲的孩子l树的度一棵树中最大的结点度数l结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层l深度(depth)树中结点的最大层次数l森林(forest)m(m0)棵互不相交的树的集合l树中同一层各结点从左至右看成是有序的即不能互换，那么称该树为有序树，否那么称为无序树。ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟

3、结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先l5.2 二叉树l定义l定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成l特点l每个结点至多有二棵子树(即不存在度大于2的结点)l二叉树的子树有左、右之分，且其次序不能恣意颠倒l根本形状A只需根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空l几种特殊方式的二叉树l满二叉树l定义：12个结点的二叉树称为且有一棵深度为kk特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n

4、个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为特点叶子结点只能够在层次最大的两层上出现对任一结点，假设其右分支下子孙的最大层次为l，那么其左分支下子孙的最大层次必为l 或l+11231145891213671014151231145891267101234567123456二叉树性质) 1(211iii个结点层上至多有：在二叉树的第性质性质2：深度为k的二叉树至多有 个结点(k1)12 k性质3：对任何一棵二叉树T，假设其终端结点数为n0， 度为2的结点数为n2，那么n0=n2+1性质4：具有n个结点的完全二叉树的深度为1log2n性质5：假设对一

5、棵有n个结点的完全二叉树的结点按层序编号，那么对任一结点i(1in)，有： (1) 假设i=1，那么结点i是二叉树的根，无双亲；假设i1，那么其双亲是i/2 (2) 假设2in，那么结点i无左孩子；假设2in，那么其左孩子是2i (3) 假设2i+1n，那么结点i无右孩子；假设2i+1n，那么其右孩子是2i+1l二叉树性质l性质1：) 1(21iii个结点层上至多有在二叉树的第证明：用归纳法证明之 i=1时，只需一个根结点， 是对的 假设对一切j(1jdata=ch;/生成根结点CreateBiTree(T-lchild);/生成左子树CreateBiTree(T-rchild);/生成右子树

6、returnOK;/CreateBiTree三叉链表typedef struct nodeTElemType data; struct node *lchild, *rchild, *parent;JD;lchild data parent rchildABCDEFG A B C D E F Gl5.4 树和二叉树的遍历l树的遍历l遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完好而有规律的走法，以得到树中一切结点的一个线性陈列l常用方法l先根序遍历：先访问树的根结点，然后依次先根遍历根的每棵子树l后根序遍历：先依次后根遍历每棵子树，然后访问根结点l按层次遍历：先访问第一层

7、上的结点，然后依次遍历第二层，第n层的结点ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNOl二叉树的遍历l方法l先序遍历：先访问根结点,然后分别先序遍历左子树、右子树l中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树l后序遍历：先后序遍历左、右子树，然后访问根结点l按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL先序遍历void PreOrderTraverse(BiTNode *No

8、de)if(Node!=NULL)printf(%c,Node-data);PreOrderTraverse(Node-lchild);PreOrderTraverse(Node-rchild);ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:中序遍历void InOrderTraverse(BiTNode *Node)if(Node!=NULL)InOrderTraverse(Node-lchild);printf(%c,Node-data);InOrderTraverse(Node-rchild);ADBCL D RBL D RL D RADC

9、L D R中序遍历序列：B D A C中序遍历:后序遍历void PostOrderTraverse(BiTNode *Node)if(Node!=NULL)PostOrderTraverse(Node-lchild);PostOrderTraverse(Node-rchild);printf(%c,Node-data);ADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d

10、/e f编程练习编程练习l求二叉树的深度l求二叉树中叶子结点的数目l交换一切结点的左右子树求二叉树的深度求二叉树的深度int depth(BiTNode *Node)int dep1,dep2;/假设T为空树，那么深度为0，/否那么其深度等于左子树或右子树的最大深度加1if(Node=NULL) return 0;else dep1=depth(Node-lchild); dep2=depth(Node-rchild); return dep1dep2?dep1+1:dep2+1; 求二叉树中叶子结点的数目求二叉树中叶子结点的数目int LeafCount(BiTNode *Node) if(

11、Node=NULL) return 0; /空树没有叶子else if(!Node-lchild&!Node-rchild) return 1; /叶子结点else return LeafCount(Node-lchild)+LeafCount(Node-rchild); /左子树的叶子数加上右子树的叶子数/LeafCount_BiTree 交换一切结点的左右子树交换一切结点的左右子树void Bitree_Revolute(BiTNode *Node) BiTNode *NodeTemp;NodeTemp=Node-rchild;Node-rchild=Node-lchild;Nod

12、e-lchild=NodeTemp; /交换左右子树if(Node-lchild) Bitree_Revolute(Node-lchild);if(Node-rchild) Bitree_Revolute(Node-rchild); /左右子树再分别交换各自的左右子树/Bitree_Revolute void preorder(BiTNode *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )前往前往pre(T R);前往前往pre(T R);ACBDTB

13、printf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C前往T左是空前往pre(T R);T左是空前往T右是空前往T左是空前往T右是空前往pre(T R);先序序列：A B D C1)中序遍历的非递归算法算法:Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e) InitStack(S); / 置空栈 p = T ; / 变量P替代根结点T，起维护根的作用 while ( p ! StackEmpty(s) /

14、当结点P存在或栈S不空时反复 if (p) Push( S, P ); P = P-Lchild; else P为空 Pop(s, p ) ; / 栈不空，退栈 if (! Visit (P-data) return ERROR; / 假设P不存在那么错 P = P- rchild ; / 得到右孩子结点，遍历右子树 /while return OK;2)后序遍历的非递归算法 (S)在设计算法前，我们先分析一下后序遍历与其它遍历有何不同。从先、中序遍历过程中可以看出每个结点都只需进一次栈。但，后序遍历的过程中每个结点都必需进两次栈。第一次进栈保管是为了遍历该结点的左子树；第二次进栈保管是为了遍

15、历该结点的右子树；只需结点第二次从栈中退出时，才干访问该结点。因此，必需设置能区分结点两次进栈的标志。设置标志的方法不是独一的，在实践应用中普通都在栈中设置标志位B。 A 0 A B C D E F G H I JD 0B 0ADR B当某结点第一次进栈时，其标志位置0，第二次进栈时，其标志位置1。当从栈中退出某结点时，同时将其标志位的值退出。然后，经过判别从栈中退出的标志位的值是0、还是1，来决议能否能访问当前结点。是1，那么访问该结点。是0，那么再将结点进栈，同时，将标志为置1。如右图6.14D进栈后，应遍历其左子树，但D无左孩子。 ADR B ADR B 此时将结点D与其标志位值0从栈中

16、退出。经过判别不能访问，那么将D再次进栈，同时把其标志位置1。然后，遍历D的右子树。后序遍历的非递归算法: A 0 I 0 A B C D E F G H I JD 1G 0B 0A 0D 0B 0图6-15后序遍历的非递归Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e) IniStack(S); / 置空栈置空栈 p = T ; / 变量变量P替代根结点替代根结点T，起维护根的作用，起维护根的作用 while ( p ! StackEmpty(s) / 当结点当结点P存在或栈存在或栈S不空时反复不空时反复 if (p

17、) Push( S, P,B ) / P存在将存在将P进栈，进栈， B =0 P = P-Lchild; / 遍历左子树遍历左子树 else / P为空为空 Pop(s, p ,B) ; / 栈不空，退栈栈不空，退栈 if ( B=0) Push( S, P,B ); ( B = 1) P = P- rchild ; / 遍历右子树遍历右子树 else if (! Visit (P-data) return ERROR; / 假设假设P不存在不存在 ，那么错，那么错 P=null; /while return OK; PostorderTraverse非递归算法ABCDEFGpiP-A(1)A

18、BCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)ABCDEFGiP-A访问：C

19、 B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)Ch5_4.cCh5_40.C后序遍历非递归算法l层次遍历lStatusLevelOrder(BiTreeT)/按层次遍历二叉树T，Q为队列InitQueue(Q);If(T!=NULL)/假设树非空EnQueue(Q,T);/根结点入队列While(!QueueEmpty(Q)DeQueue(Q,b);/队首元素出队列Visit(b-data);/访问结点If(b-lchild!=NULL)EnQueue(Q,b-lchild)

20、;/左子树非空，那么入队列If(b-rchold!=Null)EnQueue(Q,b-rchild);/右子树非空，那么入队列/while/ifLevelOrder两棵树类似两棵树类似l假设知两棵二叉树B1和B2皆为空，或者均不为空且B1的左右子树和B2的左右子树分别类似，那么称二叉树B1和B2类似。判别两棵树能否类似的递归算法判别两棵树能否类似的递归算法lint Bitree_Sim(Bitree B1,Bitree B2)l if(!B1&!B2) return 1; else if(B1&B2&Bitree_Sim(B1-lchild,B2-lchild)&

21、;Bitree_Sim(B1-rchild,B2-rchild) return 1; else return 0;/Bitree_Sim 先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法lvoid PreOrder_Nonrecursive(Bitree T InitStack(S);Push(S,T); /根指针进栈while(!StackEmpty(S)while(Gettop(S,p)&p)visit(p-data);push(S,p-lchild); /向左走到尽头pop(S,p);if(!StackEmpty(S) pop(S,p); push(S,p-rchild);

22、/向右一步/while/PreOrder_Nonrecursive 求二叉树求二叉树T中结点中结点p和和q的最近共同祖先的最近共同祖先lint found=FALSE; lBitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q) Bitree pathp 100 ,pathq 100 /设立两个辅助数组暂存从根到p,q的途径Findpath(T,p,pathp,0);found=FALSE;Findpath(T,q,pathq,0); /求从根到p,q的途径放在pathp和pathq中for(i=0;pathpi=pathqi&path

23、pi;i+); /查找两条途径上最后一个一样结点return pathp-i;/Find_Near_Ancient lvoid Findpath(Bitree T,Bitree p,Bitree path ,int i)/求从T到p途径的递归算法if(T=p)found=TRUE;return; /找到pathi=T; /当前结点存入途径if(T-lchild) Findpath(T-lchild,p,path,i+1); /在左子树中继续寻觅if(T-rchild&!found) Findpath(T-rchild,p,path,i+1); /在右子树中继续寻觅if(!found)

24、pathi=NULL; /回溯/Findpath 判别二叉树能否完全二叉树判别二叉树能否完全二叉树,是那么前往是那么前往1,否那否那么前往么前往0lint IsFull_Bitree(Bitree T InitQueue(Q);flag=0;EnQueue(Q,T); /建立任务队列while(!QueueEmpty(Q)DeQueue(Q,p);if(!p) flag=1;else if(flag) return 0;elseEnQueue(Q,p-lchild);EnQueue(Q,p-rchild); /不论孩子能否为空,都入队列/whilereturn 1;/IsFull_Bitree

25、分析:该问题可以经过层序遍历的方法来处理.与6.47相比,作了一个修正,不论当前结点能否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个延续的不包含空指针的序列.反之,那么序列中会含有空指针. l遍历算法运用l按先序遍历序列建立二叉树的二叉链表，知先序序列为：l A B C D E G F 求二叉树深度算法Ch5_5.cch5_6.cABCDEFG A B C D E F G Ch5_1.c统计二叉树中叶子结点个数算法l5.5 二叉树的运用l哈夫曼树(Huffman)带权途径长度最短的树l定义l途径：从树中一个结点到另一个结点之间的分支构成这两个结点间的l途径长度：途径上的分支数

26、l树的途径长度：从树根到每一个结点的途径长度之和l树的带权途径长度：树中一切带权结点的途径长度之和结点到根的路径长度权值其中：记作：kknkkklwlwwpl1Huffman树设有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=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1l构造Huffman树的方法Huffman算法l

27、构造Huffman树步骤l根据给定的n个权值w1,w2,wn，构造n棵只需根结点的二叉树，令起权值为wjl在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和l在森林中删除这两棵树，同时将新得到的二叉树参与森林中l反复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 113588715142923358111135819142923871511358

28、1929 23148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法实现Ch5_8.c一棵有n个叶子结点的Huffman树有2n-1个结点采用顺序存储构造一维构造数组结点类型定义typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode; /*树中结点的构造*/typedef struct char data; /*待编码的字符*/ int weight; /*字符的权值 */ c

29、har codeN; /*字符的编码 */ HTCode;lc data rc pa1 2 3 4 5 6 70 0 0 0 0 0 07 5 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0(1)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0kx1=3,x2=4m1=2,m2=4(2)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0kx1=2,x2=5m

30、1=5,m2=6(3)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 17 5 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0kx1=1,x2=6m1=7,m2=11(4)Ch5_8.clHuffman树运用l最正确断定树等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60aAJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;

31、 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-rc=pr; re

32、turn(t); A B D C Ebt0000000000l算法l按中序线索化二叉树Ch5_20.cABCDE 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; 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=

33、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);0000000000l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1prP=NULLiP-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

34、) 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);0000000000l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1prPiP-A输出:

35、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; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=

36、NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00000000001l算法l按中序线索化二叉树Ch5_20.cABCDE 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(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i;

37、 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);0000100000l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1prP=NULLiP-AP-C输出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t

38、-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);0000100000l算法l按中序线索化二叉树Ch5_20.

39、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-rt=1

40、; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00001000001l算法l按中序线索化二叉树Ch5_20.cABCDE 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

41、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);0000100010l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1prPi输出: B C A JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;

42、 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-rc=pr; re

43、turn(t);00001000101l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1Pi输出: B C A prP-DJD *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

44、) 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);0000101010l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1Pi输出: B C A prP-DP-EJD *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=NUL

45、L) 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);0000101010l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1P=NULLi输出

46、: B C A prP-DP-EJD *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-rt=1; pr-rc=p; pr=p; p=p-r

47、c; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000101010l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1Pi输出: B C A E prP-DJD *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=

48、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);0000101010 1l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1P=NULLi输出: B C A E prP-DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=

49、(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-rc=pr; return(t);0000

50、101011l算法l按中序线索化二叉树Ch5_20.cABCDE A B D C Ebtt 0 1Pi输出: B C A E D prJD *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-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);00001010111l算法l按中序线索化二叉树Ch5_