C++數據結構學習：二叉樹(2)

　　線索化二叉樹
　　
　　 　　這是數據結構課程裡第一個碰到的難點，不知道你是不是這樣看，反正我當初是費了不少腦細胞——當然，惱人的矩陣壓縮和相關的加法乘法運算不在考慮之列。 <!-- frame contents --> <!-- /frame contents --> 我費了不少腦細胞是因為思考：他們干什麼呢？很欣喜的看到在這本黃皮書上，這章被打了*號，雖然我不確定作者是不是跟我一個想法——線索化二叉樹在現在的PC上是毫無用處的！——不知我做了這個結論是不是會被人罵死，^_^。
　　
　　 　　為了證實這個結論，我們來看看線索化二叉樹提出的緣由：第一，我們想用比較少的時間，尋找二叉樹某一個遍歷線性序列的前驅或者後繼。當然，這樣的操作很頻繁的時候，做這方面的改善才是有意義的。第二，二叉樹的葉子節點還有兩個指針域沒有用，可以節省內存。說真的，提出線索化二叉樹這樣的構思真的很精巧，完全做到了“廢物利用”——這個人真應該投身環保事業。但在計算機這個死板的東西身上，人們的精巧構思往往都是不能實現的——為了速度，計算機的各個部件都是整潔劃一的，而構思的精巧往往都是建立在組成的復雜上的。
　　
　　 　　我們來看看線索化二叉樹究竟能不能達到上面的兩個目標。
　　
　　 　　求遍歷後的線性序列的前驅和後繼。前序線索化能依次找到後繼，但是前驅需要求雙親；中序線索化前驅和後繼都不需要求雙親，但是都不很直接；後序線索化能依次找到前驅，但是後繼需要求雙親。可以看出，線索化成中序是最佳的選擇，基本上算是達到了要求。
　　
　　 　　節省內存。添加了兩個標志位，問題是這兩個位怎麼儲存？即使是在支持位存儲的CPU上，也是不能拿位存儲器來存的，第一是因為結構體成員的地址是在一起的，第二是位存儲器的數目是有限的。因此，最少需要1個字節來儲存這兩個標志位。而為了速度和移植，一般來說，內存是要對齊的，實際上根本就沒節省內存！然而，當這個空間用來儲存雙親指針時，帶來的方便絕對不是線索化所能比擬的，前面已經給出了無棧的非遞歸遍歷。並且，在線索化二叉樹上插入刪除操作附加的代價太大。
　　
　　 　　綜上，線索化最好是中序線索化（前序後序線索化後還得用棧，何必要線索化呢），附加的標志域空間至少1個字節，在32位的CPU會要求對齊到4字節，還不如存儲一個雙親指針，同樣能達到中序線索化的目的，並且能帶來其他的好處。所以，線索化二叉樹在現在的PC上是毫無用處的！
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　由於對其他體系不太了解，以下觀點姑妄聽之。在內存空間非常充裕的現在，一個節點省2～3個字節實在是沒什麼意思（實際上由於對齊還省不出來）；而在內存非常寶貴的地方（比如單片機），會盡量避免使用樹結構——利用其他的方法。所以，現在看來，線索化二叉樹真的是毫無用處了。 <!-- frame contents --> <!-- /frame contents -->
　　
　　 　　二叉搜索樹
　　 　　這恐怕是二叉樹最重要的一個應用了。它的構想實際是個很自然的事情——查找值比當前節點小轉左，大轉右，等則查到，到頭了就是沒找著。越自然的東西越好理解，也就越不需要我廢話。在給出BST的實現之前，我們要在二叉樹的類中添加一個打印樹狀結構的成員函數，這樣，就能清楚的看出插入和刪除過程。
　　
　　 　　public:
　　 　　
　　 　　voidprint()
　　
　　 　　{
　　
　　 　　queue*>a;queueflag;ofstreamoutfile("out.txt");
　　
　　 　　BTNode*p=root;BTNodezero;boolv=true;
　　
　　 　　inti=1,level=0,h=height();
　　
　　 　　while(i<2<　　
　　 　　{
　　
　　 　　if(i==1<　　
　　 　　{
　　
　　
　　 　　cout<　　
　　 　　if(v)cout　　
　　 　　elsecout<<'';
　　 　　
　　 　　}
　　
　　 　　else
　　 　　
　　 　　{
　　 　　
　　 　　cout<　　 　　
　　 　　if(v)cout　　 　　
　　 　　elsecout<<"";
　　 　　
　　 　　}
　　 　　
　　 　　if(p->left){a.push(p->left);flag.push(true);}
　　 　　
　　 　　else{a.push(&zero);flag.push(false);}
　　 　　
　　 　　if(p->right){a.push(p->right);flag.push(true);}
　　 　　
　　 　　else{a.push(&zero);flag.push(false);}
　　 　　
　　 　　p=a.front();a.pop();v=flag.front();flag.pop();i++;
　　 　　
　　 　　}
　　 　　
　　 　　cout<　　 　　
　　 　　}
　　 　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　
　　 　　打印樹狀結構的核心是按層次遍歷二叉樹，但是，二叉樹有許多節點缺左或右子樹，連帶的越到下面空隙越大。 <!-- frame contents --> <!-- /frame contents --> 為了按照樹的結構打印，必須把二叉樹補成完全二叉樹，這樣下面的節點就知道放在什麼位置了——a.push(&zero);但是這樣的節點不能讓它打印出來，所以對應每個節點，有一個是否打印的標志，按理說pair結構很合適，為了簡單我用了並列的兩個隊列，一個放節點指針——a，一個放打印標志——flag。這樣一來，循環結束的標志就不能是隊列空——永遠都不可能空，碰到NULL就補一個節點——而是變成了到了滿二叉樹的最後一個節點2^(height+1)-1。——黃皮書對於樹高的定義是，空樹為的高度為－1。
　　 　　
　　 　　對於輸出格式，注重的是到了第1、2、4、8號節點要換行，並且在同一行中，第一個節點的域寬是後序節點的一半。上面的函數在樹的層次少於等於5（height<=4）的時候能正常顯示，再多的話就必須輸出到文件中去ofstreamoutfile("out.txt");——假如層次再多的話，打印出來也沒什麼意義了。
　　 　　
　　 　　二叉搜索樹的實現
　　 　　實際上就是在二叉樹的基礎上增加了插入、刪除、查找。
　　 　　
　　 　　#include"BaseTree.h"
　　 　　
　　 　　template
　　 　　
　　 　　classBSTree:publicBTree
　　 　　
　　 　　{
　　 　　
　　 　　public:
　　 　　
　　 　　BTNode*&find(constT&data)
　　 　　
　　 　　{
　　 　　
　　 　　BTNode**p=&root;current=NULL;
　　 　　
　　 　　while(*p)
　　 　　
　　 　　{
　　 　　
　　 　　if((*p)->data==data)break;
　　 　　
　　 　　if((*p)->dataright);}
　　 　　
　　 　　else{current=*p;p=&((*p)->left);}
　　 　　
　　 　　}
　　 　　
　　 　　return*p;
　　 　　
　　 　　}
　　 　　
　　 　　boolinsert(constT&data)
　　 　　
　　 　　{
　　 　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　BTNode*&p=find(data);if(p)returnfalse;
　　 　　
　　 　　p=newBTNode(data,NULL,NULL,current);returntrue;
　　 　　
　　 　　}
　　 　　
　　 　　boolremove(constT&data)
　　 　　
　　 　　{
　　 　　
　　 　　returnremove(find(data));
　　 　　
　　 　　}
　　 <!-- frame contents --> <!-- /frame contents --> 　　
　　 　　private:
　　 　　
　　
　　 　　boolremove(BTNode*&p)
　　 　　
　　 　　{
　　 　　
　　 　　if(!p)returnfalse;BTNode*t=p;
　　 　　
　　 　　if(!p->left!p->right)
　　 　　
　　 　　{
　　 　　
　　 　　if(!p->left)p=p->right;elsep=p->left;
　　 　　
　　 　　if(p)p->parent=current;
　　 　　
　　 　　deletet;returntrue;
　　 　　
　　 　　}
　　 　　
　　 　　t=p->right;while(t->left)t=t->left;p->data=t->data;current=t->parent;
　　 　　
　　 　　returnremove(current->left==t？current->left:current->right);
　　 　　
　　 　　}
　　 　　
　　 　　};
　　 　　
　　 　　以上代碼有點費解，有必要說明一下——非線性鏈式結構操作的實現都是很讓人費神。insert和remove都是以find為基礎的，因此必須讓find能最大限度的被這兩個操作利用。
　　 　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　對於insert，需要修改查找失敗時的指針內容，顯然這是個內部指針（在雙親節點的內部，而不是象root和current那樣在節點外面指向節點），這就要求find返回一個內部指針的引用。但是C++的引用綁定到一個對象之後，就不能再改變了，因此在find內部的實現是一個二重指針。insert操作還需要修改插入的新節點的parent指針域，因此在find中要產生一個能被insert訪問的指向find返回值所在節點的指針，這裡用的是current。實際上find返回的指針引用不是current->left就是current->right。這樣一來，insert的實現就非常簡單了。
　　 　　
　　 　　對於remove，需要修改查找成功時的指針內容，同樣是個內部指針。在find的基礎上，很輕易就能得到這個內部指針的引用(BTNode*&p=find(data)。
　　 　　
　　 　　在p->left和p->right中至少有一個為NULL的情況下，假如p->left==NULL，那麼就重連右子樹p=p->right，反之，重連左子樹p=p->left。注重，左右子樹全空的情況也包含在這兩個操作中了——在p->left==NULL的時候重連右子樹，而這時p->right也是NULL——因此不必列出來。假如重連後p不為空，需要修改p->parent=current。
　　 　　
　　 　　若p->left和p->right都不為空，可以轉化為有一個為空。例如一個中序有序序列[1,2,3,4,5]，假設3既有左子樹又有右子樹，那麼它的前驅2一定缺右子樹，後繼4一定缺少左子樹。【注1】這樣一來刪除節點3就等效成從[1,2,3(4),4,5]刪除節點4。這樣就可以利用上面的在p->left和p->right中至少有一個為NULL的情況下的方法了。還是由於C++的引用不能改變綁定對象，這裡是用利用遞歸來解決的，還好最多只遞歸一次。假如用二重指針又是滿天星星了，這就是明明是尾遞歸卻沒有消去的原因。
　　 　　
　　 　　【注1】這是因為，假如3既有左子樹又有右子樹，那麼2一定在3的左子樹上，4一定在3的右子樹上；假如2有右子樹，那麼在2和3之間還應該有一個節點；假如4有左子樹，那麼3和4之間也應該還有一個節點。
　　 　　
　　 　　【閒話】上面關於remove操作p->left和p->right都不為空的處理方法的講解，源於嚴蔚敏老師的課件，看完後我豁然開朗，真不知道為什麼她自己那本《數據結構（C語言版）》這裡寫的那麼難懂，我是死活沒看明白。
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或