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

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

2、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（普通的一棵樹） 由圖可見：

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

4、形態(tài)的二叉樹 【1】：一棵高度為h2.1滿二叉樹0且有2h+1-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。 （如圖3.1） 圖3.1 （滿二叉樹） 【1】：完全二叉樹2.2若一棵二叉樹至多只有最下面的兩層結(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)不同，

5、那么就不等，顯然這時要用先序遍歷； 3.1.1前序遍歷 public: void PreOrder(void (*visit)(T &data) = print) PreOrder(root, visit); private: void p, PreOrder(BTNode* 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) In

6、Order(root, visit); private: void InOrder(BTNode* p, void (*visit)(T &data) if (p) InOrder(p-left, 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)

7、 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ù)單元中。 （如圖4.1） 圖4.1 （完全二叉樹的結(jié)點(diǎn)編號） 我們將數(shù)組下標(biāo)作為結(jié)點(diǎn)編號，就可將二叉樹中所有結(jié)點(diǎn)的標(biāo)號存儲在一維數(shù)組中。 （如圖4.2） 圖4.2 可以看到二叉樹的這種表示方式下，各結(jié)點(diǎn)之間的邏輯關(guān)系是隱含表示的

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

9、存儲樹中的結(jié)點(diǎn)。一個只有k個結(jié)k個結(jié)點(diǎn)的存儲空2-1點(diǎn)的右單枝樹卻需要 間。的右單二叉樹，添上虛結(jié)點(diǎn)3假設(shè)結(jié)點(diǎn)為）4.2圖如（。樹叉二滿似近棵一為成，后 可知這樣造4.3 圖 成的存儲空間的浪費(fèi) 、索化二叉樹5當(dāng)用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，5.1因?yàn)槊總€結(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 圖 （線索鏈表）由圖5.2可知：在二叉樹的線索鏈表上增

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

11、有意義的。 7.2證明：求遍歷后的線性序列的前驅(qū)和后繼。 7.2.1先序線索化能依次找到后繼，但是前驅(qū)需要求雙親；中序線索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅(qū)，但是后繼需要求雙親。可以看出，線索化成中序是最佳的選擇，基本上算是達(dá)到了要求。 7.2.2節(jié)省內(nèi)存：線索化增加了兩個標(biāo)志位，但是這兩個位怎么儲存？即使是在支持位存儲的CPU上，也不能拿位存儲器來存的，第一是因?yàn)榻Y(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)存空間用來儲存雙親指針時，帶來的方便絕對不是線索化所