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

　　這些天參與了CSDN論壇的討論，改變了我以前的一些看法。回頭看我以前的東西，我雖對這本書很不滿，但我還是按照它的安排在一點點的寫；這樣就導致了，我過多的在意書中的偏漏，我寫的更多是說“這本書怎樣”，而偏離了我寫這些的初衷——給正在學習數據結構的人一些幫助。 <!-- frame contents --> <!-- /frame contents --> 正像我在前面所說的，雖然現有的教科書都不是很合理，但假如僅僅是抱怨這點，那無異於潑婦罵街。雖然本人的水平連初級都夠不上，但至少先從我做一點嘗試，以後這門課的教授方法必將一點點趨於合理。
　　
　　 　　因此，後面不在按照書上的次序，將本著“實際應用（算法）決定數據結構”的思想來講解，常見教科書上有的，基本不再重點敘述（除了重點，例如AVL樹的平衡旋轉），——因此，在看本文的同時，一定要有一本教科書。這只是一個嘗試，希望大家多提寶貴意見。
　　
　　 　　樹
　　 　　因為現實世界中存在這“樹”這種結構——族譜、等級制度、目錄分類等等，而為了研究這類問題，必須能夠將樹儲存，而如何儲存將取決於所需要的操作。這裡有個問題，是否答應存在空樹。有些書認為樹都是非空的，因為樹表示的是一種現實結構，而0不是自然數；我用過的教科書都是說可以有空樹，當然是為了和二叉樹統一。這個沒有什麼原則上的差別，反正就是一種習慣。
　　
　　 　　二叉樹
　　 　　二叉樹可以說是人們假想的一個模型，因此，答應有空的二叉樹是無爭議的。二叉樹是有序的，左邊有一個孩子和右邊有一個的二叉樹是不同的兩棵樹。做這個規定，是因為人們賦予了左孩子和右孩子不同的意義，在二叉樹的各種應用中，你將會清楚的看到。下面只講解鏈式結構。看各種講數據結構的書，你會發現一個有趣的現象：在二叉樹這裡，基本操作有計算樹高、各種遍歷，就是沒有插入、刪除——那樹是怎麼建立起來的？其實這很好理解，對於非線性的樹結構，插入刪除操作不在一定的法則規定下，是毫無意義的。因此，只有在具體的應用中，才會有插入刪除操作。
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　節點結構
　　 　　數據域、左指針、右指針肯定是必須的。除非很少用到節點的雙親，或者是資源緊張，建議附加一個雙親指針，這將會給很多算法帶來方便，尤其是在這個“空間換時間”的時代。
　　
　　 　　template
　　
　　 　　strUCtBTNode
　　
　　 　　{
　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　BTNode(Tdata=T(),BTNode*left=NULL,BTNode*right=NULL,BTNode*parent=NULL)
　　 　　
　　 　　:data(data),left(left),right(right),parent(parent){}
　　 　　
　　 　　BTNode*left,*right,*parent;
　　 　　
　　 　　Tdata;
　　 　　
　　 　　};
　　
　　 　　基本的二叉樹類
　　 　　template
　　 　　
　　 　　classBTree
　　 　　
　　 　　{
　　
　　 　　public:
　　 　　
　　 　　BTree(BTNode*root=NULL):root(root){}
　　 　　
　　 　　~BTree(){MakeEmpty();}
　　 　　
　　 　　voidMakeEmpty(){destroy(root);root=NULL;}
　　
　　 　　protected:
　　 　　
　　 　　BTNode*root；
　　 　　
　　 　　private:
　　 　　
　　 　　voiddestroy(BTNode*p)
　　 　　
　　 　　{
　　 　　
　　 　　if(p)
　　 　　
　　 　　{
　　 　　
　　 　　destroy(p->left);
　　 　　
　　 　　destroy(p->right);
　　 　　
　　 　　deletep;
　　 　　
　　 　　}
　　 　　
　　 　　}
　　 　　
　　 　　}
　　
　　 　　二叉樹的遍歷
　　 　　基本上有4種遍歷方法，先、中、後根，逐層。當初我對這個很迷惑，搞這麼多干什麼？到了後面才明白，這是不同的應用需要的。例如，判定兩個二叉樹是否相等，只要子樹根節點不同，那麼就不等，顯然這時要用先序遍歷；而刪除二叉樹，必須先刪除左右子樹，然後才能刪除根節點，這時就要用後序遍歷。
　　
　　 　　
　　 　　實際上，搞這麼多遍歷方法，根本原因是在內存中儲存的樹是非線性結構。對於用數組儲存的二叉樹，這些名目繁多的方法都是沒有必要的。利用C++的封裝和重載特性，這些遍歷方法能很清楚的表達。
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　1.前序遍歷
　　
　　 　　public:
　　 　　
　　 　　voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}
　　 　　
　　 　　private:
　　 　　
　　 　　voidPreOrder(BTNode*p,void(*visit)(T&data))
　　 　　
　　 　　{
　　 　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　if(p){visit(p->data);PreOrder(p->left,visit);PreOrder(p->right,visit);}
　　 　　
　　 　　}
　　 　　
　　 　　2.中序遍歷
　　 　　
　　 　　public:
　　 　　
　　 　　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.後序遍歷
　　
　　 　　public:
　　
　　 　　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.層次遍歷
　　 　　
　　 　　voidLevelOrder(void(*visit)(T&data)=print)
　　
　　 　　{
　　 　　
　　 　　queue*>a;BTNode*p=root;//記得#include
　　 　　
　　 　　while(p)
　　 　　
　　 　　{
　　 　　
　　 　　visit(p->data);
　　 　　
　　 　　if(p->left)a.push(p->left);if(p->right)a.push(p->right);
　　 　　
　　 　　if(a.empty())break;p=a.front();a.pop();
　　 　　
　　 　　}
　　 　　
　　 　　}
　　 　　
　　 　　附注：缺省的visit函數print如下
　　 　　
　　 　　private:
　　 　　
　　 　　staticvoidprint(T&data){cout<　　
　　 　　5.不用棧的非遞歸中序遍歷
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　
　　 　　當有parent指針時，可以不用棧實現非遞歸的中序遍歷，書上提到了有這種方法，但沒給出例程。
　　 　　
　　 　　public:
　　 　　
　　 　　BTNode*next()
　　 　　
　　 　　{
　　 　　
　　 　　if(!current)returnNULL;
　　 　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　if(current->right){current=current->right;while(current->left)current=current->left;}
　　 　　
　　 　　else
　　 　　
　　 　　{
　　 　　
　　 　　BTNode*y=current->parent;
　　 　　
　　 　　while(y&¤t==y->right){current=y;y=y->parent;}
　　 　　
　　 　　current=y;
　　 　　
　　 　　}
　　 　　
　　 　　returncurrent;
　　
　　 　　
　　 　　}
　　 　　
　　 　　private:
　　 　　
　　 　　BTNode*current;
　　 　　
　　 　　上面的函數能使current指針向前移動一個位置，假如要遍歷整棵二叉樹，需要使current指向中序序列的第一個節點，例如下面的成員函數：
　　 　　
　　 　　public:
　　 　　
　　 　　voidfirst(){current=root;while(current->left)current=current->left;}
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或