遍歷二叉樹詳解及代碼

《遍歷二叉樹詳解及代碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、這些天參與了CSDN論壇的討論，改變了我以前的一些看法。回頭看我以前的東西，我雖對(duì)這本書很不滿，但我還是按照它的安排在一點(diǎn)點(diǎn)的寫；這樣就導(dǎo)致了，我過多的在意書中的偏漏，我寫的更多是說“這本書怎樣”，而偏離了我寫這些的初衷——給正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人一些幫助。正像我在前面所說的，雖然現(xiàn)有的教科書都不是很合理，但如果僅僅是抱怨這點(diǎn)，那無異于潑婦罵街。雖然本人的水平連初級(jí)都?jí)虿簧?，但至少先從我做一點(diǎn)嘗試，以后這門課的教授方法必將一點(diǎn)點(diǎn)趨于合理。因此，后

2、面不在按照書上的次序，將本著“實(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è)問題，是否允許存在空樹。有些書認(rèn)為樹都是非空的，因?yàn)闃浔硎镜氖且环N現(xiàn)實(shí)結(jié)構(gòu)，而0不是自然數(shù)；我用過的教科書都是說可以有空樹，當(dāng)然是為了和二叉樹統(tǒng)一。這個(gè)沒有什么原則上的差別，反正就是一種習(xí)慣。二叉樹二叉樹可以

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

4、建議附加一個(gè)雙親指針，這將會(huì)給很多算法帶來方便，尤其是在這個(gè)“空間換時(shí)間”的時(shí)代。templatestructBTNode{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;};基本的二叉樹類templateclassBTree{public:BTree(BTNode

5、*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)不同，那么就不

6、等，顯然這時(shí)要用先序遍歷；而刪除二叉樹，必須先刪除左右子樹，然后才能刪除根節(jié)點(diǎn)，這時(shí)就要用后序遍歷。實(shí)際上，搞這么多遍歷方法，根本原因是在內(nèi)存中儲(chǔ)存的樹是非線性結(jié)構(gòu)。對(duì)于用數(shù)組儲(chǔ)存的二叉樹，這些名目繁多的方法都是沒有必要的。利用C++的封裝和重載特性，這些遍歷方法能很清晰的表達(dá)。1.????????前序遍歷public:voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}private:voidPreOrder(BTNode*p,void(*visit)(T&data)){if(p){visit(p-

7、>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);InOr