树教学内容.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,树,基本术语,结点(node)表示树中的元素，包括数据项及若干指向其子树的分支,结点的度(degree)结点拥有的子树数,叶子(leaf)度为0的结点,孩子(child)结点子树的根称为该结点的孩子,双亲(parents)孩子结点的上层结点叫该结点的,兄弟(sibling)同一双亲的孩子,树的度一棵树中最大的结点度数,结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层,深度(depth)树中结点的最大层次数,森林(forest)m(m,0),棵互不相交的树的集合,树中同一层各结点从左至右看成是有序的（即不能互换），则称该树为有序树，否则称为无序树。,A,B,C,D,E,F,G,H,I,J,K,L,M,结点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为兄弟,结点K，L为兄弟,树的度：3,结点A的层次：1,结点M的层次：4,树的深度：4,结点F，G为堂兄弟,结点A是结点F，G的祖先,5.2 二叉树,定义,定义：二叉树是n(n,0),个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成,特点,每个结点至多有二棵子树(即不存在度大于2的结点),二叉树的子树有左、右之分，且其次序不能任意颠倒,基本形态,A,只有根结点,的二叉树,空二叉树,A,B,右子树为空,A,B,左子树为空,A,B,C,左、右子树,均非空,几种特殊形式的二叉树,满二叉树,定义：,特点：每一层上的结点数都是最大结点数,完全二叉树,定义：深度为k，,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为,特点,叶子结点只可能在层次最大的两层上出现,对任一结点，若其右分支下子孙的最大层次为l，,则其左分支下子孙的最大层次必为l 或l+1,1,2,3,11,4,5,8,9,12,13,6,7,10,14,15,1,2,3,11,4,5,8,9,12,6,7,10,1,2,3,4,5,6,7,1,2,3,4,5,6,二叉树性质,性质2：深度为k,的二叉树至多有 个结点(k,1),性质3：对任何一棵二叉树T，,如果其终端结点数为n0，,度为2的结点数为n2，则n0=n2+1,性质4：具有n个结点的完全二叉树的深度为,性质5：如果对一棵有n,个结点的完全二叉树的结点按层序编号，则对任一结点i(1,in)，,有：,(1)如果i=1，,则结点i是二叉树的根，无双亲；如果i1，则其双亲是,i/2,(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i,(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,二叉树性质,性质1：,证明：用归纳法证明之,i=1,时，只有一个根结点，是对的,假设对所有j(1,jdata=ch;/生成根结点CreateBiTree(T-lchild);/生成左子树CreateBiTree(T-rchild);/生成右子树returnOK;/CreateBiTree,三叉链表,typedef struct node,TElemType,data;,struct node *lchild,*rchild,*parent;,JD;,lchild data parent rchild,A,B,C,D,E,F,G,A,B,C,D,E,F,G,5.4 树和二叉树的遍历,树的遍历,遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列,常用方法,先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树,后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点,按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n,层的结点,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,先序遍历：,后序遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,二叉树的遍历,方法,先序遍历：先访问根结点,然后分别先序遍历左子树、右子树,中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树,后序遍历：先后序遍历左、右子树，然后访问根结点,按层次遍历：从上到下、从左到右访问各结点,D,L,R,LDR,、,LRD,、,DLR,RDL、RLD、DRL,先序遍历,void PreOrderTraverse(BiTNode*Node),if(Node!=NULL),printf(%c,Node-data);,PreOrderTraverse(Node-lchild);,PreOrderTraverse(Node-rchild);,A,D,B,C,D L R,A,D L R,D L R,B,D,C,D L R,先序遍历序列：A B D C,先序遍历:,中序遍历,void InOrderTraverse(BiTNode*Node),if(Node!=NULL),InOrderTraverse(Node-lchild);,printf(%c,Node-data);,InOrderTraverse(Node-rchild);,A,D,B,C,L D R,B,L D R,L D R,A,D,C,L D R,中序遍历序列：B D A C,中序遍历:,后序遍历,void PostOrderTraverse(BiTNode*Node),if(Node!=NULL),PostOrderTraverse(Node-lchild);,PostOrderTraverse(Node-rchild);,printf(%c,Node-data);,A,D,B,C,L R D,L R D,L R D,A,D,C,L R D,后序遍历序列：D B C A,后序遍历:,B,-,+,/,a,*,b,-,e,f,c,d,先序遍历,：,中序遍历：,后序遍历：,层次遍历,：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,编程练习,求二叉树的深度,求二叉树中叶子结点的数目,交换所有结点的左右子树,求二叉树的深度,int depth(BiTNode*Node),int dep1,dep2;,/若T为空树，则深度为0，,/否则其深度等于左子树或右子树的最大深度加1,if(Node=NULL),return 0;,else,dep1=depth(Node-lchild);,dep2=depth(Node-rchild);,return dep1dep2?dep1+1:dep2+1;,求二叉树中叶子结点的数目,int LeafCount(BiTNode*Node),if(Node=NULL)return 0;,/空树没有叶子,else if(!Node-lchild,/叶子结点,else,return LeafCount(Node-lchild)+LeafCount(Node-rchild);,/左子树的叶子数加上右子树的叶子数,/LeafCount_BiTree,交换所有结点的左右子树,void Bitree_Revolute(BiTNode*Node),BiTNode*NodeTemp;,NodeTemp=Node-rchild;,Node-rchild=Node-lchild;,Node-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);,A,C,B,D,T,B,printf(B);,pre(T L);,B,T,A,printf(A);,pre(T L);,A,T,D,printf(D);,pre(T L);,D,T,C,printf(C);,pre(T L);,C,返回,T,左是空返回,pre(T R);,T,左是空返回,T,右是空返回,T,左是空返回,T,右是空返回,pre(T R);,先序序列：,A B D C,1)中序遍历的非递归算法,算法:,Status,InOrderTraverse(BiTree T,Status,(*Visit)(TElemType e),InitStack(S);/置空栈,p=T;/变量P代替根结点T，起保护根的作用,while,(p,!StackEmpty(s),/当结点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),在设计算法前，我们先分析一下后序遍历,与其它遍历有何不同。从先、中序遍历,过程中可以看出每个结点都只需进一次栈。,但，后序遍历的过程中每个结点都必须进,两次栈。第一次进栈保存是为了,遍历该结点的左子树；第二次进栈,保存是为了遍历该结点的右子树；,只有结点第二次从栈中退出时，,才能访问该结点。因而，必须设置,能区分结点两次进栈的标志。设置,标志的方法不是唯一的，在实际应,用中一般都在栈中设置标志位B。,（A）0,A,B C,D E F,G H,I J,（D）0,（B）0,ADR B,当某结点第一次进栈时，其标志位置0，第二次进栈时，其标志位置1。当从栈中退出某结点时，同时将其标志位的值退出。然后，通过判别从栈中退出的标志位的值是0、还是1，来决定是否能访问当前结点。是1，则访问该结点。是0，则再将结点进栈，同时，,将标志为置1。如右图6.14D进栈后，应遍历其左子树，但D无左孩子。,ADR B ADR B,此时将结点D与其标志位值0从栈中退出。经过判别不能访问，则将D再次进栈，同时把其标志位置1。然后，遍历D的右子树。,后序遍历的非递归算法:,（A）0,（I）0,A,B C,D E F,G H,I J,（D）1,（G）0,（B）0,（A）0,（D）0,（B）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)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,非递归算法,A,B,C,D,E,F,G,p,i,P-A,(1),A,B,C,D,E,F,G,p,i,P-A,P-B,(2),A,B,C,D,E,F,G,p,i,P-A,P-B,P-C,(3),p=NULL,A,B,C,D,E,F,G,i,P-A,P-B,访问：C,(4),p,A,B,C,D,E,F,G,i,P-A,访问：C B,(5),A,B,C,D,E,F,G,i,P-A,P-D,访问：C B,p,(6),A,B,C,D,E,F,G,i,P-A,P-D,P-E,访问：C B,p,(7),A,B,C,D,E,F,G,i,P-A,P-D,访问：C B E,p,(8),A,B,C,D,E,F,G,i,P-A,P-D,P-G,访问：C B E,P=NULL,(9),A,B,C,D,E,F,G,i,P-A,访问：C B E G D,p,(11),A,B,C,D,E,F,G,i,P-A,P-F,访问：C B E G D,p,(12),A,B,C,D,E,F,G,i,P-A,P-D,访问：C B E G,p,(10),A,B,C,D,E,F,G,i,P-A,访问：C B E G D F,p=NULL,(13),A,B,C,D,E,F,G,i,访问：C B E G D F A,p,(14),A,B,C,D,E,F,G,i,访问：C B E G D F A,p=NULL,(15),Ch5_4.c,Ch5_40.C,后序遍历非递归算法,层次遍历,StatusLevelOrder(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);/左子树非空，则入队列If(b-rchold!=Null)EnQueue(Q,b-rchild);/右子树非空，则入队列/while/ifLevelOrder,两棵树相似,若已知两棵二叉树B1和B2皆为空，或者均不为空且B1的左右子树和B2的左右子树分别相似，则称二叉树B1和B2相似。,判断两棵树是否相似的递归算法,int Bitree_Sim(Bitree B1,Bitree B2),if(!B1/Bitree_Sim,先序遍历二叉树的非递归算法,void PreOrder_Nonrecursive(Bitree T）InitStack(S);Push(S,T);/根指针进栈while(!StackEmpty(S)while(Gettop(S,p)/向右一步/while/PreOrder_Nonrecursive,求二叉树T中结点p和q的最近共同祖先,int found=FALSE;,Bitree*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/Find_Near_Ancient,void 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/回溯/Findpath,判断二叉树是否完全二叉树,是则返回1,否则返回0,int 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分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.,遍历算法应用,按先序遍历序列建立二叉树的二叉链表，已知先序序列为：,A B C,D E G F ,求二叉树深度算法,Ch5_5.c,ch5_6.c,A,B,C,D,E,F,G,A ,B,C ,D,E,F ,G ,Ch5_1.c,统计二叉树中叶子结点个数算法,5.5 二叉树的应用,哈夫曼树(Huffman)带权路径长度最短的树,定义,路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的,路径长度：路径上的分支数,树的路径长度：从树根到每一个结点的路径长度之和,树的带权路径长度：树中所有带权结点的路径长度之和,Huffman,树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫,例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,a,b,c,d,7,5,2,4,WPL=,7,*2+,5,*2+,2,*2+,4,*2=36,d,c,a,b,2,4,7,5,WPL=,7,*3+,5,*3+,2,*1+,4,*2=46,a,b,c,d,7,5,2,4,WPL=,7,*1+,5,*2+,2,*3+,4,*3=35,构造Huffman,树的方法Huffman算法,构造Huffman,树步骤,根据给定的n,个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj,在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和,在森林中删除这两棵树，同时将新得到的二叉树加入森林中,重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树,例,a,7,b,5,c,2,d,4,a,7,b,5,c,2,d,4,6,a,7,b,5,c,2,d,4,6,11,a,7,b,5,c,2,d,4,6,11,18,例 w=5,29,7,8,14,23,3,11,5,14,29,7,8,23,3,11,14,29,7,8,23,11,3,5,8,8,7,15,14,29,23,3,5,8,11,11,3,5,8,19,14,29,23,8,7,15,11,3,5,8,19,29,23,14,8,7,15,29,29,14,8,7,15,29,11,3,5,8,19,23,42,11,3,5,8,19,23,42,29,14,8,7,15,29,58,11,3,5,8,19,23,42,29,14,8,7,15,29,58,100,Huffman算法实现,Ch5_8.c,一棵有n,个叶子结点的Huffman树有,2n-1,个结点,采用顺序存储结构一维结构数组,结点类型定义,typedef struct,unsigned int weight;,unsigned int parent,lchild,rchild;,HTNode;/*树中结点的结构*/,typedef struct,char data;/*待编码的字符*/,int weight;/*字符的权值 */,char codeN;/*字符的编码*/,HTCode;,lc data rc pa,1 2 3 4 5 6 7,0 0 0 0 0 0 0,7 5 2 4 0 0 0,0 0 0 0 0 0 0,0 0 0 0 0 0 0,(1),lc data rc pa,1 2 3 4 5 6 7,0 0 0 0,3,0 0,7 5 2 4,6,0 0,0 0 0 0,4,0 0,0 0 5,5,0 0 0,k,x1=3,x2=4,m1=2,m2=4,(2),lc data rc pa,1 2 3 4 5 6 7,0 0 0 0 3,2,0,7 5 2 4 6,11,0,0 0 0 0 4,5,0,0,6,5 5,6,0 0,k,x1=2,x2=5,m1=5,m2=6,(3),lc data rc pa,1 2 3 4 5 6 7,0 0 0 0 3 2 1,7 5 2 4 6 11 18,0 0 0 0 4 5,6,7,6 5 5 6,7,0,k,x1=1,x2=6,m1=7,m2=11,(4),Ch5_8.c,Huffman,树应用,最佳判定树,等级,分数段,比例,A,B,C,D,E,059,6069,7079,8089,90100,0.05,0.15,0.40,0.30,0.10,a60,a90,a80,a70,E,Y,N,D,Y,N,C,Y,N,B,Y,N,A,70,a80,a60,C,Y,N,B,Y,N,D,Y,N,E,Y,N,A,80,a90,60,a70,E,A,D,E,C,a80,a70,a60,aA,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;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,E,bt,0,0,0,0,0,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,p,i,P-A,P-B,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,0,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P=NULL,i,P-A,P-B,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,0,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,i,P-A,输出:,B,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,0,0,0,0,0,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,输出:,B,i,P-A,P-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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P=NULL,i,P-A,P-C,输出:,B,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,i,P-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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,0,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P=NULL,i,P-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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,i,输出:,B C A,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,1,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A,pr,P-D,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A,pr,P-D,P-E,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P=NULL,i,输出:,B C A,pr,P-D,P-E,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A E,pr,P-D,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P=NULL,i,输出:,B C A E,pr,P-D,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;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A E D,pr,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;,