樹上海金融學(xué)院信息管理系樹上海金融學(xué)院信息管理系1第五章樹5.1樹的基本概念一、樹的定義：樹是由一個(gè)結(jié)點(diǎn)或多個(gè)結(jié)點(diǎn)組成的有限集T，它滿足下面兩個(gè)條件：（１）有一個(gè)特定的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)；（２）其余的結(jié)點(diǎn)分成m（m≥0）個(gè)互不相交的有限集T0,T1,T2,…,Tm-1。其中每個(gè)集合又都是一棵樹。稱T0,T1,T2,…,Tm-1為根結(jié)點(diǎn)的子樹。第五章樹5.1樹的基本概念25.1樹的基本概念k1k0k2k3k4k5k6k7k8k9k105.1樹的基本概念k1k0k2k3k4k5k6k7k8k935.1樹的基本概念二、基本概念o一棵樹至少有一個(gè)結(jié)點(diǎn)。o葉子結(jié)點(diǎn)沒有子樹；非葉子結(jié)點(diǎn)至少有一棵子樹。o結(jié)點(diǎn)的子樹的個(gè)數(shù)為該結(jié)點(diǎn)的次數(shù)。顯然，葉子結(jié)點(diǎn)的次數(shù)為０。o樹中的各結(jié)點(diǎn)次數(shù)的最大值，為該樹的次數(shù)。上一頁的樹為３次樹。o樹T是一棵m次樹，若它的非葉子結(jié)點(diǎn)的次數(shù)均為m，則稱T為一棵m次完全樹。5.1樹的基本概念二、基本概念45.1樹的基本概念o若結(jié)點(diǎn)ki和kj被一條線段所連接，ki在上端，kj在下端，則ki是kj的父結(jié)點(diǎn)，kj為ki的子結(jié)點(diǎn)。o同為某結(jié)點(diǎn)的子結(jié)點(diǎn)，則稱為兄弟結(jié)點(diǎn)。o根結(jié)點(diǎn)所在的層次為０；其他結(jié)點(diǎn)所在層次等于它的父結(jié)點(diǎn)所在層次加１。o樹中結(jié)點(diǎn)的最大層次，稱為該樹的深度，或高度。5.1樹的基本概念o若結(jié)點(diǎn)ki和kj被一條線段所連接，k55.1樹的基本概念o若結(jié)點(diǎn)ki能自上而下地通過樹中結(jié)點(diǎn)到達(dá)結(jié)點(diǎn)kj，則稱ki到kj存在一條路徑。路徑可用結(jié)點(diǎn)序列來表示。注意：位于不同子樹中的兩個(gè)結(jié)點(diǎn)之間不存在路徑。o路徑長度等于這條路徑上的結(jié)點(diǎn)個(gè)數(shù)減１。o從根結(jié)點(diǎn)到樹中的其余結(jié)點(diǎn)的路徑稱為樹枝。其路徑長度稱為樹枝長度。5.1樹的基本概念o若結(jié)點(diǎn)ki能自上而下地通過樹中結(jié)點(diǎn)到65.1樹的基本概念o在路徑（k0,k1,k2,…,kn-1,kn）中，k0,k1,k2,…,kn-1為kn的祖先，k1,k2,…,kn-1,kn為k0的后代。o若在給定的m次樹中，每個(gè)結(jié)點(diǎn)的每棵子樹規(guī)定了序號（一般從左到右），次序不能交換，則該樹為有序樹。否則，稱為無序樹。5.1樹的基本概念o在路徑（k0,k1,k2,…,75.1樹的基本概念三、樹結(jié)構(gòu)的應(yīng)用１．表示層次關(guān)系：家庭結(jié)構(gòu)２．有序樹表示某種順序關(guān)系（１）句子結(jié)構(gòu)（２）算術(shù)表達(dá)式p.1045.1樹的基本概念三、樹結(jié)構(gòu)的應(yīng)用85.2樹的存儲結(jié)構(gòu)樹是不同于線性表的非線性結(jié)構(gòu)，不能用一維數(shù)組或線性鏈表來存儲樹。樹的結(jié)點(diǎn)的一般形式：data:存儲結(jié)點(diǎn)值，可有多個(gè)分量（包括鍵）。pointers:指針，可有多個(gè)分量，表現(xiàn)結(jié)點(diǎn)之間的非線性關(guān)系。datapointers5.2樹的存儲結(jié)構(gòu)樹是不同于線性表的非線性結(jié)構(gòu)，不能用95.2樹的存儲結(jié)構(gòu)１.樹的標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)若樹是m次樹，則結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為：pointers有m個(gè)字段，依次存放子結(jié)點(diǎn)的地址。若某個(gè)序號的子結(jié)點(diǎn)不存在，則置空。datachild0,child1,child2,…,childm-2,childm-1pointers5.2樹的存儲結(jié)構(gòu)１.樹的標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)datachi10１.樹的標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)標(biāo)準(zhǔn)形式若為３次樹，則結(jié)點(diǎn)的類型描述為：structnode{intdata;structnode*child[3];};typedefstructnodeNODE;NODE*root1;１.樹的標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)標(biāo)準(zhǔn)形式115.2樹的存儲結(jié)構(gòu)2.樹的逆形式存儲結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為：parent是一個(gè)指針，指向父結(jié)點(diǎn)。只有根結(jié)點(diǎn)沒有父結(jié)點(diǎn)，根結(jié)點(diǎn)的parent字段置空。dataparent5.2樹的存儲結(jié)構(gòu)2.樹的逆形式存儲結(jié)構(gòu)datapa122.樹的逆形式存儲結(jié)構(gòu)逆形式結(jié)點(diǎn)的類型描述為：structr_node{intdata;structr_node*parent;};typedefstructr-nodeR_NODE;R_NODE*root2;2.樹的逆形式存儲結(jié)構(gòu)逆形式結(jié)點(diǎn)的類型描述為：135.2樹的存儲結(jié)構(gòu)3.樹的擴(kuò)充標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)若樹為m次樹，則結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為：其中：指針parent指向父結(jié)點(diǎn)；指針childi（０≤i≤m-1）依次指向子結(jié)點(diǎn)。dataparentchild0,child1,child2,…,childm-2,childm-15.2樹的存儲結(jié)構(gòu)3.樹的擴(kuò)充標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)datap143.樹的擴(kuò)充標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)若樹為３次樹，則結(jié)點(diǎn)的類型描述為：structe_node{intdata;structe_node*child[3];structe_node*parent;};typedefstructe_nodeE_NODE;E_NODE*root3;3.樹的擴(kuò)充標(biāo)準(zhǔn)形式存儲結(jié)構(gòu)若樹為３次樹，則結(jié)點(diǎn)的類型155.2樹的存儲結(jié)構(gòu)樹的圖示：pp.106-107標(biāo)準(zhǔn)形式逆形式擴(kuò)充標(biāo)準(zhǔn)形式5.2樹的存儲結(jié)構(gòu)樹的圖示：165.4樹的遍歷樹的遍歷：按某種指定的次序獲得一棵樹中的所有的結(jié)點(diǎn)。樹的遍歷是對于樹結(jié)構(gòu)進(jìn)行的最基本和最重要的一種操作。5.4樹的遍歷樹的遍歷：按某種指定的次序獲得一棵樹中的175.4樹的遍歷遍歷方法：（１）前序遍歷（２）后序遍歷（３）層次遍歷（４）遍歷葉子結(jié)點(diǎn)（５）對于二叉樹，中序遍歷（以后講）5.4樹的遍歷遍歷方法：18（1）前序遍歷首先訪問根結(jié)點(diǎn)，然后按前序遍歷根結(jié)點(diǎn)的各棵子樹。對于下面的樹，前序遍歷的結(jié)點(diǎn)序列為ABCDEFGHJKL.ABHDCLKJGEF（1）前序遍歷首先訪問根結(jié)點(diǎn)，然后按前序遍歷根結(jié)點(diǎn)的各棵19（2）后序遍歷首先按后序遍歷根結(jié)點(diǎn)的各棵子樹，然后訪問根結(jié)點(diǎn)。對于下面的樹，后序遍歷的結(jié)點(diǎn)序列為CFEGDHBKLJA.ABHDCLKJGEF（2）后序遍歷首先按后序遍歷根結(jié)點(diǎn)的各棵子樹，然后訪問根20（3）層次遍歷首先訪問第０層的根結(jié)點(diǎn)，然后訪問第１層的結(jié)點(diǎn)，再逐一訪問以下各層。對于下面的樹，層次遍歷的結(jié)點(diǎn)序列為ABJCDHKLEGF.ABHDCLKJGEF（3）層次遍歷首先訪問第０層的根結(jié)點(diǎn)，然后訪問第１層的結(jié)21（4）樹中葉子結(jié)點(diǎn)遍歷如果只有一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)就是葉子結(jié)點(diǎn)；否則就是根結(jié)點(diǎn)的各棵子樹的葉子結(jié)點(diǎn)。對于下面的樹，葉子結(jié)點(diǎn)的結(jié)點(diǎn)序列為CFGHKL.ABHDCLKJGEF（4）樹中葉子結(jié)點(diǎn)遍歷如果只有一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)就是葉子225.4樹的遍歷設(shè)m次樹的標(biāo)準(zhǔn)存儲形式的結(jié)點(diǎn)類型為：#defineMAXM10structnode{intdata;structnode*child[MAXM];};typedefstructnodeNODE;NODE*t;intm;//樹的次數(shù)5.4樹的遍歷設(shè)m次樹的標(biāo)準(zhǔn)存儲形式的結(jié)點(diǎn)類型為：235.4樹的遍歷

兩個(gè)前序遍歷的算法：p.115r_preorder(t,m)用遞歸調(diào)用來實(shí)現(xiàn)對m次樹t的前序遍歷。pp.115-116s_preorder(t,m)用棧來幫助實(shí)現(xiàn)對m次樹t的前序遍歷，順序存儲的棧用來保存尚未完成遍歷的子樹的根結(jié)點(diǎn)的地址。5.4樹的遍歷兩個(gè)前序遍歷的算法：24Voids_preorder(t,m)NODE*t;Intm;{NODE*s[100]Inttop,I;if(t==Null)return;//空樹,返回.s[0]=t;//根進(jìn)棧top=1;//棧頂指針=1while(top>0){t=s[--top];//取棧頂(某根)printf(“%c”,t->data);for(I=m-1;I>=0;I--)//該根結(jié)點(diǎn)所有子樹由后向前進(jìn)棧if(t->chlid[I]!=NULL)s[top++]=t->chlid[I];}}Voids_preorder(t,m)255.4樹的遍歷按層次遍歷的算法：p.116levorder(t,m)用隊(duì)列來幫助實(shí)現(xiàn)對m次樹t的層次遍歷，算法中使用一個(gè)順序存儲的隊(duì)列存放還沒有處理的子樹的根結(jié)點(diǎn)的地址（指針）。這里，隊(duì)首指針head指向隊(duì)首結(jié)點(diǎn)，隊(duì)尾指針tail指向隊(duì)尾結(jié)點(diǎn)的后面一個(gè)位置。5.4樹的遍歷按層次遍歷的算法：265.5樹的線性表示前面介紹的樹結(jié)構(gòu)，都是用指針來體現(xiàn)結(jié)點(diǎn)之間所存在的關(guān)系。但是，建立樹的結(jié)構(gòu)，需要按一定順序逐一將結(jié)點(diǎn)輸入計(jì)算機(jī)。這時(shí)的結(jié)點(diǎn)排列是線性的。于是，我們需要考慮怎樣用線性的方法來表示一棵樹。具體方法有：（１）層號表示（２）括號表示5.5樹的線性表示前面介紹的樹結(jié)構(gòu)，都是用指針來體現(xiàn)結(jié)27１.樹的層號表示定義結(jié)點(diǎn)層號：如果k是樹中的一個(gè)結(jié)點(diǎn)，那么結(jié)點(diǎn)k的層號lev(k)為整數(shù)，且滿足：（1）如果k’是k的子結(jié)點(diǎn)，那么lev(k’)>lev(k);（2）如果k’和k’’同是結(jié)點(diǎn)k的子結(jié)點(diǎn)，那么lev(k’)=lev(k’’)。p.117中間的樹以及其層號表示。注意：結(jié)點(diǎn)層號和結(jié)點(diǎn)所在的層次是不同的。１.樹的層號表示定義結(jié)點(diǎn)層號：28１.樹的層號表示樹的層號表示：（1）用一個(gè)二元組來表示結(jié)點(diǎn)，前一個(gè)元為層號，后一個(gè)元為結(jié)點(diǎn)鍵值。（2）所有結(jié)點(diǎn)的二元組按前序排列存放在一個(gè)二元組的數(shù)組中。１.樹的層號表示樹的層號表示：29１.樹的層號表示二元組數(shù)組的數(shù)據(jù)結(jié)構(gòu)描述：#defineMAXN100typedefstructdnode{intlev;intdata;}DNODE;DNODEa[MAXN];//存放層號表示的樹intn;//樹的結(jié)點(diǎn)個(gè)數(shù)１.樹的層號表示二元組數(shù)組的數(shù)據(jù)結(jié)構(gòu)描述：30１.樹的層號表示舉例：pp.117-118上的程序的功能是實(shí)現(xiàn)由樹的層號表示建立一棵按擴(kuò)充標(biāo)準(zhǔn)形式存儲的m次樹。對于某個(gè)結(jié)點(diǎn)來說，前面層號小的最近的結(jié)點(diǎn)是它的父結(jié)點(diǎn)；后面緊靠它、層號大的結(jié)點(diǎn)為它的子結(jié)點(diǎn)，再后面層號與子結(jié)點(diǎn)相同的結(jié)點(diǎn)為子結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，直到出現(xiàn)層號小于或者等于它的結(jié)點(diǎn)。１.樹的層號表示舉例：31*lev_tree(a,m,n){if(n<1)return;root=(NODE*)malloc();root->lev=a[0].lev;root->data=a[0].data;處理根結(jié)點(diǎn)For(I=0;I<m;I++)root->child[I]=NULL;Root->parent=NULL;P=root;For(I=1;I<n;I++){q=(NODE*)malloc();q->lev=a[I].lev;q->data[I]=a[I].data;//創(chuàng)建新結(jié)點(diǎn)for(j=0;j<m;j++)q->child[j]=NULL;//當(dāng)前結(jié)點(diǎn)兒子,清空;while(q->lev<=p->lev)p=p->parent;//找到P層號比Q的層號小,即找到Q的父親q->parent=p;//認(rèn)父親;j=-1;while(p->chlid[++j]!=NULL;//找沒有認(rèn)領(lǐng)過兒子的域;p->chlid[j]=q;//認(rèn)領(lǐng)兒子;p=q;//p指向新結(jié)點(diǎn),重復(fù)下一步;}return(root);}

(0,a),(1,b),(2,d),(2,e),(3,h),(3,I),(2,f),(3,j),(1,c),(2,g),(3,k)*lev_tree(a,m,n)(0,a),(1,b),(2322.樹的括號表示設(shè)T是一棵樹，則其括號表示σT的規(guī)則為：（1）如果樹T只有一個(gè)結(jié)點(diǎn)，則此結(jié)點(diǎn)就是它的括號表示（可直接用結(jié)點(diǎn)鍵值表示它）。（2）如果樹T是由根結(jié)點(diǎn)A和子樹T0，T1，…，Tm-1組成，則樹T的括號表示σT為A（σT0，σT1，…，σTm-1）p.117中間的樹的括號表示σT=A(σB,σC)=A(B(σD,σE,σF),C(σG))=A(B(D,E(σH,σI),F(σJ)),C(G(σK,σL)))=A(B(D,E(H,I),F(J)),C(G(K,L)))2.樹的括號表示設(shè)T是一棵樹，則其括號表示σT的規(guī)則為：332.樹的括號表示樹的括號表示，是一個(gè)字符串，將被存儲在字符數(shù)組中，用“\0”標(biāo)識括號表示結(jié)束。pp.119-120上的程序是實(shí)現(xiàn)由樹的括號表示建立一棵按標(biāo)準(zhǔn)形式存儲的m次樹的程序。其中結(jié)點(diǎn)鍵值為英文字母。程序用一個(gè)棧存放正在建立的子樹的根結(jié)點(diǎn)的地址。2.樹的括號表示樹的括號表示，是一個(gè)字符串，將被存儲在字345.6二叉樹二叉樹的定義一個(gè)有限的結(jié)點(diǎn)集合，或?yàn)榭?；或由一個(gè)根結(jié)點(diǎn)及表示為根結(jié)點(diǎn)的左右子樹的兩個(gè)互不相交的結(jié)點(diǎn)集合所組成，而根結(jié)點(diǎn)的左右子樹也是二叉樹。如5.6二叉樹二叉樹的定義355.6二叉樹二叉樹與m次樹的區(qū)別（1）二叉樹可為空，但是m次樹不能為空，至少有一個(gè)結(jié)點(diǎn)。（2）二叉樹中的結(jié)點(diǎn)可有兩棵子樹（可能其中一棵或兩棵為空），而m次樹的結(jié)點(diǎn)可有若干子樹。（3）在二叉樹中每個(gè)結(jié)點(diǎn)的子樹都是有序的，可用左、右子樹來區(qū)別，而m次樹的子樹間（若不特別指定）是無序的。5.6二叉樹二叉樹與m次樹的區(qū)別365.6二叉樹3.把任意次樹轉(zhuǎn)換成相應(yīng)的二叉樹描述性方法：若任意結(jié)點(diǎn)k有子結(jié)點(diǎn)k0,k1,…,km-1，則轉(zhuǎn)換后的二叉樹的結(jié)點(diǎn)k，它的左子結(jié)點(diǎn)為k0，而其他結(jié)點(diǎn)ki+1作為結(jié)點(diǎn)ki的右子結(jié)點(diǎn)（i=0,1,…,m-2）。5.6二叉樹3.把任意次樹轉(zhuǎn)換成相應(yīng)的二叉樹375.6二叉樹原樹的兩個(gè)結(jié)點(diǎn)轉(zhuǎn)換后的二叉樹相應(yīng)結(jié)點(diǎn)kk0k1k2k3kk0k1k2k3k01k02k03k01k02k035.6二叉樹原樹的兩個(gè)結(jié)點(diǎn)轉(zhuǎn)換后的二385.6二叉樹把多棵有序樹轉(zhuǎn)換成一棵二叉樹（1）方法若T=(T0,T1,…,Tm-1)是m棵樹的序列，則得到與樹T相對應(yīng)的二叉樹β(T)的法則為：如果m=0，那么β(T)為空的二叉樹；如果m>0，那么β(T)的根結(jié)點(diǎn)就是樹T0的根結(jié)點(diǎn)，β(T)的根結(jié)點(diǎn)的左子樹是β(A0,A1,…,Ar-1),其中A0,A1,…,Ar-1是樹T0的根結(jié)點(diǎn)的子樹；β(T)的根結(jié)點(diǎn)的右子樹是β（T1,T2,

…,Tm-1)。5.6二叉樹把多棵有序樹轉(zhuǎn)換成一棵二叉樹395.6二叉樹把多棵有序樹轉(zhuǎn)換成一棵二叉樹（2）舉例p.123三棵三次樹組成的有序樹林變換成一棵對應(yīng)的二叉樹（3）性質(zhì)如果T是有序樹組成的樹林，那么上面方法得到的與T相對應(yīng)的二叉樹β（T）是唯一的。5.6二叉樹把多棵有序樹轉(zhuǎn)換成一棵二叉樹405.6二叉樹算法pp.123-124的beta()函數(shù)的功能是將三棵或三棵以下的三次樹，用遞歸方法轉(zhuǎn)化為一棵二叉樹，返回這棵二叉樹的根結(jié)點(diǎn)的地址。做法：（1）第一棵樹的根結(jié)點(diǎn)變?yōu)槎鏄涞母Y(jié)點(diǎn)；（2）第一棵樹的根結(jié)點(diǎn)的子樹用beta()轉(zhuǎn)化成一棵二叉樹，為新樹的左子樹；（3）第二棵和第三棵樹用beta()轉(zhuǎn)化成一棵二叉樹，為新樹的右子樹。5.6二叉樹算法415.7二叉樹的遍歷1.復(fù)習(xí)前序和后序遍歷二叉樹（1）前序遍歷二叉樹typedefstructnode{intdata;structnode*lchild,*rchild;}NODE;NODE*t;

5.7二叉樹的遍歷1.復(fù)習(xí)前序和后序遍歷二叉樹42前序遍歷二叉樹算法（遞歸）voidr_preorder(NODE*t){if(t!=NULL){printf(“%d”,t->data);r_preorder(t->lchild);r_preorder(t->rchild);}}前序遍歷二叉樹算法（遞歸）voidr_preor431.復(fù)習(xí)前序和后序遍歷二叉樹后序遍歷二叉樹voidr_posorder(t)NODE*t;{if(t!=NULL){r_posorder(t->lchild);r_posorder(t->rchild);printf(“%d”,t->data);}}1.復(fù)習(xí)前序和后序遍歷二叉樹后序遍歷二叉樹445.7二叉樹的遍歷中序遍歷二叉樹(取結(jié)點(diǎn)垂直投影)（1）做法首先按中序遍歷根結(jié)點(diǎn)的左子樹；然后訪問根結(jié)點(diǎn)；最后按中序遍歷根結(jié)點(diǎn)的右子樹。5.7二叉樹的遍歷中序遍歷二叉樹(取結(jié)點(diǎn)垂直投影)452.中序遍歷二叉樹（2）中序遍歷二叉樹的遞歸算法voidr_midorder(t)NODE*t;{if(t!=NULL){r_midorder(t->lchild);printf(“%d”,t->data);r_midorder(t->rchild);}}2.中序遍歷二叉樹（2）中序遍歷二叉樹的遞歸算法462.中序遍歷二叉樹中序遍歷二叉樹的非遞歸算法pp.125-126函數(shù)s_midorder()使用“鏈接?！?，棧結(jié)點(diǎn)用于存放正在遍歷的子樹的根結(jié)點(diǎn)的地址。做法：（1）按前序順序?qū)⒔Y(jié)點(diǎn)一一進(jìn)棧；（2）當(dāng)棧頂結(jié)點(diǎn)的左子樹為空或左子樹處理完成時(shí)，遍歷棧頂結(jié)點(diǎn)。2.中序遍歷二叉樹中序遍歷二叉樹的非遞歸算法475.7二叉樹的遍歷采用逆轉(zhuǎn)鏈接指針的方法遍歷二叉樹這種方法不使用棧或遞歸。做法為：若當(dāng)前結(jié)點(diǎn)為k，當(dāng)需要向其左（或右）子樹運(yùn)動時(shí)，則逆轉(zhuǎn)它的左（或右）指針改指k的父結(jié)點(diǎn)，以便為將來“回溯”準(zhǔn)備路徑。若回溯經(jīng)過結(jié)點(diǎn)k，則修改指針恢復(fù)指向左（或右）子樹。設(shè)立標(biāo)志tag，若逆轉(zhuǎn)的是右指針，則令tag=1。5.7二叉樹的遍歷采用逆轉(zhuǎn)鏈接指針的方法遍歷二叉樹483.采用逆轉(zhuǎn)鏈接指針的方法遍歷二叉樹pp.127-128invert_link_order(t,i)為實(shí)現(xiàn)對給定的二叉樹用逆轉(zhuǎn)指針的方法進(jìn)行遍歷的函數(shù)。參數(shù)t為指向需要遍歷的樹的根結(jié)點(diǎn)的指針。參數(shù)i為遍歷方式的選項(xiàng)，若i=1，則按前序遍歷；若i=2，則按中序遍歷；若i=3，則按后序遍歷。注意：樹結(jié)點(diǎn)的結(jié)構(gòu)多一個(gè)字段tag。3.采用逆轉(zhuǎn)鏈接指針的方法遍歷二叉樹pp.127-128495.7二叉樹的遍歷4.二叉樹的遞歸操作（1）復(fù)制一個(gè)二叉樹p.129copy()（2）比較兩棵二叉樹是否等價(jià)p.130equiltree()5.7二叉樹的遍歷4.二叉樹的遞歸操作505.8二叉樹的順序存儲假如一棵二叉樹建立以后，不需要再進(jìn)行插入和刪除操作，那么，我們可以將樹結(jié)點(diǎn)依次順序存儲在一組連續(xù)的存儲單元（如數(shù)組）中，這便是二叉樹的順序存儲。具體方法有：按層次順序存儲按前序順序存儲（有附加左標(biāo)志和右指針方法、附加兩個(gè)標(biāo)志方法等）5.8二叉樹的順序存儲假如一棵二叉樹建立以511.按層次順序存儲二叉樹我們研究的這棵二叉樹應(yīng)滿足：（1）除了最后一層外，每層都放滿結(jié)點(diǎn)；（2）最后一層則結(jié)點(diǎn)從左到右逐一存放。用數(shù)學(xué)概念表示：設(shè)有n個(gè)結(jié)點(diǎn)的序列(k0,k1,…,kn-1)，令i=[log2(n+1)]，則將序列中的前面的(2i-1)個(gè)結(jié)點(diǎn)依次從上到下、從左到右放滿前i層（即第0層到第i-1層），剩下的n-(2i-1)個(gè)結(jié)點(diǎn)則依次從左到右放在第i層上。1.按層次順序存儲二叉樹我們研究的這棵二叉521.按層次順序存儲二叉樹假若將n個(gè)結(jié)點(diǎn)的序列(k0,k1,…,kn-1)依次存放在一維數(shù)組a[MAXN]中，那么就有：（1）當(dāng)0≤i≤[(n-2)/2]時(shí)，a[i]有左子結(jié)點(diǎn)a[2*i+1]；否則沒有左子結(jié)點(diǎn)。（2）當(dāng)0≤i≤[(n-3)/2]時(shí)，a[i]有右子結(jié)點(diǎn)a[2*i+2]；否則沒有右子結(jié)點(diǎn)。（3）當(dāng)1≤i≤n-1時(shí)，a[i]有父結(jié)點(diǎn)a[(i-1)/2]。（4）當(dāng)0≤i≤[(n-3)/2]時(shí)，a[2*i+1]和a[2*i+2]有相同的父結(jié)點(diǎn)。1.按層次順序存儲二叉樹假若將n個(gè)結(jié)點(diǎn)的序列(k0,535.8二叉樹的順序存儲按前序順序存儲二叉樹僅將二叉樹的結(jié)點(diǎn)按前序存放在一個(gè)一維數(shù)組中，不能反映樹中結(jié)點(diǎn)之間的關(guān)系。因此，需要附加一些信息。我們介紹下列兩種存儲方法：(1)附加左標(biāo)志和右指針(2)附加兩個(gè)標(biāo)志5.8二叉樹的順序存儲按前序順序存儲二叉樹54（1）附加左標(biāo)志和右指針的方法假設(shè)二叉樹中的結(jié)點(diǎn)已按前序依次存放在數(shù)組中。數(shù)組元素有三個(gè)字段：ltag,data和rchild。如果樹中的結(jié)點(diǎn)k有左子結(jié)點(diǎn)，那么它一定存放在結(jié)點(diǎn)k的后面。ltag是標(biāo)志結(jié)點(diǎn)k后面是否有左子結(jié)點(diǎn)，若有，ltag=0；若無，ltag=1。如果結(jié)點(diǎn)k有右子結(jié)點(diǎn)，那么rchild中存放它右子結(jié)點(diǎn)的數(shù)組元素的下標(biāo)；若無右子結(jié)點(diǎn)，則rchild=-1。舉例：p.132ltagdatarchild（1）附加左標(biāo)志和右指針的方法假設(shè)二叉樹中的結(jié)點(diǎn)已按前序55（1）附加左標(biāo)志和右指針的方法算法：#defineMAXN100typedefstructnode{intltag;chardata;intrchild;}NODE;NODEa[MAXN];introot=0;（1）附加左標(biāo)志和右指針的方法算法：56（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）的左子結(jié)點(diǎn)if(a[p].ltag==0)printf(“%c”,a[p+1].data);else<無左子結(jié)點(diǎn)，出錯(cuò)處理>（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）57（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）的右子結(jié)點(diǎn)if(a[p].rchild==-1)<無右子結(jié)點(diǎn)，出錯(cuò)處理>elseprintf(“%c”,a[a[p].rchild].data);（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）58（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）的按前序的前面結(jié)點(diǎn)if(p-1<0)<結(jié)點(diǎn)k沒有按前序的前面結(jié)點(diǎn)，出錯(cuò)處理>elseprintf(“%c”,a[p-1].data);（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）59（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）的按前序的后面結(jié)點(diǎn)if(p+1>=n)<結(jié)點(diǎn)k沒有按前序的后面結(jié)點(diǎn)，出錯(cuò)處理>elseprintf(“%c”,a[p+1].data);（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）60（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）的父結(jié)點(diǎn)if(p-1<0)<結(jié)點(diǎn)k沒有父結(jié)點(diǎn)>elseif(a[p-1].ltag==0)printf(“%c”,a[p-1].data);else{for(q=p-1;a[q].rchild!=p;q--);printf(“%c”,a[q].data);}

（1）附加左標(biāo)志和右指針的方法查找結(jié)點(diǎn)k（存放在a[p]中）61請畫出下面數(shù)組的樹0A60B31D-10E51G-11H-11C70F-11I-1請畫出下面數(shù)組的樹0A60B31D-10E51G-11H-162(2)附加兩個(gè)標(biāo)志的方法假設(shè)二叉樹中的結(jié)點(diǎn)已按前序依次存放在數(shù)組中。數(shù)組元素有三個(gè)字段：ltag,data和rtag。

字段ltag是標(biāo)志結(jié)點(diǎn)k是否有左子結(jié)點(diǎn)，若有，ltag=0；若無，ltag=1。字段rtag是標(biāo)志結(jié)點(diǎn)k是否有右子結(jié)點(diǎn)，若有，rtag=0；若無，rtag=1。ltagdatartag(2)附加兩個(gè)標(biāo)志的方法假設(shè)二叉樹中的結(jié)點(diǎn)63(2)附加兩個(gè)標(biāo)志的方法在存放二叉樹的數(shù)組中，假如結(jié)點(diǎn)k的ltag=0，那么，緊跟在后面的是它的左子結(jié)點(diǎn)；當(dāng)ltag=1，則結(jié)點(diǎn)k沒有左子結(jié)點(diǎn)。問題是結(jié)點(diǎn)k的右子結(jié)點(diǎn)怎么找？尋找的原則：（1）右子結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的ltag=1，也就是說，ltag=1的結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)一定是右子結(jié)點(diǎn)。（2）將右子結(jié)點(diǎn)與前面最靠近的rtag=0的結(jié)點(diǎn)配對，形成父子關(guān)系。試用上述原則畫出p.134上數(shù)組表示的樹。(2)附加兩個(gè)標(biāo)志的方法在存放二叉樹的數(shù)組中64(2)附加兩個(gè)標(biāo)志的方法pp.134-135transfer(tree,n)功能是將存儲在數(shù)組tree[]中n個(gè)結(jié)點(diǎn)表示的二叉樹轉(zhuǎn)換成按標(biāo)準(zhǔn)形式存儲的二叉樹。算法使用了棧stack[]，用于存放要找右子結(jié)點(diǎn)的父結(jié)點(diǎn)（rtag=0）的地址（指針）。棧頂下標(biāo)top指向棧頂結(jié)點(diǎn)的上面一個(gè)位置。(2)附加兩個(gè)標(biāo)志的方法pp.134-135tra655.9穿線樹和穿線排序用標(biāo)準(zhǔn)形式存儲一棵有n個(gè)結(jié)點(diǎn)的二叉樹，每個(gè)結(jié)點(diǎn)有兩個(gè)指針，共有2*n個(gè)指針，但只有n-1個(gè)指針用于指向子結(jié)點(diǎn)，而n+1個(gè)指針是空的。這是一種浪費(fèi)。于是可利用這些空指針，作為“穿線”。5.9穿線樹和穿線排序665.9穿線樹和穿線排序

1.穿線