C++程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)：第10章 非線性結(jié)構(gòu)

1、第三部分第三部分 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)本章內(nèi)容 樹(shù)的基本概念 二叉樹(shù)的基本概念和性質(zhì) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的遍歷 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 2 210.1 樹(shù)的基本概念l 樹(shù)：是一類(lèi)非常重要的非線性結(jié)構(gòu)，適合于描述數(shù)據(jù)元素之間的層次關(guān)系。3 3l 樹(shù)是n(n0)個(gè)數(shù)據(jù)元素的有限集合T。它滿(mǎn)足以下兩個(gè)條件：P2671.有且僅有一個(gè)特定的稱(chēng)為根的元素。 一棵樹(shù)中，有且僅有一個(gè)根結(jié)點(diǎn)。 根是只有后件沒(méi)有前件的結(jié)點(diǎn)。 除根結(jié)點(diǎn)外，其它結(jié)點(diǎn)均有且僅有一個(gè)前件。 每個(gè)結(jié)點(diǎn)均可以有任意多個(gè)后件，沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其余稱(chēng)內(nèi)結(jié)點(diǎn)。2.其余元素分為m（m0）個(gè)互不相交的有限

2、集合T1、T2、Tm，其中每個(gè)集合又都是一棵樹(shù)并稱(chēng)其為根的子樹(shù)。數(shù)學(xué)上的定義4 4A AB BE EF FK KL LC CG GMMD DHHNNI IJ JA AB BE EL L5 5樹(shù)的常用術(shù)語(yǔ)l 雙親、子女、兄弟、邊： 若結(jié)點(diǎn)y是結(jié)點(diǎn)x的一棵子樹(shù)的根，則x稱(chēng)做y的“雙親”(parents)，y稱(chēng)做x的“子女”(child) 有序?qū)ΨQ(chēng)做從x到y(tǒng)的“邊”。 具有同一雙親的結(jié)點(diǎn)稱(chēng)為“兄弟”。l 路徑、路徑長(zhǎng)度： 若樹(shù)中存在著一個(gè)結(jié)點(diǎn)的序列k1 k2kj，使ki是ki+1（1i0，則ki雙親結(jié)點(diǎn)的編號(hào)為 (i-1)/2； 若i=0，則ki是根結(jié)點(diǎn)。 若2i+1n，則ki左子女結(jié)點(diǎn)的編號(hào)是2i

3、+1，否則ki無(wú)左子女。若2i+2n，則ki右子女結(jié)點(diǎn)的編號(hào)為2i+2，否則ki無(wú)右子女。1616二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) l 順序存儲(chǔ)結(jié)構(gòu) 對(duì)完全二叉樹(shù)，利用性質(zhì)5，將其所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一維數(shù)組里。 對(duì)一般二叉樹(shù)，需要加上一些并不存在的“虛結(jié)點(diǎn)”，轉(zhuǎn)換為完全二叉樹(shù)的形式。 1717l 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈接存儲(chǔ)時(shí)結(jié)點(diǎn)的結(jié)構(gòu)lchilddatarchildA AB BC C F F D D E EG GHHrootroot存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)1818二叉樹(shù)的遍歷l 先序遍歷 ：訪問(wèn)根結(jié)點(diǎn)(D)，先序遍歷左子樹(shù)(L)，先序遍歷右子樹(shù)(R)。 ABDGECFl 中序遍歷：LDR DGBEAFCl 后序遍歷：LRD GDEBFCAl 層次遍歷：按層數(shù)由小到大、同一層從左到右順序依次訪問(wèn)二叉樹(shù)的各個(gè)結(jié)點(diǎn)。 ABCDEFG1919樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 l 樹(shù)到二叉樹(shù)的轉(zhuǎn)換1. 在所有的兄弟之間加一條連線；2. 對(duì)每個(gè)結(jié)點(diǎn)，除了保留與最左邊子女的連線外，去掉與其他子女連線；3. 將保留下來(lái)的邊作為左子樹(shù)的邊，兄弟間的連線作為右子樹(shù)的邊。2020l 森林到二叉樹(shù)的轉(zhuǎn)換1. 先將森林中的每一棵樹(shù)變?yōu)槎鏄?shù)，2. 然后將各二叉樹(shù)的根結(jié)點(diǎn)看成兄弟，用線把它們連到一起，3. 經(jīng)整理后可得到相應(yīng)的二叉樹(shù)。2121l 二叉樹(shù)到樹(shù)、森林的