數(shù)據(jù)結(jié)構(gòu)-二叉樹(c++)

數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++).數(shù)據(jù)結(jié)構(gòu)——二叉樹〔c++〕[摘要]現(xiàn)實(shí)社會中的樹——書籍的目錄、任務(wù)大綱、家族族譜之類等等。人們要研究就必須能過將樹正確的儲存，如何存儲又關(guān)系到實(shí)際的操作。樹是否為空，在本學(xué)期學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的教材中允許樹為空[1]。因為樹表現(xiàn)形式的是一種現(xiàn)實(shí)的結(jié)構(gòu)，而0不是自然數(shù)。從直觀上看樹是分支關(guān)系定義的層次結(jié)構(gòu)，其中樹和二叉樹是最常見的[1]。[關(guān)鍵詞]數(shù)據(jù)結(jié)構(gòu)；樹；二叉樹；遍歷；探討空間；1、二叉樹1.1二叉樹T是有限的結(jié)點(diǎn)的集合〔允許為空〕，或者由一個根結(jié)點(diǎn)u以與分別稱為左子樹和右子樹的兩棵互不相交的二叉樹u(1)和u(2)組成。若用n,n1和n2分別表示T，u(1)和u(2)的結(jié)點(diǎn)數(shù)，則有n=1+n1+n2。u(1)和u(2)有時分別稱為T的第一和第二子樹。在二叉樹中，每個結(jié)點(diǎn)至多有兩個孩子，并且有左、右之分。因此任一結(jié)點(diǎn)的孩子不外4種情況：沒有孩子；只有一個左孩子；只有一個右孩子；有一個左孩子并且有一個右孩子。〔如圖1.1〕圖1.1五種基本形態(tài)〔其中□表示空〕1.2二叉樹與度數(shù)不超過2的樹不同，與度數(shù)不超過2的有序樹也不同。在有序樹中，雖然一個結(jié)點(diǎn)的孩子之間是有左右次序的，但若該結(jié)點(diǎn)只有一個孩子時，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個孩子也有左右之分。圖1.2a〔不同的兩顆二叉樹〕圖1.2b〔普通的一棵樹〕數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第1頁。由圖可見：(a)和(b)是兩棵不同的二叉樹。雖然它們與普通數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第1頁。所以，二叉樹是一種人們假設(shè)的一種現(xiàn)象，所以允許為空是無爭議的。二叉樹是一種有序的樹，左邊是孩子、右邊是兄弟。其實(shí)可以看作不同的兩棵樹。做這個規(guī)定，正式因為人們要賦予給孩子兄弟不同的意義。通過這學(xué)期的學(xué)習(xí)發(fā)現(xiàn)了一個現(xiàn)象，就是樹并沒有插入刪除操作。對于非線性的樹結(jié)構(gòu)，插入刪除操作不在一定的法則規(guī)定下，是毫無意義的。因此，只有在具體的應(yīng)用中，才會有插入刪除操作。2、特殊形態(tài)的二叉樹2.1滿二叉樹[1]：一棵高度為h≥0且有2h+1-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹?！踩鐖D3.1〕圖3.1〔滿二叉樹〕2.2完全二叉樹[1]：若一棵二叉樹至多只有最下面的兩層結(jié)點(diǎn)的度數(shù)小于2，并且最下面一層結(jié)點(diǎn)都集中在該層的最左邊，則稱這種二叉樹為完全二叉樹。〔如圖3.2〕圖3.2〔完全二叉樹〕3、二叉樹的遍歷以與實(shí)現(xiàn)〔c++〕3.1二叉樹基本上有先序遍歷、中序遍歷、后序遍歷，最開始并不明白為什么有這么多，到了后面才明白，這是不同的應(yīng)用需要的。例如，刪除二叉樹，必須先刪除左右子樹，然后才能刪除根節(jié)點(diǎn)，這時就要用后序遍歷，而判斷兩個二叉樹是否相等，只要子樹根節(jié)點(diǎn)不同，那么就不等，顯然這時要用先序遍歷；數(shù)據(jù)結(jié)構(gòu)——二叉樹數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第2頁。public:voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}private:voidPreOrder(BTNode*p,void(*visit)(T&data)){if(p){visit(p->data);PreOrder(p->left,visit);PreOrder(p->right,visit);}}3.1.2public:voidInOrder(void(*visit)(T&data)=print){InOrder(root,visit);}private:voidInOrder(BTNode*p,void(*visit)(T&data)){if(p){InOrder(p->left,visit);visit(p->data);InOrder(p->right,visit);}}3.1.3public:voidPostOrder(void(*visit)(T&data)=print){PostOrder(root,visit);}private:voidPostOrder(BTNode*p,void(*visit)(T&data)){if(p){PostOrder(p->left,visit);PostOrder(p->right,visit);visit(p->data);}}4、二叉樹的順序存儲結(jié)構(gòu)4.1在一棵具有n個結(jié)點(diǎn)的近似滿二叉樹中，我們從樹根起，自上到下，逐層從左到右給所有結(jié)點(diǎn)編號，就能得到一個足以反映整個二叉樹結(jié)構(gòu)的線性序列。所以，順序存儲結(jié)構(gòu)是二叉樹的一種特點(diǎn)，按照一定的順序存儲在特定的連續(xù)單元中?！踩鐖D4.1〕數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第3頁。圖4.1〔完全二叉樹的結(jié)點(diǎn)編號〕我們將數(shù)組下標(biāo)作為結(jié)點(diǎn)編號，就可將二叉樹中所有結(jié)點(diǎn)的標(biāo)號存儲在一維數(shù)組中?！踩鐖D4.2〕圖4.2可以看到二叉樹的這種表示方式下，各結(jié)點(diǎn)之間的邏輯關(guān)系是隱含表示的。完全二叉樹中，除最下面一層外，各層都充滿了結(jié)點(diǎn)。除最底層外，每一層的結(jié)點(diǎn)個數(shù)恰好是上一層結(jié)點(diǎn)個數(shù)的2倍。因此，從一個結(jié)點(diǎn)的編號就可推知其父親，左孩子、右兄弟，等各結(jié)點(diǎn)的編號。假設(shè)對結(jié)點(diǎn)為i的二叉樹有如下定義：僅當(dāng)i=1時，結(jié)點(diǎn)i為根結(jié)點(diǎn)；當(dāng)i>1時，結(jié)點(diǎn)i的父結(jié)點(diǎn)為[i/2]；結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)為2i；結(jié)點(diǎn)i的右孩子結(jié)點(diǎn)為2i+1；當(dāng)i為奇數(shù)且不為1時，結(jié)點(diǎn)i的左兄弟結(jié)點(diǎn)為i-1；當(dāng)i為偶數(shù)時，結(jié)點(diǎn)i的右兄弟結(jié)點(diǎn)為i+1。4.2但對于一般的二叉樹，采用順序存儲時，為了能用結(jié)點(diǎn)在數(shù)組中的位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系，也必須按近似滿二叉樹的形式來存儲樹中的結(jié)點(diǎn)。一個只有k個結(jié)點(diǎn)的右單枝樹卻需要2k-1個結(jié)點(diǎn)的存儲空間。數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第4頁。假設(shè)結(jié)點(diǎn)為3的右單二叉樹，添上虛結(jié)點(diǎn)后，成為一棵近似滿二叉樹。〔如圖數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第4頁。圖4.3可知這樣造成的存儲空間的浪費(fèi)5、索化二叉樹5.1當(dāng)用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，因為每個結(jié)點(diǎn)中只有指向其左、右孩子結(jié)點(diǎn)的指針，所以從任一結(jié)點(diǎn)出發(fā)只能直接找到該結(jié)點(diǎn)的左、右孩子。在一般情況下靠它無法直接找到該結(jié)點(diǎn)在某種遍歷序下的前驅(qū)和后繼結(jié)點(diǎn)。如果在每個結(jié)點(diǎn)中增加指向其前驅(qū)和后繼結(jié)點(diǎn)的指針，將降低存儲空間的效率。例：一棵中序線索二叉樹如〔圖5.1〕：圖5.1圖5.2〔線索鏈表〕數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第5頁。由圖數(shù)據(jù)結(jié)構(gòu)——二叉樹(c++)全文共6頁，當(dāng)前為第5頁。6、探討線索化二叉樹是否降低空間效率7.1線索化二叉樹提出的緣由：第一，二叉樹的葉子節(jié)點(diǎn)還有兩個指針域沒有用，可以節(jié)省內(nèi)存。第二，我們想用比較少的時間，尋找二叉樹某一個遍歷線性序列的前驅(qū)或者后繼。當(dāng)然，這樣的操作很頻繁的時候，做這方面的改善才是有意義的。7.2證明：求遍歷后的線性序列的前驅(qū)和后繼。先序線索化能依次找到后繼，但是前驅(qū)需要求雙親；中序線索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅(qū)，但是后繼需要求雙親?？梢钥闯?，線索化成中序是最佳的選擇，基本上算是達(dá)到了要求。節(jié)省內(nèi)存：線索化增加了兩個標(biāo)志位，但是這兩個位怎么儲存？即使是在支持位存儲的CPU上，也不能拿位存儲器來存的，第一是因為結(jié)構(gòu)體成員變量的內(nèi)存地址是在連續(xù)的一起的，第二是位存儲器的存儲數(shù)目是有限的。目前的計算機(jī)最少需要1個字節(jié)來儲存這兩個標(biāo)志位。而為了傳輸速度和內(nèi)存移植，大部分的內(nèi)存是要對齊的，這就導(dǎo)致在內(nèi)存中使用線索化二叉樹根本就沒節(jié)省內(nèi)存。假設(shè)把個內(nèi)存空間用來儲存雙親指針時，帶來的方便絕對不是線索化所能比擬的，前面已經(jīng)給出了無棧的非遞歸遍歷。并且，在線索化二叉樹上插入刪