數(shù)據(jù)結(jié)構(gòu)二叉樹ppt

1、校長，一，二，三，六系，教務(wù)處，科研處，總務(wù)處，每個節(jié)點(diǎn)(根節(jié)點(diǎn)除外)只有一個直接前驅(qū)節(jié)點(diǎn)。3 .每個節(jié)點(diǎn)(包括根節(jié)點(diǎn))可以有多個后續(xù)節(jié)點(diǎn)。4 .樹顯示，1 .節(jié)點(diǎn)的度：2。樹的度：3。葉節(jié)點(diǎn)：4。分支節(jié)點(diǎn)：5。層次的定義：該節(jié)點(diǎn)擁有的子樹的數(shù)目。樹中的最大節(jié)點(diǎn)數(shù)。圖0中的節(jié)點(diǎn)，圖0中的節(jié)點(diǎn)，根節(jié)點(diǎn)在第一層，節(jié)點(diǎn)(如果有)在第一層，7 .林(林)由： m0棵不相交的樹組成的樹集合.8 .二進(jìn)制樹的基本形式：(空)，6.2二進(jìn)制樹，2 .兩種特殊形式的二叉樹，1 .非空二進(jìn)制樹的層i最多包含2i1個節(jié)點(diǎn)(i1)。2 .深度為h的非空二叉樹最多可以有2h -1個節(jié)點(diǎn)。3 .如果非空二叉樹中有n0個

2、葉節(jié)點(diǎn)，n2度為2的節(jié)點(diǎn)，則n0=n2 1，4。具有n個節(jié)點(diǎn)的整個二叉樹的深度h=log2n 1。二叉樹的存儲結(jié)構(gòu)2。一般二叉樹順序存儲結(jié)構(gòu)，2 .二叉樹鏈存儲結(jié)構(gòu)(二次鏈表)，2 .前一個順序遍歷，3 .中間順序巡回，4。后序遍歷，前序遍歷序列3360a，b，d，k，j連續(xù)遍歷序列3360 d，g，j，k，b，e，i，f，h，c，a，按層次順序3360a，遍歷結(jié)果是求節(jié)點(diǎn)的線性序列。指向線性序列“前導(dǎo)”和“后續(xù)”的指針稱為“線索”。包含“線索”的存儲結(jié)構(gòu)相應(yīng)的二叉樹稱為“線索二叉樹”。把二叉樹按某種順序遍歷，變成線索二叉樹的過程稱為“線索化”。2 .2.在雙叉鏈接表的節(jié)點(diǎn)結(jié)構(gòu)中添加兩個標(biāo)志域

3、的線索鏈接表的節(jié)點(diǎn)結(jié)構(gòu)。其中：ltag=，0 lchild域表示節(jié)點(diǎn)的左側(cè)ii 1 lchild域表示節(jié)點(diǎn)的前置任務(wù)，rtag=，0 rchild域表示節(jié)點(diǎn)/link=0:指針，thread=1:線索threadstruct bithrnode *lchild，* rchild/左和右眼指針pointerthr ltag，rtag/左和右徽標(biāo)bithrnode，* bithrtree，3 .線索二叉樹圖例，線索二叉樹和存儲結(jié)構(gòu)(a)中間順序線索二叉樹(b)中間順序線索鏈表，如果右邊的標(biāo)志為 1 ，則組合中間順序線索樹，右邊的鏈?zhǔn)蔷€索，右邊的鏈直接表示節(jié)點(diǎn)的后面。如果右側(cè)標(biāo)志為“0”，則右側(cè)鏈為

4、指針，然后是右側(cè)子樹最左側(cè)的底部節(jié)點(diǎn)。如何在線索樹中查找節(jié)點(diǎn)的前兆？與中間順序線索樹一起，如果左標(biāo)志為“1”，左鏈為線索，則直接指示該前置任務(wù)。如果左側(cè)標(biāo)志為“0”，則左側(cè)子樹的最右下方節(jié)點(diǎn)是前一個節(jié)點(diǎn)。線索鏈接列表的中間順序遍歷算法status iotraver _ t (bith rtree t，status (* visit) (t elemtype e)/t指向標(biāo)頭節(jié)點(diǎn)，標(biāo)頭節(jié)點(diǎn)的左鏈lchild指向根節(jié)點(diǎn)p=t-lchild；/p根節(jié)點(diǎn)while (p！=t) /空樹或巡回結(jié)束時p=t while(p-ltag=link)p=p-lchild；if(！visit(p-data)ret

5、urn error:/左側(cè)子樹為空節(jié)點(diǎn)while(p-rtag=thread/io traver _ t，6.4.2樹系和樹和二叉樹之間的對應(yīng)，將樹轉(zhuǎn)換為二叉樹方法：1)從左到右排列每個孩子。2)在兄弟之間添加連接。3)對于每個節(jié)點(diǎn)，刪除與其他孩子的連接(左側(cè)孩子除外)。4)旋轉(zhuǎn)根節(jié)點(diǎn)，將整個樹順時針旋轉(zhuǎn)45。2 .森林和二叉樹之間的對應(yīng)關(guān)系可以從樹的次鏈表表達(dá)的定義中看出?？梢?，與樹對應(yīng)的二叉樹中，至少有一個右邊的子樹是空的。(約翰f肯尼迪，northern exposure(美國電視劇)，如果將森林中第二棵樹的根節(jié)點(diǎn)看作第一棵樹的根節(jié)點(diǎn)的兄弟，那么還可以導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。已知條件

6、：設(shè)置森林和二叉樹的對應(yīng)關(guān)系林f=(t1，t2，tn)；t1=(根，t11，t12，t1m)；二叉樹b=(lbt，節(jié)點(diǎn)(根)，rbt)；從森林到二叉樹的轉(zhuǎn)換規(guī)則為： f=b=；否則，從根(t1)映射節(jié)點(diǎn)(根)。lbt對應(yīng)于(t11，t12，t1m)。rbt對應(yīng)于(t2，t3，tn)。從二進(jìn)制樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為： b=f=；否則，獲取節(jié)點(diǎn)(根)的相應(yīng)根(t1)。lbt響應(yīng)(t11、t12、t1m)；除t1根外，森林是通過rbt反應(yīng)(t2，t3，tn)獲得的。t1以外的樹林，6.4.3樹木和森林的巡回，1 .遍歷樹：三條搜索路徑首先通過根(順序)。如果樹不是空的，則首先訪問根節(jié)點(diǎn)，然后依次遍

7、歷每個子樹。遍歷后根(順序):如果樹不是空的，則依次遍歷每個子樹，然后訪問根節(jié)點(diǎn)。按層次結(jié)構(gòu)遍歷：如果結(jié)構(gòu)樹不為空，則從上到下從左到右訪問結(jié)構(gòu)樹中的每個節(jié)點(diǎn)。例如，樹的第一根橫移，獲得的第一根順序?yàn)椋簶涞淖詈蟾鶛M移，得到的根順序?yàn)椋篴 b e f c d g h i，e f b c g h i d a，2。森林的橫移，第一次橫移(林中每棵樹的第一根橫移)1)如果不是林，則2)先遍歷林中第一棵樹的子樹林。3)首先巡回森林(第一棵樹除外)剩下的樹組成的森林。后巡回(后巡回)林中每棵樹的后巡回)1)如果林不空，后巡回(后巡回)林中第一棵樹的子樹林。2)訪問森林中第一棵樹的根節(jié)點(diǎn)。3)依次巡回森林(第一棵樹除外)剩下的樹組成的森林。例如：首先遍歷森林，獲得的順序如下：后巡回森林，得到的后巡順序如下：b e f c d g h i，e f b c g h i d，摘要：1。二叉樹的線索化2。樹的表示及其巡回工作；設(shè)置森林和