1、 s=(BiTree)malloc(sizeof(BiNode);/申請結(jié)點s-data=ch;s-lchild=s-rchild=nul1;if(bst=null)bst=s;/根結(jié)點else/查找插入結(jié)點P=bst;while(p)if(chp-data)f=p;p=p-rchild;/沿右分枝查.f是雙親elsef=p;p=p-lchild;/沿左分枝査if(f-datarchild=s;elsef-lchild=s;/將s結(jié)點插入樹中scanf(%”,&ch);/讀入下一數(shù)據(jù)/while(ch!=常)Tetum(bst):/結(jié)束creatvoidInOrder(BiTreebst)/b

2、st是二叉排序樹，中序遍歷輸出二叉排洋樹if(bst)InOrder(bst-lchild);printf(bst-data);InOrder(bst-rchild):/結(jié)束InOrder41葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pr“初始為空。第一個葉子結(jié)點山指針hed指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild抬針指向它，最后葉子結(jié)點的rchild為空。LinkedListhead,pre=null:全局變雖LinkedListInOrder(BiTreebt)/中序遍歷二叉樹bt,將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為headif(bt)InOrd

3、er(bt-lchild);/中洋遍歷人:子樹if(bt-lchild=null&bt-rchild=null)/葉子結(jié)點if(pre=null)head=bt;pre=bt;/處理第一個葉子結(jié)點elsepre-rchild=bt;pre=bt;/將葉子結(jié)點鏈入鏈表InOrder(bt-rchiId);/中序遍歷右子樹Dre-rchild二null:/設(shè)置鏈表尾return(head);/InOrder時間復(fù)雜度為0(n),輔助變雖使用head和pre,棧空間復(fù)雜度0(n)層次遍歷算法26.voidInvertLevel(b訂reebt)/對二叉樹按自下至上.自右至左的進行層次遍歷if(bt!

4、=null)Stacklnit(s);棧初始化，棧中存放二叉樹結(jié)點的指針Queuelnit(Q);/隊列初始化。隊列中存放二叉樹結(jié)點的指針QueueIn(0.bt);*hile(!QueueEmDtv(Q)/從卜.而疋層次遍歷d二QueueOut(Q):Dush(s,d):/出隊，入棧if(D-lchild)QueueIn(Q,p-lchild);/若左子不空,則入隊歹Uif(D-rchild)Queuein(Q,p-rchild);/若右子不空,則入隊歹Uwhile(!StackEmD(s)p=pop(s);printf(p-data);/丫卜而匕從右到心的戻次i扁歷/if(bt!=null

5、)結(jié)束InvertLevel借助隊列和棧，最后彈岀棧中元素實現(xiàn)對二叉樹按IT下至上，白右至左的層次遍歷33計算每層中結(jié)點值大于50的結(jié)點個數(shù)，應(yīng)按層次遍歷。設(shè)一隊列Q,用front和rear分別指向隊頭和隊尾元素,last指向各層最右結(jié)點的位置。存放值大于50的結(jié)點結(jié)構(gòu)為_typedefstructintlevelsvalue,idx;node;/元素所在層號、值和本層中的序號nodea,s;voidValueGT50(B訂reebt)/査各層中結(jié)點值大于50的結(jié)點個數(shù)，輸出其值及序號if(bt!二null)intfront=0,last=l,rear=l,level=l,i=0,num=0;

6、/numi己50的結(jié)點個數(shù)BiTreeQ;Ql=bt;根結(jié)點入隊while(front=13st)bt=Qfrontl;if(bt-data50)s.1evel=level;s.idx二+i;s.value=bt-data;ajjnuml=s;if(bt-lchild!=null)orrear=bt-lchild:/左子女入隊列if(bt-rchiId!=nul1)QrearZ=bt-rchiId:/右子女入隊列if(front=last)last二rear;levels;i=0;/本層最后一個結(jié)點己處理完/初始化下層:last指向下層最右結(jié)點,層號加1,下層50的序號初始為0for(i=l；

7、il)層上葉子結(jié)點個數(shù)if(btHnull丨丨kl)return(0);B訂reep=bt,Q;/Q足隊列元素是二叉樹結(jié)點指針，容雖足夠大intfront=0,rear=l,leaf=0;/front和rear是隊頭和隊尾指針，leaf葉子結(jié)點數(shù)intlast=l.level=l:0二:/last是二叉樹同層最右結(jié)點的指針level是二叉樹的層數(shù)hile(front二rear)d二Q+front：:if(level=k&!D-lchild&!p-rchild)leaf+;/葉子結(jié)點1f(D-lchild)Q+r亡ar二p-lchild;/左子女入隊if(p-rchild)Qrearl=Drch

8、ild;/右子女入隊if(froni=last)level+*;last=rear;if(froni=last)level+*;last=rear;ifreturn(leaf);/二叉樹同層最右結(jié)點已處理，層數(shù)增1/last移到指向下層最右一元素層數(shù)大于k后退出運行/while/結(jié)束LeafKLevel45木題應(yīng)釆用層次遍歷方式。若樹不空，則二叉樹根結(jié)點入隊，然后當隊列不空且隊列長不超過m重復(fù)如下操作：岀隊，若出隊元素不為空，則記住其下標，且將其左右子女入隊列：若出隊元素為空，當作虛結(jié)點，也將其“虛子女”入隊列。為節(jié)省空間，就用樹T的順序存儲結(jié)構(gòu)Aln作隊列，隊頭指針front,隊尾指針rea

9、r,元素最大下標last.voidTraverse(BiTreebt,intn)/求二叉樹bt的順序存儲結(jié)構(gòu)Al.n,下標超過n報借，給出實際的最大下標BiTreeA,p;if(bt!二null)intfront=0,rear二1,last二1:Al=bt;while(fronterEar)p=AC+front;if(D)last=front;/出隊;用last記住最后一個結(jié)點的下標rear=2*front;/計算結(jié)點(包括虛結(jié)點)左子”下標AifM二叉樹的實際結(jié)點if(rearn)printf(c結(jié)點無左子”);elseArear=p-lchiId;if(rear+ln)printf(c結(jié)點

10、無右子”);elseArear=p-rchild;/p是虛結(jié)點if(rear=n)Arear=null;if(rear+l=n)Arear+l=null;/while(frontdata);/出隊，訪問結(jié)點if(D-lchild&!D-rchild!D-lchild&D-rchild)num+;/度為1的結(jié)點if(p-lchild)Queuein(Q.p-lchild);/非空左子入隊if(p-rchild)Queuein(Q,p-rchild);/非空右子入隊/lf(bt)return(num);返回度為1的結(jié)點的個數(shù)先序轉(zhuǎn)為后序算法火29對一般二叉樹，僅根據(jù)一個先序.中序、后序遍歷，不能確

11、定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均禽有數(shù)雖相等的結(jié)點，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列(即任一遍歷序列均可確定一棵二叉樹voidPreToPost(ElemTypepre,post,int11,hl,12,h2)將滿二叉樹的先序序列轉(zhuǎn)為后序序列，11,hl,12,h2是序列初始和最后結(jié)點的下標。if(hl=ll)posth2=prell:/扭結(jié)蟲.half=(hl-ll)/2;/左或右子樹的結(jié)點數(shù)PreToPost(pre,post,11+1,11+half,12,12+half-l)/將左子樹先序序列轉(zhuǎn)為后序序列PreToPost(pre,post,11+ha

12、lf+l,hl,12+half,h2-l)/將右子樹先序序列轉(zhuǎn)為后序序列/PreToPost中序后序算法30.BiTreeIntoPost(ElemTypein,post,lnt11,hl,12,h2)/in和post是二叉樹的中序序列和后序序列遞歸,11,hl,12,h2分別是兩序列第一和最后結(jié)點的下標BiTreebt=(BiTree)malloc(sizeof(BiNode);/申請結(jié)點bt-data=posth2:后序遍歷序列最肓一個元索楚捉結(jié)點數(shù)據(jù)for(i=ll;ilchild=null;/處理左子樹elsebt-lchild=IntoPost(in,post,il,i-1,12,1

13、2+iTlT):if(i=hl)bt-rchild=null;/處理右子樹elsebt-rchild=IntoPost(in,post,i+1,hl,h2-l);return(bt);38知二叉樹中序序列與后序序列，第30題以遞歸算法建立了二叉樹，本題是非遞歸算法。voidInPostCreat(ElemTypeIN,POST,int11,hl,12,h2)山二叉樹的中序序列IN匚和后序序列POST非遞歸建立二叉樹，初始調(diào)用時，11=12=1,hl二h2=n。typedefstructint11,hl,12,h2;BiTreet;node;nodes,p;/s為棧，容雖足夠夫BiTreebt=

14、(BiTree)malloc(sizeof(BiNode);inttop=0,i;p.11=11;p.hl=hl;p.12=12;p.h2=h2:p.t=bt;sltopl=p;/初始化while(torPO)p=sLtopJ:bt=p.t;ll=p.11;hl=p.hl;12=p.12;h2=p.h2;/取出棧頂數(shù)據(jù)for(i=ll；idata=P0STh2;/根結(jié)點的值if(i=ll)bt-lchild=null;/bt無左子樹else將建立左壬樹的數(shù)據(jù)入棧bt-lchild=(BiTree)malloc(sizeof(BiNode);p.t=bt-lchild;p.11=11;Dhl=i

15、-1;p.12=12;Dh2二12+i-ll-l;s+tOD】=D：if(i=hl)bt-rchild=null;/bt無右子樹elsebt-rchild=(BiTree)malloc(sizeof(BiNode):p.t=bt-rchild;D11二il:p.hl=hl;d12=12+i-ll:d.h2二h2-l:s十od二d:右子樹數(shù)據(jù)入棧/while(top0)結(jié)束InPostCreat先序中序算法37.voidPreInCreat(ElemTypeA,B,int11,hl,12,h2)由二叉樹前序序列Al.n和中序序列Bl.n建立二叉樹,11,hl,和12,h2分別為先序序列和/中序序

16、列第一和最后結(jié)點的下標初始調(diào)用時11=12=1,hl=h2=n。非遞歸typedefstructint11,hl,12,h2;BiTreet;node;BiTreebt;inttop=0,i:nodes,p;/s為棧，容量足夠大bt=(BiTree)malloc(sizeof(BiNode);/申請結(jié)點空間D11=11:Dhl二hl:d12=12:Dh2=h2:p.t=bt;s+1od=d:/初始化while(top0)p=sCtop:bt=p.t;ll=p11;hl二phl;12二p12;h2二ph2;/取出棧頂數(shù)據(jù)for(i=12;idata=All；/All為根結(jié)點的值if(i=12)b

17、t-lchild=null;/bt無龍子樹else/將建立左子樹的數(shù)拯入棧bt-lchild=(BiTr亡e)malloc(sizeof(BiNode);p.t=bt-lchild;d.11二11+1:d.hl=ll+i-12:p.12=12:p.h2=i-l;sltoDl=D：if(i=h2)bt-rchild=null;/bt無右子樹elsebt-rchild=(BiTre亡)malloc(sizeof(BiNode):p.t=bt-rchild;Dll=ll+i-12+l:p.hl=hl:d12二i+1:p.h2=h2;stonl=p;右子樹數(shù)據(jù)入棧/while結(jié)束當二叉樹為單支樹時，棧

18、深m當二叉樹左右子樹高相等時，棧深logno時間復(fù)雜度0(n)56.voidPrelnCreat(BiTreeroot,ElemTypepre,in,int11,hl,12,h2)遞歸/根據(jù)二叉樹前序序列pre和中序序列in建立二叉樹o11,hl,12,h2是序列第一和最后元素下標。root=(BiTree)meilloc(sizeo:f(BiNode):/申請結(jié)點root-data=pre11;/pre11址根for(i=12;ilchild=null;/無冷子樹elsePrelnCreat(root-lchildpre,in,11+1,ll+(i-12),12,iT)；/遞歸建立用子樹if

19、(i=h2)root-rchild=null;/無右子樹elsePrelnCreat(root-rchiId,pre,in,ll+(i-12)+l.hl,i+1,h2)/遞歸題立右子樹/結(jié)束PrelnCreat層次中序算法80.二叉樹的層次遍歷序列的第一個結(jié)點是二叉樹的根。實際上，層次遍歷序列中的每個結(jié)點都是“局部根J確定根后.到二叉樹的中序序列中，査到該結(jié)點，該結(jié)點將二叉樹分為“左根右”三部分。若左、右子樹均有，則層次序列根結(jié)點的后而應(yīng)是左右子樹的根：若中序序列中只有左子樹或只有右子樹，則在層次序列的根結(jié)點后也只有左子樹的根或右子樹的根。這樣，定義一個全局變雖指針R，指向?qū)哟涡蛄写幚碓亍?/p>

20、算法中先處理根結(jié)點，將根結(jié)點和左右子女的信息入隊列。然后，在隊列不空的條件下，循環(huán)處理二叉樹的結(jié)點。隊列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstructintlvl;intl,h;intf;intlr;qnode;/層次序列指針，總是指向當前“根結(jié)點”在層次序列中的位呂/中序序列的下上界/層次序列中當前根結(jié)點”的雙親結(jié)點的指針/1一雙親的左子樹2雙親的右子樹BiTreeCreat(datatypein,levelC,intn)/III二叉樹的層次序列l(wèi)evn和中序序列inn生成二叉樹：n是二叉樹的結(jié)點數(shù)if(ndata=levelO;p-lchild=null;p-rchild=null;

21、/填寫該結(jié)點數(shù)據(jù)for(i=0;ilchild=null;s.lvl=+R;s.1二i+1:s.h=n-l:s.f=p：s.lr=2;enqueue(0s):elseif(i=nl)/根結(jié)點無右子樹,遍歷序列的1一n-1是左子樹p-rchild=null;s.lvl=+R;s.l=l;s.h=i-l;sf=p；s.lr=l;enaueue(Q,s):/根結(jié)點有怎子樹和右子樹s.lvl=+R;s.1=0:sh=i-l:sf=p；s.lr=l;enaueue(0.s):幻子樹有關(guān)信息入隊列s.lvl=+R;s.l=i+l;sh=n-l;sf=p；s.lr=2;enqueue(Q,s):/右子樹有關(guān)

22、信息入隊列Sdle(匕/當隊列不空，講行循環(huán)構(gòu)造二叉樹的左右子樹s=delQueue(Q):father二sf;for(i=s.1;idata=levels.lvl;p-lchild=null;p-rchild=null;/填寫該結(jié)點數(shù)據(jù)if(s.lr=l)father-lchild=p;elsefather-rchild=p：讓雙親的子女指針指向該結(jié)點if(i=s.1)p-lchild=nul1;/處理無左子s.1vl=+R;s.l=i+l:s.f=p;s.1r=2;enaueues):elseif(i=s.h)p-rchild=nul1;/處理無右子s.lv1二+R;s.h=iT;s.f=

23、p;s.1r=l;enaueue(Q,s):elsels.lvl=+R;s.h=i-l:s.f=p;s.lr=l;enaueue(0.s):,7幻子樹有關(guān)信息入從歹ils.lvl=+R;s1二i+1:s.f=p;s.lr=2;enqueue(Q,s);/右子樹有關(guān)信息入隊列/結(jié)束while(!empty(Q)return(p);算法結(jié)束森林算法40森林在先根次序遍歷時，首先遍歷第一棵子樹的根，接著繪第一棵子樹的結(jié)點：之后址第二棵樹，最后一棵樹。本題中Ei是Hi所抬結(jié)點的次數(shù)，次數(shù)就是結(jié)點的分支個數(shù)B,而分支數(shù)B與樹的結(jié)點數(shù)N的關(guān)系定二B+l(除根結(jié)點外，任何一個結(jié)點都有一個分支所指)。所以，從

24、Ei的第一個單元開始，將值累加.當累加到第i個單元，其值正好等于i-1時，就繪第一棵樹。接著，用相同方法，將其它樹分開，進行到第n個單元，將所有樹分開。voidForest(ElemTypeH,intE,int,n)/Hi是森林F在先根次序下結(jié)點的地址排列，Ei是Hi所指結(jié)點的次數(shù)，木算法計算森林F的樹形個數(shù)，并計算森林F的最后一個樹形的根結(jié)點地址inti=l,sum=0,j=0,m=0;/sumid一棵樹的分支數(shù)，j記樹的棵數(shù)，m記一棵樹的結(jié)點數(shù)inttree;/tree記毎棵樹先序遍歷最后一個結(jié)點在Hi中的地址while(iintroot)/木算法將雙親表示法的樹pt轉(zhuǎn)為孩子兄弟鏈表農(nóng)示的

25、樹，root是根結(jié)點在雙親表示法中的下標。CSTreechild,sibling;intfirstchild;CSTreecst=(CSTree)malloc(sizeof(CSNode);/申請結(jié)點空間cst-data=ptnodesrootdata;cst-firstchild=null;cst-nextsibling=null;/根結(jié)點firstchild二1:for(i=l；ifirstchild=child;firstchild=O:sibling=cst-firstchild;else/child不是root的第一個孩子，作兄弟處理sibling-nextsibling=child

26、;sibling=sibling-nextsibling;/if/endforreturncst;/結(jié)束PtreetoCstree二叉樹相似算法46兩棵空二叉樹或僅有根結(jié)點的二叉樹相似：對非空二叉樹，可判左右子樹是否相似，釆用遞歸算法。intSimilar(BiTreep,q)/判斷二叉樹p和q是否相似if(p=null&q=null)return(1)；elseif(!p&qp&!q)return(0);elsereturn(Similar(p-lchiId,q-lchild)&Similar(p-rchiId,q-rchild)/結(jié)束Similar統(tǒng)計結(jié)點數(shù)算法intBTLC(BiTree

27、T,int*c)/對二叉樹T的結(jié)點計數(shù)-遞歸if(T)*c+;BTLC(T-lchild,&c);/統(tǒng)計左子樹結(jié)點BTLC(rchild,&c);/統(tǒng)計右子樹結(jié)點/結(jié)束Count,調(diào)用時*c=0intCount(CSTreet)/統(tǒng)計以孩子兄弟鏈表表示的樹的葉子結(jié)點個數(shù)-遞歸if(t=null)return(0);else辻(t-firstlchild=null)/左子女為空，結(jié)點必為葉子retum(lCount(t-n亡xtsibling)：/(葉子)+兄弟子樹上的葉子結(jié)點elsereturn(CountdfirstchildHount(t-nextsibling);/子女子樹兄弟子樹/Co

28、untvoidCount(BiTreebt,int*n0,*n)/統(tǒng)計二叉樹bt上葉子結(jié)點數(shù)nO和非葉子結(jié)點數(shù)n-遞歸if(bt)if(bt-lchild=null&bt-rchild=nul1)*n0+；/葉壬結(jié)點else*n+;/非葉結(jié)點Count(bt-lchild.&n0,&n);Count(bt-rchild.&n0,&n);/結(jié)束CountintCount(BiTreebt)/非遞歸遍歷求二叉樹上的葉子結(jié)點個數(shù)/類似后序或中序思想tintnum=0;B訂wes;/s是找棧中元素定二叉樹結(jié)點指針，棧容雖足夠大whlie(bt!二null丨toD0)/樹不空或棧不空審hile(bt!二

29、null)push(stbt):bt=bt-lchild：/樹不空$仆左分支向下if(!StackEniD(s)/棧不空bt=null(J)bt=bt-lchild(2)bt=bt-rchildbt=DOD(s):i(bt-lchild=null&bt-rchild=nul1)num+：/吐壬結(jié)點，計數(shù)bt=bT-rchild：/出棧轉(zhuǎn)右子樹return(num):/結(jié)束Count后序線索二叉樹算法61在線索二叉樹上插入結(jié)點，破壞了與被插入結(jié)點的線索。因此，插入結(jié)點時，必須修復(fù)線索。在結(jié)點y的右側(cè)插入結(jié)點x,因為是后序線索樹，要區(qū)分結(jié)點y有無左子樹的情況。voidTreeinsert(B訂re

30、et,y,x)/在后序線索二叉樹t的結(jié)點y的右側(cè)，插入結(jié)點xif(y-ltag=0)/y有左子p二y-lchild;if(p-rtag=l)p-rchild=x;/x是y的左壬的后莊辰繼x-ltag=l;x-lchild=p;/x的左線盍足y的左子女else/v無冷子x-ltag=l;x-lchild=y-lchild;/y的左線索成為x的左線蜜if(y-lchild-rtag=l)/若y的后序前驅(qū)的右標記為1右線索后繼y-lchi1d-rchi1d=x;/則將y的后序述驅(qū)的后繼改為xx-rtag=l;x-rchild=y;5r-rtag=0;y-rchild=x;/x作y的右子樹結(jié)束Tree

31、insert中序線索二叉樹算法62在中序全線索化T樹的P結(jié)點上，插入以X為根的中序全線索化二叉樹，要對X有無左右子樹進行討論,并修改X左(右)子樹上最左結(jié)點和最右結(jié)點的線索。在中序線索樹上査找某結(jié)點P的前驅(qū)的規(guī)律定：若p-ltag=b則p-lchild就指向前驅(qū)，否則，其前驅(qū)是p的左子樹上按中序遍歷的最后一個結(jié)點：查找某結(jié)點P的后繼的規(guī)律是：若p-rtag=b則p-rchild就指向后繼.否則，其后繼是p的右子樹上按中序遍歷的第一個結(jié)點。intTreeThrlnsert(Bi.ThrTreeT,P,X)/在中序全線索二叉樹T的結(jié)點P,插入以X為根的中序全線索二叉樹，返回插入結(jié)果信息。if(P-

32、ltag=O&P-rtag=O)printf(“P結(jié)點有左右子樹，插入失敗n”):return(0);if(P-ltag=0)P有左子,將X林九P的右子if(X-ltag=l)X-lchild=P;若X無左子樹，X的在線蠱(前驅(qū))楚Pelse若X有左子樹尋找X的左子樹上最左(下)邊的結(jié)點q=X-lchild;q=q-lchild;q-lchild=P;if(X-rtag=l)/若X無右子樹，修改X的右紅盍X-rchild=P-rchild;/將P的右線索改為X的右線索else若X有右子樹找X右子樹最右面的結(jié)點q=X-rchild;while滬二0)q=q-rchild;q-rchild=P-r

33、chiId;P-rtag=O;P-rchild=X;/將X作為P的右子樹/結(jié)束將X插入為P的右子樹else/P-ltag=lP有右子,將X插入為P的心子if(X-ltag=l)/X無左子X-lchild=P-lchild;/將P的左線索改為X的左線鑾else/X有左子樹，找X左子樹上最左邊的結(jié)點q=X-lchild;二=0)q=q-lchild;q-lchild=P-lchild;if(X-rtag=l)X-rchild=P;/若X無右子樹，則X的右線索是Pelse/X有右子樹.査其右子樹中最右邊的結(jié)點,將該結(jié)點的后繼修改為Pq=X-rchild;vrhile滬二0)q=q-rchild;q-

34、rchild=P;P-ltag=0;/最后將P的左標記置0P-lchild=X;/P的左子鏈接到X/結(jié)束將X插入為P的左子/結(jié)束TreeThrfnsert72若使新插入的葉子結(jié)點S成T右子樹中序序列的第一個結(jié)點，則應(yīng)在T的右子樹中最左而的結(jié)點(設(shè)為p)處插入，使S成為結(jié)點P的左子女。則S的前驅(qū)是T,后繼是pvoidThrTreelnsert(BiThrTreeT,S)在中序線索二叉樹T的右子樹上插入結(jié)點S使S成為T右子樹中序遍歷第一個結(jié)點p=T-rchild;/用p去指向T的右子樹中最左面的結(jié)點vrhileg-RgKO)p=p-lchild;S-ltag=l;S-rtag=l;/S叢葉子,其左

35、右標記均為1S-lchild=T;S-rchild=p;/S的遡驅(qū)是根結(jié)點T,底繼是結(jié)點pp-lchild=S;p-ltag=O;/將p的左子女指向S,并修改左標志為0/結(jié)束ThrTreelnsert63在中序線索樹中，非遞歸査找數(shù)據(jù)域為A的結(jié)點(設(shè)該結(jié)點存在，其指針為P)并將數(shù)據(jù)域為x的Q結(jié)點插入到左子樹中。若F無左子女，則Q成為P的左子女，原P的左線索成為Q的左線索，Q的右線索為P：若F有左子樹，設(shè)P左子樹中最右結(jié)點的右線索是結(jié)點Q，結(jié)點Q的右線索是P。voidInThrlnsert(BiThrTreeT,Q;ElemTypeA)在中序線索二叉樹T中，査找其數(shù)拯域為A的結(jié)點，并在該結(jié)點的左

36、子樹上插入結(jié)點QBiThrTreeP=T;while(P)while(P-LT=O&PTdata!二A)P=P-LL;沿冷子樹向下if(Pd泣a=A)break:/找到數(shù)據(jù)域為A的結(jié)點，退出循環(huán)while(PJRT=l)bP-RL;/還沒找到數(shù)據(jù)域為A的結(jié)點沿右線索找后繼P=P-RL;/沿右子樹向下if(P-LT=l)/P沒有左子樹,Q結(jié)點插入作P的左子Q-LL=P-LL;Q-LT=1：/將P的左線索作為Q的左線索else/P右：冷樹,應(yīng)修改P的人辛樹品右結(jié)占的線盍Q-LL=P-LL;Q-LT=O;/Q成為P的左壬原P的左子成為Q的左子s=Q-LL;/s指向原P的左子女while(s-RT=O

37、)s=s-RL;/查找P的左子樹最右邊的結(jié)點s-RL=Q;原P左子樹上最右結(jié)點的右線索圧新插入結(jié)點QP-LT=O;P-LL=Q;/修改P的標記和指針0成為P的左子Q-RT=1;Q-RL=P;/Q中序后繼是P;/結(jié)束InThrlnsert64“雙鏈”就利用二叉樹結(jié)點的左右指針，重新定義左指針為指向前驅(qū)的指針，右指針是指向后繼的指針，鏈表在遍歷中建立,下面采用中序遍歷二叉樹。BiTreehead二null,pre;/個局變;就鏈表頭指針head,prevoidCreatLeafList(BiTreebt)/將BiTree樹中所有葉子結(jié)點鏈成帶頭結(jié)點的雙鏈表中序遞歸if(bt)若bt不空CmtLea

38、fList(bt-lchild);/中序遍歷左子樹if(bt-lchild=null&bt-rchild=null)/葉子結(jié)點if(head二二null)/第一個葉子結(jié)點head二(BiTree)malloc(sizeof(BiNode):/生成頭結(jié)點head-lchild=null;head-rchild=bt;/頭結(jié)點的圧鏈為牢右鏈指向第一個葉子結(jié)點bt-lchild=head;pre=bt;/第一個葉子結(jié)點左鏈指向頭結(jié)點，pre指向當前葉子結(jié)點else/已不叢第一個葉壬結(jié)點pre-rchild=bt;bt-lchild=pre;pre=bt;/當前葉子結(jié)點鏈入雙鏈表CreatLeafLi

39、st(bt-rchild);/中序遍歷右子樹Dre-Xrchild二null:/最后一個葉子結(jié)點的右鏈宙牢(鏈表結(jié)束標記)/if(bt)/結(jié)束CreatLeafList;65求中序全線索樹任意結(jié)點p的前序后繼，其規(guī)則如下：若p有左子女，則左子女就是其前序后繼：若p無左子女而有右子女.則P的右子女就是P的前序后繼；若P無左右子女，這時沿P的右線索往上，直到P的右標志為0(非線索)，這時若p的右子女為空，則表示這是中序遍歷最后一個結(jié)點，故指定結(jié)點無前序后繼，否則，空結(jié)點就是指定結(jié)點的前序后繼。程序段如下：if(p-ltag0&D-lchild!二null)return(p-lchild);/p的左

40、子女是p的前序后繼elseif(p-rtag=0&D-rchild!二null)return(p-rchiId);/p右子女是其前序后繼else/p無左右子女，應(yīng)沿右線索向上(找其前序后繼),直到某結(jié)點右標記為0while(p-rtag=l)p=p-rchild;if(p-rchild)return(p-rchiId);elsereturn(null);/指定結(jié)點的前序后繼算法討論請注總題目“中序序列第一結(jié)點的左標志和最后結(jié)點的右標志皆為0(非線索)，對應(yīng)指針皆為空”的說明。若無這一說明.只要結(jié)點的左標記為0.苴左子女就是苴前序厲繼。最后，當p無子女，沿右線索向上找其前序后繼時，若最后結(jié)點的右

41、標志為0,但對應(yīng)指針為空，p也無前序后繼。66不借助輔助堆棧實現(xiàn)蟲生遍歷，必須解決如何查找厲繼的間題。使用線索樹就行。為此，將結(jié)點結(jié)構(gòu)修改為(ltag,lchild,data,rchild,rtag)。設(shè)二叉樹己中序線索化。下面首先編寫一查中序后繼的函數(shù)，接著是中用遍歷的非遞歸算法。BiTreeAfter(BiThrTreet)査中序線索二叉樹上結(jié)點t的后繼if(t-rtag=l)return(t-rchild);p=t-rchild;while(p-ltag=0)p=p-lchild;/d右子樹中最左卞的結(jié)點是d的中序后繼return(p);/ifvoidInOrder(BiThrTreeb

42、t)/非遞歸中序遍歷帶頭結(jié)點的中序線索二叉樹btp=bt-lchild;/p指向原二叉樹的根結(jié)點if(p!=bt)二叉樹非空while(p-ltag=0)p=p-lchild;/找中序遍歷的第一個結(jié)點while/沒回到頭結(jié)點，就一直找后繼并遍歷visit(*p);p=After(p);/if結(jié)束算法InOrder67在中序穿線樹中找結(jié)點的雙親，最簡單悄況是順線索就可找到。例如，結(jié)點的左子女的右線索和右子女的左線索都指向雙親,但對于有左右子女的結(jié)點來說，則要利用中序穿線樹中線索“向上”指向祖先的特點：若結(jié)點p是結(jié)點q右子樹中中序遍歷最左下的結(jié)點，P的左線索指向3若結(jié)點P是結(jié)點q左子樹上中序遍歷最

43、右下的結(jié)點，P的右線索指向是q反過來.通過祖先找子女就容易了。另外，若結(jié)點的后紳肚中存穿線樹的頭結(jié)占，則應(yīng)特殊老慮avoidFFA(B訂hrTreet,p,q)/在中序穿線樹t上，求結(jié)點p的雙親結(jié)點qq=P；/暫存while(q-RTAG=O)q=q-RLINK;/找d的中序最右下的結(jié)點q=q-RLINK;/順右線索找到q的后繼(p的竝結(jié)點)if(a二二I)q=t-LLINK;/若厲繼肚頭結(jié)點,則轉(zhuǎn)到根結(jié)點if(E)printf(捏結(jié)蟲無雙親n”)：return;if(a-ALLIXRKD)return(q)；elseq=q-LLINK;/準備到心子樹中找d砰hile(a-RLIXK!二d)a

44、二a-RLIXK：return(q):/找最右結(jié)點的過程中回找到D/結(jié)束FFA算法討論也可以先求結(jié)點P最左下結(jié)點的前驅(qū)線索，請讀者H己寫岀算法。B:iThrTreeInOrder(BiThrTreeT,ElemTypex)先在帶頭結(jié)點的中序線索二叉樹T中查找給定值為x的結(jié)點，假定值為x的結(jié)點存在p=T-lchild;/設(shè)p指向二叉樹的根結(jié)點while(p!=T)while(pltag=0&p-data!=x)p=p-lc;if(p-data=x)return(p);while(p-rtag=1&p-rc!=T)p=p-rc;if(p-data=x)return(p);p=p-rc;結(jié)束InOr

45、derBiThrTreeAfterXNode(B訂hrTreeT)/在中序線索二叉樹T中，求給定值為x的結(jié)點的后繼結(jié)點BiThrTreeD=InOrde(T.x);/首先在T樹上査找給定值為x的結(jié)點山p指向if(p-rtag=l)return(p-rc);/若p的右標志為1.則p的rc指針指向其后繼elseq=p-rc;while(q-ltag=O)q=q-lc;return(q);結(jié)點p的右子樹中最左而的結(jié)點是結(jié)點p的中序后繼/結(jié)束AfterXnode6&帶頭結(jié)點的中序線索樹，苴頭結(jié)點的lchiId梧向二叉樹的根結(jié)點,頭結(jié)占的rchild域指向中序遍歷的最后一個結(jié)點。而二叉樹按中用遍歷的第一

46、個結(jié)點的lchild和最后一個結(jié)點的rchild指向頭結(jié)點。故從頭結(jié)點找到根結(jié)點后，順“后繼”訪問二叉樹。voidPreorderlnThreat(BiTrhTreetbt)前序遍歷-中序全線索二叉樹tbt,tbt足頭結(jié)點指針bt=tbt-lchild;while(bt)while二二0)printf(bt-data);bt=btlchiId:/沿心分核向卜=printf(bt-data);遍歷其左標志為1的結(jié)點，準備右轉(zhuǎn)while(bi-Ariagnl&bt-rchilC!二tbt)bt=bt-rchiId;/id右鏈向I:if(bt-rchild!二tbt)bt=bt-rchild;/沿右

47、分枝向卞/結(jié)束PreorderlnThreat時間復(fù)雜度0(n)。后序遍歷是“左-右-根J因此，若結(jié)點有右子女，則右子女是其后序前驅(qū)，否則，左子女(或左線索)指向其后序前驅(qū)。BiThrTreePostSucc(BiThrTreeT,p)/在后序線索二叉樹T中，查找指定結(jié)點p的直接前驅(qū)qif(p-Rtag=0)q=p-Rchild;/若d有右子女,則右子女為其前驅(qū)elseq=p-Lchild;若d無右子女,左子女或左線索就泉p的后序前驅(qū)return(q);/結(jié)束PostSucc在后序序列中，若結(jié)點p有右子女，則右子女是其前驅(qū)，若無右子女而有左子女.則左子女是其前驅(qū)。若結(jié)點p左右子女均無，設(shè)其中序左線索指向某祖先結(jié)點f(p是f右子樹中按中序遍歷的第一個結(jié)點).若f有左子女，則其左子女是結(jié)點p在后序下的前驅(qū)；若f無左子女，則順其前驅(qū)找雙親的雙親.一直繼續(xù)到雙親有左子女(這時左子女是p的前驅(qū))。還有一種情況，若p是中