數(shù)據(jù)結(jié)構(gòu)第09次課-樹C課件

調(diào)課通知本周（第5周）星期一1~2節(jié)的數(shù)據(jù)結(jié)構(gòu)課調(diào)到：本周（第5周）星期四5~6節(jié) 教室：L24121等級(jí)考試反思：1.英文(尤其計(jì)算機(jī)專業(yè)英語(yǔ))很重要,很多考生英文版的VC環(huán)境不會(huì)用。比如：編譯compile,運(yùn)行execute2.熟悉編程環(huán)境很重要。Java的運(yùn)行環(huán)境很多，JCreator,Eclipse,(適合初學(xué)),NetBeans等等。3.總結(jié)前兩條，自學(xué)很重要。學(xué)時(shí)有限，上課講授的內(nèi)容有限。網(wǎng)絡(luò)是最好的自學(xué)工具。2上堂課內(nèi)容回顧1.二叉樹的遍歷

DLRLDRLRD先

(根)序遍歷中

(根)序遍歷后(根)序遍歷

口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根先序遍歷：ABDGCEF后序遍歷：GDBEFCA中序遍歷：DGBAECF3voidtraversal(BinTreeNoderoot){if(root){

printf(“%c”,root.getData());

traversal(root.getLChild());

printf(“%c”,root.getData()

);

traversal(root.getRChild());}}ABCDE遍歷增強(qiáng)版：右圖二叉樹執(zhí)行下列操作輸出序列是什么？先序＋中序遍歷：第一次經(jīng)過和第二次經(jīng)過時(shí)都訪問到。ABDDBEEACC5特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？已證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。

例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請(qǐng)畫出這棵二叉樹。分析：①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。6中序遍歷：BDCEAFHG

后序遍歷：DECBHGFA（BDCE）（FHG）ABF（DCE）（HG）CDEGHABBFF7ABCDEFGH先序遍歷：ABCDEFGH

后序遍歷：DECBHGFA問：若已知先序和后序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？FGH8注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。思路：利用先序遍歷來建樹（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜）BinTreeNode

createBTpre(){BinTreeNodeT;charch;scanf(“%c”,ch);if(ch==’#’)T=NULL;else{T=newBinTreeNode();T.setData(ch);T.setLChild(createBTpre());T.setRChild(createBTpre());}returnT;}怎樣建樹？ABFCDEGHAB#CD##E##F#GH###10思考：采用二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息？二叉鏈表只能找到結(jié)點(diǎn)的左右孩子信息，而不能得到結(jié)點(diǎn)在任一序列中的前驅(qū)和后繼信息，這種信息只有在遍歷過程中才能得到，我們可否對(duì)二叉鏈表進(jìn)行改造？?jī)煞N解決方法增加兩個(gè)域：fwd和bwd；利用空鏈域（n+1個(gè)空鏈域）存放前驅(qū)指針存放后繼指針——我們可以用這n+1個(gè)空鏈域來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。－>二叉線索樹12規(guī)定：1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個(gè)標(biāo)志域，如下圖所示：lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)Tag域?yàn)?時(shí),表示線索情況.14有關(guān)線索二叉樹的幾個(gè)術(shù)語(yǔ)：線索鏈表：用上面結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹：加上線索的二叉樹（圖形式樣）

線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程注：在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時(shí)，則需要通過一定運(yùn)算才能找到它的后繼。lchildLTagdataRTagrchild15dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例1：帶了兩個(gè)標(biāo)志的某先序遍歷結(jié)果如表所示，請(qǐng)畫出對(duì)應(yīng)二叉樹。162.線索二叉樹的生成線索化過程就是在遍歷過程中修改空指針的過程：將空的lchild改為結(jié)點(diǎn)的直接前驅(qū)；將空的rchild改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況”）17ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,

G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例2：畫出以下二叉樹對(duì)應(yīng)的中序線索二叉樹。為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)184.給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。

2825405560330854解:因?yàn)橹行虮闅v序列是：5540256028083354對(duì)應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。NULLNULL206.4樹和森林樹和森林的存儲(chǔ)方式樹和森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷21ABCGEIDHF缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。01234567812233ABCDEFGHI-1001例1:雙親表示法23思路：將每個(gè)結(jié)點(diǎn)的孩子排列起來，形成一個(gè)帶表頭（裝父結(jié)點(diǎn)）的鏈表（n個(gè)結(jié)點(diǎn)要設(shè)立n個(gè)鏈表）；再將n個(gè)表頭用數(shù)組存放起來，這樣就形成一個(gè)混合結(jié)構(gòu)。例如：abecdfhgdefghgfedcbah123456782、用孩子表示法來存儲(chǔ)bc24abecdfhgbacedfgh問：樹轉(zhuǎn)二叉樹的“連線—抹線—旋轉(zhuǎn)”如何由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)？答：用“左孩子右兄弟”表示法來存儲(chǔ)即可。

存儲(chǔ)的過程就是轉(zhuǎn)換的過程！例如：262.樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點(diǎn)的兄弟相連;step2:保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；step3:將同一層孩子的連線繞左孩子旋轉(zhuǎn)45度角。加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？27方法：加線—抹線—旋轉(zhuǎn)

abeidfhgc樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長(zhǎng)兄為父孩子靠左根結(jié)點(diǎn)肯定沒有右孩子！28法一：①各棵樹先各自轉(zhuǎn)為二叉樹；②依次連到前一個(gè)二叉樹的右子樹上。討論3：森林如何轉(zhuǎn)為二叉樹？法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹即F={T1,T2,…,Tm}B={root,LB,RB}30ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉(zhuǎn)二叉樹舉例：（法二）兄弟相連長(zhǎng)兄為父孩子靠左頭根為根A31討論4：二叉樹如何還原為森林？要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>

ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}323、樹和森林的遍歷先根遍歷訪問根結(jié)點(diǎn)；依次先序遍歷根結(jié)點(diǎn)的每棵子樹。樹的遍歷例如：abdec先序序列：后序序列：abcdebdcea

后根遍歷依次后序遍歷根結(jié)點(diǎn)的每棵子樹；訪問根結(jié)點(diǎn)。樹沒有中根遍歷（因子樹不分左右）遍歷深度遍歷（先序、后序）廣度遍歷（層次）33討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.樹的先根遍歷二法相同；2.

樹的后根遍歷相當(dāng)于對(duì)應(yīng)二叉樹的中序遍歷；3.

樹沒有中根遍歷，因?yàn)樽訕錈o左右之分。結(jié)論：34先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷若森林為空，返回；中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問第一棵樹的根結(jié)點(diǎn)；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷ABCDEFGHJI35討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先序和中序遍歷在兩種方式下的結(jié)果相同。（但森林的后序遍歷則不一定）36//求二叉樹的深度intBTreeDepth(BTreeNodeBT){

if(BT==NULL)

return0;//對(duì)于空樹，返回0并結(jié)束遞歸

else{

//計(jì)算左子樹的深度

i