數(shù)據(jù)結(jié)構(gòu)與算法-樹

6樹2/50第5章樹樹的邏輯表示、基本概念樹、森林與二叉樹的相互轉(zhuǎn)換樹、森林的周游由周游序列確定二叉樹UNION/FIND算法3/50樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。當(dāng)n=0時(shí)，稱為空樹；在任意一棵非空樹中滿足如下條件：

(1)有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。

(2)其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m>0）個(gè)互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。

樹的概念4/50(1)樹型表示法。這是樹的最基本的表示,使用一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象。樹的邏輯表示法5/50(2)文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。樹的邏輯表示法6/50(3)凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。樹的邏輯表示法7/50(4)括號(hào)表示法(廣義表表示法)。將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來描述樹結(jié)構(gòu)。樹的邏輯表示法8/50樹結(jié)構(gòu)中的概念沒有子樹的結(jié)點(diǎn)稱作樹葉或終端結(jié)點(diǎn)

非終端結(jié)點(diǎn)稱為分支結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為度數(shù)根結(jié)點(diǎn)的層數(shù)為0，其它任何結(jié)點(diǎn)的層數(shù)等于它的父結(jié)點(diǎn)的結(jié)點(diǎn)層數(shù)加19/50樹結(jié)構(gòu)中的概念有序樹在樹T中如果子樹T1，T2，…，Tm的相對(duì)次序是重要的，則稱樹T為有向有序樹，簡(jiǎn)稱有序樹。在有序樹中可以稱T1是根的第一棵子樹，T2是根的第二棵子樹，等等10/50森林與樹森林(forest)

森林是零棵或多棵不相交的樹的集合(通常是有序集合)。11/50(1)在所有相鄰兄弟結(jié)點(diǎn)之間加一水平連線。(2)對(duì)每個(gè)非葉結(jié)點(diǎn)k,除了其最左邊的孩子結(jié)點(diǎn)外,刪去k與其他孩子結(jié)點(diǎn)的連線。(3)所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度，使之結(jié)構(gòu)層次分明。樹做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹是唯一的。樹轉(zhuǎn)換為二叉樹12/50加邊刪邊調(diào)整13/50將樹轉(zhuǎn)換為二叉樹的形式表示。令結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)兒子和右邊的兄弟。RBACDEFHGK∧∧∧RADBE∧C∧F∧G∧∧H∧K∧∧14/50森林轉(zhuǎn)換為二叉樹的方法如下：（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

森林轉(zhuǎn)換為二叉樹15/5016/50將一棵二叉樹還原為樹或森林，具體方法如下：（1）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。（2）刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。（3）整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。二叉樹還原為樹或森林17/50二叉樹到森林的轉(zhuǎn)換示例1.添加連線2.刪除右孩子節(jié)點(diǎn)的連線3.整理18/50樹的周游深度優(yōu)先先根次序后根次序廣度優(yōu)先寬度優(yōu)先周游（層次周游）19/501）先根次序若樹非空，則遍歷方法為：①訪問根結(jié)點(diǎn)。②從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。

先根次序周游序列ABECFHGD等同于轉(zhuǎn)換的二叉樹進(jìn)行先序周游樹的周游20/502)后根次序若樹非空，則遍歷方法為：①?gòu)淖蟮接?，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹。②訪問根結(jié)點(diǎn)。

后根次序周游序列為EBHFGCDA等同于轉(zhuǎn)換的二叉樹進(jìn)行中序周游樹的周游21/50樹的周游按廣度方向周游寬度優(yōu)先周游也稱為層次周游層次周游序列為ABCDEFGH22/50森林的周游深度優(yōu)先先根次序后根次序廣度優(yōu)先寬度優(yōu)先周游（層次周游）23/501）先根次序若森林非空，則遍歷方法為：①訪問森林中第一棵樹的根結(jié)點(diǎn)。②先根次序周游第一棵樹的根結(jié)點(diǎn)的子樹森林。③先根次序周游其他的樹。

先根周游序列為ABCDEFGHIJ等同于轉(zhuǎn)換的二叉樹進(jìn)行先序周游森林的周游24/502）后根次序若森林非空，則遍歷方法為：①后根次序周游森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。②訪問第一棵樹的根結(jié)點(diǎn)。③后根次序周游其他的樹。

后根周游序列為BCDAFEHJIG等同于轉(zhuǎn)換的二叉樹進(jìn)行中序遍歷森林的周游25/50森林的周游按廣度方向周游寬度優(yōu)先周游（層次周游）層次周游序列為AEGBCDFHIJ26/50關(guān)于二叉樹的先序、中序和后序周游序列確定二叉樹的問題。給定先序、中序周游序列可唯一確定二叉樹。給定后序、中序周游序列可唯一確定二叉樹由周游序列確定二叉樹27/50任何n(n≥0)個(gè)不同結(jié)點(diǎn)的二叉樹,都可由它的中序序列和先序序列唯一地確定。證明：先序序列是a1a2…an中序序列是b1b2…bn根結(jié)點(diǎn)：a1。在中序序列中與a1相同的結(jié)點(diǎn)為：bj。

{b1…bj-1}bj{bj+1…bn}←→a1{a2…ak}{ak+1…an}28/50例：已知先序序列為ABDGCEF,中序序列為DGBAECF根結(jié)點(diǎn)：G左先序:空左中序:空右先序:空右中序:空根結(jié)點(diǎn)：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根結(jié)點(diǎn)：B左先序:DG左中序:DG右先序:空右中序:空根結(jié)點(diǎn)：D左先序:空左中序:空右先序:G右中序:G根結(jié)點(diǎn)：C左先序:E左中序:E右先序:F右中序:F根結(jié)點(diǎn)：E左先序:空左中序:空右先序:空右中序:空根結(jié)點(diǎn)：F左先序:空左中序:空右先序:空右中序:空29/50思考1實(shí)現(xiàn)由先序、中序序列構(gòu)造二叉樹的算法：30/50任何n(n＞0)個(gè)不同結(jié)點(diǎn)的二叉樹,都可由它的中序序列和后序序列唯一地確定。證明：后序序列是a1a2…an中序序列是b1b2…bn根結(jié)點(diǎn)：an。在中序序列中與an相同的結(jié)點(diǎn)為：bj。{b1…bj-1}bj{bj+1…bn}←→{a1a2…ak}{ak+1…an-1}an31/50例：后序序列為GDBEFCA,中序序列為DGBAECF根結(jié)點(diǎn)：A左中序:DGB左根:B右中序:ECF右根:C根結(jié)點(diǎn)：B左中序:DG左根:D右中序:空右根:空根結(jié)點(diǎn)：D左中序:空左根:空右中序:G右根:G根結(jié)點(diǎn)：G左中序:空左根:空右中序:空右根:空根結(jié)點(diǎn)：C左中序:E左根:E右中序:F右根:F根結(jié)點(diǎn)：E左中序:空左根:空右中序:空右根:空根結(jié)點(diǎn)：F左中序:空左根:空右中序:空右根:空32/50思考2實(shí)現(xiàn)由后序、中序序列構(gòu)造二叉樹的算法：33/50①給定樹的先根周游序列和后根周游序列可唯一畫出一棵樹。②給定森林的先根周游序列和后根周游序列可唯一確定一森林。

由周游序列確定樹或者森林34/50樹的存儲(chǔ)父指針表示法35/50父指針表示法父指針(parentpointer)表示法：每個(gè)結(jié)點(diǎn)只保存一個(gè)指針域指向其父結(jié)點(diǎn).如果兩個(gè)結(jié)點(diǎn)到達(dá)同一根結(jié)點(diǎn)，它們一定在同一棵樹中。36/50父指針數(shù)組表示法父節(jié)點(diǎn)索引標(biāo)記結(jié)點(diǎn)索引37/50等價(jià)類的并查

（UNION/FIND）算法

并查算法包含兩種基本操作：判斷兩個(gè)結(jié)點(diǎn)是否在同一個(gè)集合中，查找一個(gè)給定結(jié)點(diǎn)的根結(jié)點(diǎn)的過程稱為FIND歸并兩個(gè)集合，這個(gè)歸并過程常常被稱為UNION整個(gè)操作以“UNION/FIND算法”（也可以翻譯為“并查算法”）命名38/50UNION/FIND算法示例10個(gè)結(jié)點(diǎn)A、B、C、D、E、F、G、H、J、K和它們的等價(jià)關(guān)系（A,B）、(C,K)、(J,F)、(H,E)、(D,G)、(K,A)、(E,G)、(H,J)39/50UNION/FIND算法示例對(duì)這5個(gè)等價(jià)對(duì)的處理結(jié)果

（A,B）、(C,K)、(J,F)、(H,E)、(D,G)40/50UNION/FIND算法示例對(duì)兩個(gè)等價(jià)對(duì)（K，A）和（E，G）的處理結(jié)果

41/50UNION/FIND算法實(shí)現(xiàn)循環(huán)鏈表的思想root[]標(biāo)識(shí)頂點(diǎn)集合的頂點(diǎn)索引next[]指示鏈表中的下一個(gè)頂點(diǎn)length[]指示鏈表中的頂點(diǎn)數(shù)目42/50UNION/FIND算法示例(一)012435root012345next012345length111111vertices012345union(0,1)012435root002345next102345length211111vertices012345union(4,3)43/50UNION/FIND算法示例(二)25root002445next102435length211121vertices012345root004445next103425length211131vertices012345union(2,3)014301524344/50UNION/FIND算法示例(三)root004440next503421length311131vertices012345243501015root004445next103425length211131vertices012345union(0,5)24345/50UNION/FIND算法示例(四)root004440next503421length311131vertices012345243501union(2,5)root444444next203451length311161vertices01234524350146/50UNION/FIND定義classUFSets{private:

intn;

int*root;

int*next;

int*length;public:

UFSets(intsize);

int

Find(intv); voidUnion(int

v,intu);};47/50UNION/FIND算法initialize()fori=0to|v|-1

root[i]=next[i]=i;

length[i]=1;48/50UNION/FIND算法（續(xù)）union(intv，intu)

if(root[u]==root[v])return;elseif(length[root[v]]<length[root[u]])

rt=root[v];

length[root[u]]+=length[rt];

root[rt]=root[u];

for(j=next[rt];j!=rt;j=next[j])