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

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

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