C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):二叉樹(1)

2019-11-17 05:04:11

字體：大中小

供稿：網(wǎng)友

　　這些天參與了CSDN論壇的討論，改變了我以前的一些看法。回頭看我以前的東西，我雖對(duì)這本書很不滿，但我還是按照它的安排在一點(diǎn)點(diǎn)的寫；這樣就導(dǎo)致了，我過多的在意書中的偏漏，我寫的更多是說“這本書怎樣”，而偏離了我寫這些的初衷——給正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人一些幫助。

正像我在前面所說的，雖然現(xiàn)有的教科書都不是很合理，但假如僅僅是抱怨這點(diǎn)，那無異于潑婦罵街。雖然本人的水平連初級(jí)都?jí)虿簧希辽傧葟奈易鲆稽c(diǎn)嘗試，以后這門課的教授方法必將一點(diǎn)點(diǎn)趨于合理。

　　因此，后面不在按照書上的次序，將本著“實(shí)際應(yīng)用（算法）決定數(shù)據(jù)結(jié)構(gòu)”的思想來講解，常見教科書上有的，基本不再重點(diǎn)敘述（除了重點(diǎn)，例如AVL樹的平衡旋轉(zhuǎn)），——因此，在看本文的同時(shí)，一定要有一本教科書。這只是一個(gè)嘗試，希望大家多提寶貴意見。

　　樹
　　因?yàn)楝F(xiàn)實(shí)世界中存在這“樹”這種結(jié)構(gòu)——族譜、等級(jí)制度、目錄分類等等，而為了研究這類問題，必須能夠?qū)鋬?chǔ)存，而如何儲(chǔ)存將取決于所需要的操作。這里有個(gè)問題，是否答應(yīng)存在空樹。有些書認(rèn)為樹都是非空的，因?yàn)闃浔硎镜氖且环N現(xiàn)實(shí)結(jié)構(gòu)，而0不是自然數(shù)；我用過的教科書都是說可以有空樹，當(dāng)然是為了和二叉樹統(tǒng)一。這個(gè)沒有什么原則上的差別，反正就是一種習(xí)慣。

　　二叉樹
　　二叉樹可以說是人們假想的一個(gè)模型，因此，答應(yīng)有空的二叉樹是無爭(zhēng)議的。二叉樹是有序的，左邊有一個(gè)孩子和右邊有一個(gè)的二叉樹是不同的兩棵樹。做這個(gè)規(guī)定，是因?yàn)槿藗冑x予了左孩子和右孩子不同的意義，在二叉樹的各種應(yīng)用中，你將會(huì)清楚的看到。下面只講解鏈?zhǔn)浇Y(jié)構(gòu)。看各種講數(shù)據(jù)結(jié)構(gòu)的書，你會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象：在二叉樹這里，基本操作有計(jì)算樹高、各種遍歷，就是沒有插入、刪除——那樹是怎么建立起來的？其實(shí)這很好理解，對(duì)于非線性的樹結(jié)構(gòu)，插入刪除操作不在一定的法則規(guī)定下，是毫無意義的。因此，只有在具體的應(yīng)用中，才會(huì)有插入刪除操作。

更多內(nèi)容請(qǐng)看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或　　節(jié)點(diǎn)結(jié)構(gòu)
　　數(shù)據(jù)域、左指針、右指針肯定是必須的。除非很少用到節(jié)點(diǎn)的雙親，或者是資源緊張，建議附加一個(gè)雙親指針，這將會(huì)給很多算法帶來方便，尤其是在這個(gè)“空間換時(shí)間”的時(shí)代。

　　template

　　strUCtBTNode

　　{

　　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種遍歷方法，先、中、后根，逐層。當(dāng)初我對(duì)這個(gè)很迷惑，搞這么多干什么？到了后面才明白，這是不同的應(yīng)用需要的。例如，判定兩個(gè)二叉樹是否相等，只要子樹根節(jié)點(diǎn)不同，那么就不等，顯然這時(shí)要用先序遍歷；而刪除二叉樹，必須先刪除左右子樹，然后才能刪除根節(jié)點(diǎn)，這時(shí)就要用后序遍歷。

　　
　　實(shí)際上，搞這么多遍歷方法，根本原因是在內(nèi)存中儲(chǔ)存的樹是非線性結(jié)構(gòu)。對(duì)于用數(shù)組儲(chǔ)存的二叉樹，這些名目繁多的方法都是沒有必要的。利用C++的封裝和重載特性，這些遍歷方法能很清楚的表達(dá)。

更多內(nèi)容請(qǐng)看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或　　1.前序遍歷

　　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);}
　　
　　}
　　
　　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函數(shù)print如下
　　
　　private:
　　
　　staticvoidprint(T&data){cout<　　
　　5.不用棧的非遞歸中序遍歷

更多內(nèi)容請(qǐng)看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或　　
　　當(dāng)有parent指針時(shí)，可以不用棧實(shí)現(xiàn)非遞歸的中序遍歷，書上提到了有這種方法，但沒給出例程。
　　
　　public:
　　
　　BTNode*next()
　　
　　{
　　
　　if(!current)returnNULL;
　　

　　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;
　　
　　上面的函數(shù)能使current指針向前移動(dòng)一個(gè)位置，假如要遍歷整棵二叉樹，需要使current指向中序序列的第一個(gè)節(jié)點(diǎn)，例如下面的成員函數(shù)：
　　
　　public:
　　
　　voidfirst(){current=root;while(current->left)current=current->left;}

更多內(nèi)容請(qǐng)看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

上一篇：C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):遞歸(3.1)

下一篇：C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):二叉樹(2)