中序線索化二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)

1、中序線索化二叉樹(shù)數(shù)據(jù)結(jié)構(gòu).當(dāng)用二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，因?yàn)槊總€(gè)結(jié)點(diǎn)中只有指向其左、右孩子結(jié)點(diǎn)的指 針，所以從任一結(jié)點(diǎn)出發(fā)只能直接找到該結(jié)點(diǎn)的左、右孩子。在一般情況下靠它無(wú)法直接找 到該結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)。如果在每個(gè)結(jié)點(diǎn)中增加指向其前驅(qū)和后繼結(jié) 點(diǎn)的指針，將降低存儲(chǔ)空間的效率。與此同時(shí)，我們可以證明：在n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針。因?yàn)楹琻個(gè)結(jié)點(diǎn)的 二叉鏈表中含有2n個(gè)指針，除了根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都有一個(gè)從父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針， 因此一共使用了 n-1個(gè)指針，所以在n個(gè)結(jié)點(diǎn)的二叉鏈表中含有2n-(n-l)=n+1個(gè)空指針。因此，可以利用這些空指針，存放指向結(jié)點(diǎn)

2、在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針。這 種附加的指針?lè)Q為線索，加上了線索的二叉鏈表稱(chēng)為線索鏈表，相應(yīng)的二叉樹(shù)稱(chēng)為線索二叉 樹(shù)。為了區(qū)分一個(gè)結(jié)點(diǎn)的指針是指向其孩子的指針，還是指向其前驅(qū)或后繼結(jié)點(diǎn)的線索，可 在每個(gè)結(jié)點(diǎn)中增加兩個(gè)線索標(biāo)志。這樣，線索二叉樹(shù)結(jié)點(diǎn)類(lèi)型定義為：LchildLtagDataRtagRchild其中：Ltag=0時(shí)，表示Lchild指向該結(jié)點(diǎn)的左孩子；Ltag=1時(shí)，表示Lchild指向該結(jié)點(diǎn)的線性前驅(qū)結(jié)點(diǎn);Rtag=0時(shí)，表示Rchild指向該結(jié)點(diǎn)的右孩子；Rtag=1時(shí)，表示Rchild指向該結(jié)點(diǎn)的線性后繼結(jié)點(diǎn);以二叉鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)所構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)

3、構(gòu)，叫做線索二叉鏈表；指 向結(jié)點(diǎn)的線性前驅(qū)或者線性后繼結(jié)點(diǎn)的指針叫做線索；加上線索的二叉樹(shù)稱(chēng)為線索二叉樹(shù) 對(duì)二叉樹(shù)以某種次序遍歷將其變?yōu)榫€索二叉樹(shù)的過(guò)程叫做線索化。中序線索化是指用二叉鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)建立二叉樹(shù)的二叉鏈表，然后按照中序遍歷的方法 訪問(wèn)結(jié)點(diǎn)時(shí)建立線索。例如有如上圖所示二叉樹(shù)，則中序遍歷的順序是：0 / J * I + H A G【參考程序】#include #include typedef enumLink,Thread PointerTag; /*指針標(biāo)志*/typedef char DataType;typedef struct BiThreTree /*定義結(jié)點(diǎn)元素*/Po

4、interTag LTag,RTag;DataType data;struct BiThreTree *lchild,*rchild;BiThreTree;BiThreTree *pre;/*全局變量，用于二叉樹(shù)的線索化*/BiThreTree *CreateTree()/*按前序輸入建立二叉樹(shù)*/BiThreTree *T;DataType ch;scanf(%c,&ch);if(ch=#)T=NULL;elseT=(BiThreTree *)malloc(sizeof(BiThreTree);T-data=ch;T-LTag二Link；/*初始化時(shí)指針標(biāo)志均為L(zhǎng)ink*/T-RTag=Li

5、nk;T-lchild=CreateTree()；T-rchild=CreateTree()；return T；void InThread(BiThreTree *T)BiThreTree *p；p=T；if(p)InThread(p-lchild)；if(!p-lchild) p-LTag=Thread；p-lchild=pre;if(!pre-rchild) pre-RTag=Thread;pre-rchild=p;pre=p;InThread(p-rchild);BiThreTree *InOrderThrTree(BiThreTree *T) /*中序線索化二叉樹(shù)*/ BiThreTr

6、ee *Thre；/*Thre 為頭結(jié)點(diǎn)的指針*/Thre=(BiThreTree *)malloc(sizeof(BiThreTree);Thre-lchild=T；Thre-rchild=Thre；pre=Thre；InThread(T)；pre-RTag=Thread；pre-rchild=Thre；Thre-rchild=pre；return Thre；void InThrTravel(BiThreTree *Thre) /*中序遍歷二叉樹(shù)*/BiThreTree *p;p=Thre-lchild;while(p!=Thre) /*指針回指向頭結(jié)點(diǎn)時(shí)結(jié)束*/ while(p-LTag=

7、Link)p=p-lchild;printf(%4c,p-data); while(p-RTag=Thread&p-rchild!=Thre)p=p-rchild;printf(%4c,p-data);p=p-rchild;void main()BiThreTree *T,*Thre;printf(“PreOrder Create Binary Tree:n”);T=CreateTree();Thre=InOrderThrTree(T);printf(“InOrder Traverse Binary Tree:n”);InThrTravel(Thre);system(pause);【調(diào)試舉例】

8、建立二叉樹(shù)時(shí)，按先序遍歷方式輸入：“ABD#EH#I#CF#G#”，其中“#”表示空指 針。建立的二叉樹(shù)為：ABCD E F GH I程序輸出為中序遍歷線索化二叉樹(shù)的結(jié)果：DBHEIAFCG已知A、B和C為三個(gè)遞增有序的線性表，現(xiàn)要求對(duì)A表作如下操作：刪除那些既在B表中 出現(xiàn)又在C表中出現(xiàn)的元素。【實(shí)驗(yàn)步驟】試對(duì)順序表編寫(xiě)實(shí)現(xiàn)上述操作的算法并上機(jī)編寫(xiě)代碼，要求算法盡可能高效。在實(shí)驗(yàn)報(bào)告 中分析你的算法的時(shí)間復(fù)雜度。A表中要?jiǎng)h除的元素實(shí)際上就是在三個(gè)表中都存在的元素。注意這三個(gè)線性表都是遞增有 序的線性表！可以利用這一性質(zhì)減少對(duì)線性表“掃描”的趟數(shù)。3改用單鏈表作為存儲(chǔ)結(jié)構(gòu)編寫(xiě)算法，請(qǐng)釋放A表中

9、無(wú)用的結(jié)點(diǎn)空間，并上機(jī)編程實(shí)現(xiàn)?！舅惴ㄋ枷搿肯葟腂和C中找出共有元素same，再?gòu)腁中從當(dāng)前位置開(kāi)始，凡小于same的元素均保留, 等于same的就跳過(guò)，大于same時(shí)就再找下一個(gè)same。【順序存儲(chǔ)結(jié)構(gòu)算法描述】void SqList_Delete(SqList&A, SqList B, SqList C)i=O；j=O；m=O；/*i指示A中元素原來(lái)的位置，m為移動(dòng)后的位置*/while(iA.leng th&jB.leng th&kC.leng th)if(B.elemjC.elemk) j+；else if(B.elemjC.elemk)k+；elsesame= B.elemj；/*找

10、到了相 同元素 same*/while(B.elemj=same)j+；while(C.elemk)=same)k+；/*j,k 后移到新的元素*/while(iA.length&A.elemisame)A.elemm+=A.elemi+；/ *需要保留的元素移動(dòng)到新位置*/while( iA.length&A.elemi=same)i+；/*else*/*while*/while(iA.length)A.elemm+=A.elemi+；/*A 的剩余元素重新存儲(chǔ)*/A.length=m;/*SqList_Delete*/【順序存儲(chǔ)結(jié)構(gòu)參考程序】#includemain()#defineN3/

11、*宏定義,代表數(shù)組維數(shù)*/#defineM4#defineT5int i,j,k,r,m,same；/*定義變量分別指向數(shù)組a,b,c*/int aN,bM,cT;printf(“please input numbers:n”)；for (i=0；iN；i+) scanf(%d,&ai)；for (j=0；jM；j+) scanf(%d,&bj)；for (k=0；kT；k+)scanf(%d,&ck)；i=O；j=O；m=O；k=O；/*分別賦值為0,即指向數(shù)組的第一元素*/while(iN&jM&kT)if(bjck) k+；elsesame=bj； while(bj=same)j+;wh

12、ile(ck=same)k+;while(iN&aisame)am+=ai+;while(iN&ai=same) i+;while(iN)am+=ai+;printf(a%d二,m)；/*輸出刪除元素后的數(shù)組a/*for (r=0;rm-1;r+)printf(%d,ar);printf(%d,am-1)；printf(n)；return；【程序調(diào)試】程序運(yùn)行是屏幕顯示：please input numbers:此時(shí)輸入三組測(cè)試數(shù)據(jù),數(shù)據(jù)間用空格隔開(kāi):2 3 4回車(chē)3 4 5 6回車(chē)4 5 6 7 8回車(chē)程序輸出結(jié)果：a3 = 2,3,即刪除了數(shù)組a中即在b和c中都出現(xiàn)的元素。單鏈表存儲(chǔ)結(jié)構(gòu)參

13、考程序】# include # include Typedef struct LNodeint data;struct LNode *next;Lnode,*LinkLis t；/*定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)*/void main ( )/*功能：建立單鏈表A,B,C，并且刪除A中均在B和C中出現(xiàn)的數(shù)據(jù)。*/Crea te Lis t (LinkLis t head)；/*函 數(shù)聲明*/ListDelete (LinkList La, LinkList Lb ,LinkList Lc)；Print (LinkList head)；LinkList headA,headB,headC；headA=NUL

14、L；headB=NULL；headC=NULL；headA=Crea teLis t( headA)；/*建立鏈表*/headB=CreateList(headB)；headC=CreateList(headC)；prin t(headA)；/*輸出顯示鏈表數(shù)據(jù)*/print(headB)；print(headC)；headA二ListDelete(headA,headB,headC)；/*刪除 A 中滿(mǎn)足條件的節(jié)點(diǎn)*/Print (headA);LinkList createList(LinkList head)/*功能：建立有頭節(jié)點(diǎn)head的數(shù)據(jù)單鏈表*/LinkList p,q;p=q=

15、(LinkList)malloc(sizeof(Lnode);printf(ninput data:n);scanf(%d,&p-data);p-next=NULL;while(p-dataO)/*建立鏈表的輸入數(shù)據(jù)必須大于0，數(shù)據(jù)輸入時(shí)以輸入任何負(fù)數(shù)作 為結(jié)束*/if(head=NULL) head=p;elseq-next=p;q=p;p=(LinkList)malloc(sizeof(Lnode);printf(ninput data:n);scanf(%d,&p-data);return head;LinkList ListDelete(LinkList La,LinkList Lb,

16、LinkList Lc)/*功能：刪除A中的有關(guān)節(jié)點(diǎn)*/LinkList pa,pb,pc,qa;pa=La;qa=La;pb=Lb;pc=Lc;while(pb&pc)if(pb-datadata)pb=pb-next;else if(pb-datapc-data)pc=pc-next;else/*首先找到B和C中都存在的數(shù)據(jù)，并且定位*/f (pa-datapb-data)/*在A中找到B和C中都存在的數(shù)據(jù)*/ qa=pa;else if(pada ta=pbda ta)/*刪 除節(jié)點(diǎn)*/ qa-next=pa-next; f ree(pa);pa=qa-next;else pb=pb-n

17、ext;/*else*/*while*/return La;void print(LinkList head)/*輸出鏈表數(shù)據(jù)*/LinkList r;r=head;printf(noutput data:n);while(r!=NULL)printf(%d ,r-data);return;【實(shí)驗(yàn)分析】因?yàn)閱捂湵鞟, B, C中的元素都是遞增有序的，所以先通過(guò)遍歷B和C找到它們共同 的元素，然后再查找該元素是否也存在于A中，存在則刪除；否則再查找B和C中的下一個(gè) 相同元素。無(wú)論是順序存儲(chǔ)結(jié)構(gòu)還是單鏈表存儲(chǔ)結(jié)構(gòu)，都采用一次遍歷的方式來(lái)找到即在B和C中 都出現(xiàn)的元素，故時(shí)間復(fù)雜度為 O(n)。作業(yè)

18、參考答案2007.9.271試寫(xiě)出一個(gè)計(jì)算鏈表中數(shù)據(jù)元素結(jié)點(diǎn)個(gè)數(shù)的算法，其中指針P指向該鏈表的第一個(gè)結(jié)點(diǎn)?！緟⒖妓惴ā縤nt ListLength_L(LinkList &L)p=L-next;i=0;while(p)p=p-next;i+;return i;2試設(shè)計(jì)實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)的算法。【參考算法】status ListDelete_L(LinkList &L)p=L-next;while(p)r=p;while(q)if(q-data=p-data)r-next=q-next;free(q);q=r-next;else r=q;q=q-next;p=p-next;3有一

19、個(gè)線性表(al a2 -an),它存儲(chǔ)在有附加表頭結(jié)點(diǎn)的單鏈表中，寫(xiě)一個(gè)算法求出該 線性表中值為x的元素的序號(hào)，若x不存在，則輸出序號(hào)0.【參考算法】int Locate_L(LinkList L,int x)k=1;for (p=L-next;p&p-data!=x;p=p-next)k+;if(knext;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next;q-next=p;s-next=q;L-next=s;5.在一個(gè)非遞減有序線性表中，插入一個(gè)值為x的元素，使插入后的線性表仍為非遞減有序 的，分別用向

20、量和單鏈表編寫(xiě)算法。【參考算法】向量算法：status Insert_SqList(SqList &va,int x)if(va.length+1va.listsize) return error;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;retrun ok;單鏈表算法：status Insert_LinkList(LinkList &L)while(p &p-datanext;q=(LinkList)malloc(sizeof(LNode);q-data=x;q-next=p;r-next=q;rerurn ok;6將兩個(gè)遞增有序的線性表歸并成一個(gè)非遞增有序表?！緟⒖妓惴ā縱oid MergeList_L(LinkList &La,LinkList &Lb,LinkList