1、數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)(C+)【摘要】現(xiàn)實(shí)社會(huì)中的樹(shù) 一一書(shū)籍的目錄、任務(wù)大綱、家族族譜之類等等。人們要研究就必須能過(guò)將樹(shù)正確的儲(chǔ)存，如何存儲(chǔ)又關(guān)系到實(shí)際的操作 樹(shù)是否為空，在本學(xué)期學(xué)習(xí)的數(shù)據(jù)結(jié) 構(gòu)的教材中允許樹(shù)為空 【1】。因?yàn)闃?shù)表現(xiàn)形式的是一種現(xiàn)實(shí)的結(jié)構(gòu)，而o不是自然數(shù).從直觀上看樹(shù)是分支關(guān)系定義的層次結(jié)構(gòu)，其中樹(shù)和二叉樹(shù)是最常見(jiàn)的【關(guān)鍵詞】數(shù)據(jù)結(jié)構(gòu)；樹(shù)；二叉樹(shù)；遍歷；探討空間；1、二叉樹(shù)1.1二叉樹(shù)T是有限的結(jié)點(diǎn)的集合 (允許為空)，或者由一個(gè)根結(jié)點(diǎn) u以及分別稱為左子 樹(shù)和右子樹(shù)的兩棵互不相交的二叉樹(shù)u(1)和u( 2)組成。若用n,n1和n2分別表示T, u(1)和u (2)的結(jié)點(diǎn)數(shù)，則有n

2、=1+ n1+n2 。u(1 )和u(2)有時(shí)分別稱為T(mén)的第一和第二子樹(shù)。在二叉樹(shù)中，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子，并且有左、右之分。因此任一結(jié)點(diǎn)的孩子不外4種情況：沒(méi)有孩子；只有一個(gè)左孩子；只有一個(gè)右孩子；有一個(gè)左孩子并且有一個(gè)右孩子。圖1.1五種基本形態(tài)(其中 口 表示空)1.2 二叉樹(shù)與度數(shù)不超過(guò) 2的樹(shù)不同，與度數(shù)不超過(guò)2的有序樹(shù)也不同。在有序樹(shù)中，雖 然一個(gè)結(jié)點(diǎn)的孩子之間是有左右次序的，但若該結(jié)點(diǎn)只有一個(gè)孩子時(shí)，就無(wú)須區(qū)分其左右次序。而在二叉樹(shù)中，即使是一個(gè)孩子也有左右之分。由圖可見(jiàn)：(a)和(b)是兩棵不冋的二叉樹(shù)。雖然它們與普通的一棵樹(shù)(作為無(wú)序樹(shù)或有序圖1。2a (不同的兩顆二叉樹(shù))

3、圖1。2b (普通的一棵樹(shù))樹(shù)）很相似，但它們卻不能等同于這棵普通的樹(shù)。若將這 3棵樹(shù)均看作是有序樹(shù)，則它們就 是相同的了。所以二叉樹(shù)和樹(shù)盡管有很多相似 ，但是二叉樹(shù)不是樹(shù)的特殊情形。所以，二叉樹(shù)是一種人們假設(shè)的一種現(xiàn)象 ，所以允許為空是無(wú)爭(zhēng)議的二叉樹(shù)是一種有序 的樹(shù)，左邊是孩子、右邊是兄弟。其實(shí)可以看作不同的兩棵樹(shù)。做這個(gè)規(guī)定 ，正式因?yàn)槿藗?要賦予給孩子兄弟不同的意義。 通過(guò)這學(xué)期的學(xué)習(xí)發(fā)現(xiàn)了一個(gè)現(xiàn)象， 就是樹(shù)并沒(méi)有插入刪除 操作。對(duì)于非線性的樹(shù)結(jié)構(gòu)，插入刪除操作不在一定的法則規(guī)定下，是毫無(wú)意義的 因此， 只有在具體的應(yīng)用中，才會(huì)有插入刪除操作。2、特殊形態(tài)的二叉樹(shù)2。1滿二叉樹(shù) 卬：一棵

4、高度為h> 0且有2h+1-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。（如圖3。1）圖3.1（滿二叉樹(shù)）2。2完全二叉樹(shù) “：若一棵二叉樹(shù)至多只有最下面的兩層結(jié)點(diǎn)的度數(shù)小于2，并且最下面一層結(jié)點(diǎn)都集中在該層的最左邊，則稱這種二叉樹(shù)為完全二叉樹(shù)（如圖3。2）圖3.2（完全二叉樹(shù)）3、二叉樹(shù)的遍歷以及實(shí)現(xiàn)（C+）3。1二叉樹(shù)基本上有先序遍歷、 中序遍歷、后序遍歷，最開(kāi)始并不明白為什么有這么多， 到了后面才明白，這是不同的應(yīng)用需要的。例如，刪除二叉樹(shù)，必須先刪除左右子樹(shù)，然后才能刪除根節(jié)點(diǎn)，這時(shí)就要用后序遍歷，而判斷兩個(gè)二叉樹(shù)是否相等，只要子樹(shù)根節(jié)點(diǎn)不同，那么就不等，顯然這時(shí)要用先序遍歷；3.1.1 前序

5、遍歷public:void PreOrder(void (衣 visit) (T &data)= print) PreOrder(root, visit) ;private:void PreOrder(BTNode* p ， void (*visit) (T data)if (p) visit(p>data)；PreOrder(p->left, visit);PreOrder(p-right， visit)；3。1.2 中序遍歷public：void InOrder(void (visit) (T data) = print) InOrder(root, visit); p

6、rivate ： void InOrder(BTNode* p ， void (*visit ) (T &data)if (p) InOrder(pleft, visit) ;visit(p data)；InOrder(p- > right, visit); 3。1。 3 后序遍歷public：void PostOrder(void (visit) (T data) = print ) PostOrder(root, visit); private:void PostOrder(BTNode p, void (*visit)(T &data) )if ( p) PostO

7、rder(p->left, visit);PostOrder(p> right, visit ) ;visit (p->data);4、二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)4.1 在一棵具有 n 個(gè)結(jié)點(diǎn)的近似滿二叉樹(shù)中,我們從樹(shù)根起，自上到下，逐層從左到右給所有結(jié)點(diǎn)編號(hào)，就能得到一個(gè)足以反映整個(gè)二叉樹(shù)結(jié)構(gòu)的線性序列.所以，順序存儲(chǔ)結(jié)構(gòu)是二叉樹(shù)的一種特點(diǎn),按照一定的順序存儲(chǔ)在特定的連續(xù)單元中。(如圖 4.1)圖4.1（完全二叉樹(shù)的結(jié)點(diǎn)編號(hào)）我們將數(shù)組下標(biāo)作為結(jié)點(diǎn)編號(hào)，就可將二叉樹(shù)中所有結(jié)點(diǎn)的標(biāo)號(hào)存儲(chǔ)在一維數(shù)組中。（如圖4.2）圖4.2可以看到二叉樹(shù)的這種表示方式下，各結(jié)點(diǎn)之間的邏輯關(guān)系是隱含表

8、示的。完全二叉樹(shù)中，除最下面一層外，各層都充滿了結(jié)點(diǎn)。除最底層外，每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層 結(jié)點(diǎn)個(gè)數(shù)的2倍。因此，從一個(gè)結(jié)點(diǎn)的編號(hào)就可推知其父親，左孩子、右兄弟，等各結(jié)點(diǎn)的編號(hào).假設(shè)對(duì)結(jié)點(diǎn)為i的二叉樹(shù)有如下定義：1. 僅當(dāng)i=1時(shí)，結(jié)點(diǎn)i為根結(jié)點(diǎn)；2. 當(dāng)i1時(shí)，結(jié)點(diǎn)i的父結(jié)點(diǎn)為i/2；3. 結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)為 2i；4. 結(jié)點(diǎn)i的右孩子結(jié)點(diǎn)為 2i+1 ；5. 當(dāng)i為奇數(shù)且不為1時(shí)，結(jié)點(diǎn)i的左兄弟結(jié)點(diǎn)為i-1 ；6. 當(dāng)i為偶數(shù)時(shí)，結(jié)點(diǎn)i的右兄弟結(jié)點(diǎn)為i+1。4。2但對(duì)于一般的二叉樹(shù)，采用順序存儲(chǔ)時(shí)，為了能用結(jié)點(diǎn)在數(shù)組中的位置來(lái)表示結(jié)點(diǎn) 之間的邏輯關(guān)系，也必須按近似滿二叉樹(shù)的形式來(lái)存儲(chǔ)

9、樹(shù)中的結(jié)點(diǎn)。一個(gè)只有k個(gè)結(jié)點(diǎn)的右單枝樹(shù)卻需要 2k-1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間.假設(shè)結(jié)點(diǎn)為 3的右單二叉樹(shù)，添上虛結(jié)點(diǎn)后，成為一棵近似滿二叉樹(shù)。（如圖4。2）5、索化二叉樹(shù)5。1當(dāng)用二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，因?yàn)槊總€(gè)結(jié)點(diǎn)中只有指向其左、右孩子結(jié) 點(diǎn)的指針，所以從任一結(jié)點(diǎn)出發(fā)只能直接找到該結(jié)點(diǎn)的左、右孩子。在一般情況下靠它 無(wú)法直接找到該結(jié)點(diǎn)在某種遍歷序下的前驅(qū)和后繼結(jié)點(diǎn)。如果在每個(gè)結(jié)點(diǎn)中增加指向其 前驅(qū)和后繼結(jié)點(diǎn)的指針，將降低存儲(chǔ)空間的效率。例:一棵中序線索二叉樹(shù)如（圖5.1）:圖5.1圖5.2（線索鏈表）由圖5。2可知：在二叉樹(shù)的線索鏈表上增加了一個(gè)頭結(jié)點(diǎn)，其LeftChild指針指向二叉樹(shù)的

10、根結(jié)點(diǎn)，其 RightChild指針指向中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn).另外，二叉樹(shù)中依中序列表的第一個(gè)結(jié)點(diǎn)的 LeftChild 指針，和最后一個(gè)結(jié)點(diǎn)的 RightChild 指針都指向頭結(jié)點(diǎn) .這 就像為二叉樹(shù)建立了一個(gè)雙向線索鏈表,既可從第一個(gè)結(jié)點(diǎn)起，順著后繼進(jìn)行遍歷，也可從最后一個(gè)結(jié)點(diǎn)起順著前驅(qū)進(jìn)行遍歷。6、探討線索化二叉樹(shù)是否降低空間效率7.1 線索化二叉樹(shù)提出的緣由： 第一，二叉樹(shù)的葉子節(jié)點(diǎn)還有兩個(gè)指針域沒(méi)有用，可以節(jié)省內(nèi)存。第二， 我們想用比較少的時(shí)間， 尋找二叉樹(shù)某一個(gè)遍歷線性序列的前驅(qū)或者后繼。 當(dāng)然， 這樣的操作很頻繁的時(shí)候，做這方面的改善才是有意義的 .7.2 證明：求遍歷后的

11、線性序列的前驅(qū)和后繼。7.2。1 先序線索化能依次找到后繼 ,但是前驅(qū)需要求雙親； 中序線索化前驅(qū)和后繼都不需 要求雙親 ,但是都不很直接； 后序線索化能依次找到前驅(qū) ,但是后繼需要求雙親。 可以看出， 線索化成中序是最佳的選擇，基本上算是達(dá)到了要求。7。2.2 節(jié)省內(nèi)存： 線索化增加了兩個(gè)標(biāo)志位， 但是這兩個(gè)位怎么儲(chǔ)存 ?即使是在支持位存 儲(chǔ)的CPU上，也不能拿位存儲(chǔ)器來(lái)存的，第一是因?yàn)榻Y(jié)構(gòu)體成員變量的內(nèi)存地址是在連 續(xù)的一起的，第二是位存儲(chǔ)器的存儲(chǔ)數(shù)目是有限的。目前的計(jì)算機(jī)最少需要1 個(gè)字節(jié)來(lái)儲(chǔ)存這兩個(gè)標(biāo)志位。而為了傳輸速度和內(nèi)存移植，大部分的內(nèi)存是要對(duì)齊的，這就導(dǎo)致 在內(nèi)存中使用線索化二叉樹(shù)根本就沒(méi)節(jié)省內(nèi)存。 假設(shè)把個(gè)內(nèi)存空間用來(lái)儲(chǔ)存雙親指針時(shí)， 帶來(lái)的方便絕對(duì)不是線索化所能比