偽代碼闡述

先序遍歷

先序遍歷:先訪問根節(jié)點, 然后深入左子樹,直到不能深入時再深入右子樹
由定義可得遞歸式

void travPre_R(BinNodePosi* x,VISIT& visit){if(!X) return; //到達葉子節(jié)點,開始回歸visit(x->data);//向左子樹深入的過程中便開始進行對每個節(jié)點的數(shù)據(jù)進行訪問travPre_R(x->lChild,visit);//深入右子樹travPre_R(x->rChild,visit);//深入右子樹 }

例:

其遍歷順序為: 0-1-3-7-8-4-9-10-2-5-11-12-6-13-14
就上述順序表明遍歷過程總是從根到左,再到右
由消除尾遞歸的方式可得其迭代式

void travPre_I1(BinNodePosi* x,VISIT& visit){stack<BinNodePosi>s; //借助輔助棧記錄根節(jié)點的左右孩子,以便于回溯if(x) s.push(x);while(!s.empty()){visit(s.top()->data);//訪問當前節(jié)點s.pop();//刪除棧頂if(x->lChild) s.push(x->rchild);//由于棧的結構,所以讓rChild先進,lChild后進即可做到先訪問lChild,后rChildif(x->rChild) s.push(x->lChild);}//整個while操作就可以實現(xiàn)向左子樹深入的過程,直到?jīng)]有左子樹 }

通過消除尾遞歸的方式所得到的迭代式不具有普遍性(無法推廣到中序,后序,這二者非尾遞歸),就此通過以下迭代式做闡述

void travPre_I2(BinNodePosi* x,VISIT& visit){stack<BinNodePosi>s;while(x){//visit(x->data);while(x->lChild){s.push(x->rChild);//有右孩子存入棧中,以便回溯訪問x=x->lchild;//迭代向左子樹進行深入}x=s.top();s.pop();}//看似O(n^2),但復雜度低于遞歸版 }

中序遍歷

中序遍歷:先查看最左端的葉子節(jié)點,然后根節(jié)點,最后右子樹
得遞歸式:

void traveIn_R(BinNodePosi* x,VISIT& visit){if(!x) return;traveIn_R(x->lChild,visit);//先向左深入直到最左的葉子節(jié)點visit(x->data);traveIn_R(x->lChild,visit); }

上圖的中序遍歷順序:7-3-8-1-9-4-10-0-11-5-12-2-13-6-14
根據(jù)先序遍歷的迭代可推廣到中序遍歷

void traveIn_I(BinNodePosi* x,VISIT& visit){stack<BinNodePosi>s;while(!s.empty()){while(x){s.push(x);x=x->lChild;//向左子樹不斷深入}x=s.top();visit(x->data);x=x->rChild;s.pop();} }

上述過程描述如下:
先將所有最左邊的左子樹存入棧中,直到到達最左端的葉子節(jié)點(如上圖的7號位置),當進行完visit操作后,節(jié)點轉(zhuǎn)向7號的右子樹,沒有右子樹的情況下將彈出棧內(nèi)元素,開始回溯,向上回溯至當前節(jié)點具有右子樹時,將該右子樹下的所有左子樹入棧,重復上述操作,直到所有節(jié)點都遍歷.
遍歷過程中無右子樹的節(jié)點需要做回溯處理

后序遍歷

后序遍歷: 先依次遍歷完左子樹,右子樹后才訪問根節(jié)點
得如下遞歸定義式:

void travePost_R(BinNodePosi* x,VISIT& visit){if(!x) return;travePost_R(x->lChild,visit);travePost_R(x->rChild,visit);visit(x->data); }

上述圖片中的遍歷順序:7-8-3-9-10-4-1-11-12-5-13-14-6-2-0
迭代式如下:

void travePast_I(BinNodePosi* x,VISIT& visit){stack<BinNodePosi>s;if(x)s.push(x);while(!s.empty()){if(s.top()!=x->parent){//s.top()!=x->parent主要用于判斷兩節(jié)點是否屬于兄弟節(jié)點,例如上圖的3,4;使得可以轉(zhuǎn)向4號,將4號下的最左邊的左子樹及部分右子樹進行入棧處理while(x){if(x->rChild) s.push(x->rChild);if(x->lChild) s.push(x->lChild);x=x->lChild;//將最左邊的左子樹,及部分右子樹依次存入棧中}}x=s.top();visit(x->data);s.pop();} }

層次遍歷

層次遍歷:將二叉樹看做金字塔形狀,層次遍歷做到的就是對每一層中左子樹,右子樹進行遍歷處理,遍歷順序總是"先上后下,先左后右", 該遍歷方式在廣度優(yōu)先遍歷中也有所應用
由于層次遍歷具有順序性,而非后進先出原則,所以采用queue處理
上圖中的遍歷順序:0-1-2-3-4-5-6-7-8-9-10-11-12-13-14
迭代式如下:

void traveLevel_R(BinNodePosi* x,VISIT& visit){queue<BinNodePosi>q;if(x) q.push(x);while(!q.empty()){x=queue.front();visit(x->data);if(x->lChild) q.push(x->lChild);if(x->rChild) q.push(x->rChild);} }

每當一個節(jié)點入隊時,便讓該節(jié)點的左右子樹入隊,由于隊列的先進先出的性質(zhì),就能使每一層都能依次遍歷

來一點小插曲

完全二叉樹
在層次遍歷中,每一次迭代中都必定有一個節(jié)點出隊,如果在前n/2次迭代中都有左孩子入隊, 且前n/2-1次迭代中都有右孩子入隊,那么這棵樹就是完全二叉樹
拓撲結構特征: 葉子節(jié)點只能出現(xiàn)在最底部的兩層,且最底層的葉子節(jié)點必須位于次葉子節(jié)點的左側(cè)
高度h的完全二叉樹, 規(guī)模介于2^h~2(h+1)-1之間

滿二叉樹
所有葉子節(jié)點都位于最底層, 高度為h的滿二叉樹由2^(h+1)-1個節(jié)點組成

完整詳細設計(遞歸的設計方式很簡單將不再闡述)

數(shù)據(jù)結構定義如下:

二叉樹本身主要由結構體完成, 該結構體包含每個節(jié)點存儲的節(jié)點數(shù)據(jù)value, 以及兩個左右指針 lchild 和 rchild和一個父指針 parent , 這兩個指針主要用來指向二叉樹的左右子樹, 通過左右指針, 就能很好的完成二叉樹的遍歷, 使用父指針也能很好完成節(jié)點的記錄, 由于采用的非遞歸的方式遍歷樹結構, 所以需要使用到輔助數(shù)組, 通過數(shù)組, 和循環(huán)模擬遞歸遍歷的過程。

功能詳細設計:

• 二叉樹結構：每一個二叉樹節(jié)點包含數(shù)據(jù)域以及3個指針(分別指向左子樹，右子樹，父節(jié)點)。
• 創(chuàng)建二叉樹: 采用前序遍歷的方式創(chuàng)建一棵完整的二叉樹, 便于后面的遍歷方式的測試，我使用"#"字符代表空。
• 非遞歸的前序遍歷: 前序遍歷的方式是先查看當前節(jié)點內(nèi)容然后再查看左子樹, 最后查看右子樹。所以在非遞歸遍歷中, 就模擬這種遍歷方式, 首先存入根節(jié)點, 使用循環(huán), 每次將數(shù)組最后位置的節(jié)點取出, 進行訪問, 將訪問過的節(jié)點的右子樹存入數(shù)組中, 然后存左子樹, 循環(huán)終止條件是數(shù)組為空, 模擬這種情況, 就能每次做到先訪問根, 然后訪問左子樹, 最后訪問右子樹
• 非遞歸中序遍歷: 中序遍歷是先訪問左子樹, 再訪問根節(jié)點, 最后訪問右子樹, 同樣的采用數(shù)組模擬這種遍歷方式。首先將當前節(jié)點的所有依次左子樹存入數(shù)組中(直到?jīng)]有左子樹)，然后取出數(shù)組中最后一個位置的節(jié)點進行訪問，此時再轉(zhuǎn)向右子樹(無論右子樹是否存在，這里需要利用右子樹等于空的條件進行判斷下一次循環(huán)是否要再將左子樹存入數(shù)組中)，執(zhí)行完上述操作后，再重復執(zhí)行，直到所有節(jié)點都訪問完。
• 非遞歸后序遍歷：后序遍歷是先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點，非遞歸實現(xiàn)：將當前節(jié)點的所有左子樹依次存入數(shù)組中(同時將該節(jié)點的右子樹存入數(shù)組中，便于待會模擬回溯)，左右子樹存儲的條件是：左右節(jié)點都訪問過才能訪問父節(jié)點，當棧頂元素與當前元素的父節(jié)點是同一個，則說明當前節(jié)點存在兄弟節(jié)點還沒被訪問1.整個過程盡量往左子樹方向走，如果該節(jié)點沒有左子樹，就往右子樹方向走一次，然后重復步驟1，直到節(jié)點左右子樹都不存在，此時輸出該節(jié)點存儲的數(shù)據(jù)

函數(shù)關系調(diào)用圖如下:

寫代碼容易出現(xiàn)的問題:

正確理解遞歸遍歷的方式, 防止理解錯誤導致, 不能用棧結構模擬出遍歷的過程, 在非遞歸后序遍歷，沒用弄清楚循環(huán)判斷和條件判斷，導致在遍歷過程中出現(xiàn)錯誤，最后采用得到方式就是判斷棧頂元素與當前節(jié)點的父節(jié)點是否是同一個，通過這樣的方式判斷是否輸出該節(jié)點的父節(jié)點內(nèi)容。

樹結構體:

struct BitNode{BitNode(char c,BitNode *p):data(c),parent(p){}Type data;BitNode *parent=NULL,*lchild=NULL,*rchild=NULL; };

非遞歸先序遍歷:

void nrperOrder(BitNode *bt){//非遞歸先序遍歷int top=-1;BitNode *stack[size],*p;if(bt!=NULL)stack[++top]=bt;else return;while(top>-1){p=stack[top--];cout<<p->data;//有右存右，有左存左，先存右再存左 if(p->rchild!=NULL)stack[++top]=p->rchild;if(p->lchild!=NULL)stack[++top]=p->lchild;} }

非遞歸中序遍歷:

void nrinOrder(BitNode *bt){//非遞歸中序遍歷int top=-1;BitNode *stack[size],*p=bt;while(p||top>-1){if(p){stack[++top]=p;p=p->lchild;}else{p=stack[top--];cout<<p->data;p=p->rchild;}} }

非遞歸后序遍歷:

void nrpastOrder(BitNode *bt){//非遞歸后序遍歷int top=-1,tag[size];BitNode *stack[size],*p=bt;stack[++top]=bt; while(top>-1){//左右節(jié)點都訪問過才能訪問parent//當棧頂元素與當前元素p的parent是一個，則說明p存在兄弟節(jié)點還沒被訪問 if(stack[top]!=p->parent){p=stack[top];while(p){if(p->rchild)stack[++top]=p->rchild;if(p->lchild)stack[++top]=p->lchild;if(p->lchild)p=p->lchild;//盡量往左偏移 else if(p->rchild)p=p->rchild;//做不下去,往右走 else p=NULL;//左右都走不下去,p置空 }}p=stack[top--];cout<<p->data;} }

求根節(jié)點到指定節(jié)點的路徑:

void path(BitNode *bt,char c,BitNode *parent){//方法1.先序遍歷,找到目標節(jié)點,不斷返回父節(jié)點(即當前節(jié)點到根節(jié)點路徑),中后序遍歷一致 //方法2.迭代式查找,找到當前節(jié)點然后迭代輸出parent int top=-1;BitNode *stack[size],*p;if(bt!=NULL)stack[++top]=bt;else return;while(top>-1){p=stack[top--];if(p->data==c){while(p){cout<<p->data;p=p->parent;}return;}if(p->rchild!=NULL)stack[++top]=p->rchild;if(p->lchild!=NULL)stack[++top]=p->lchild;} }

完整函數(shù)調(diào)用代碼如下:

#include<iostream> #define Type char #define size 20 using namespace std; struct BitNode{BitNode(char c,BitNode *p):data(c),parent(p){}Type data;BitNode *parent=NULL,*lchild=NULL,*rchild=NULL; }; void createBtree(BitNode* &bt,BitNode* parent){//創(chuàng)建二叉樹char c;if((cin>>c)&&(c!='#')&&(c!='\n')){bt=new BitNode(c,parent);parent=bt;createBtree(bt->lchild,parent);createBtree(bt->rchild,parent);} } void nrperOrder(BitNode *bt){//非遞歸先序遍歷int top=-1;BitNode *stack[size],*p;if(bt!=NULL)stack[++top]=bt;else return;while(top>-1){p=stack[top--];cout<<p->data;//有右存右，有左存左，先存右再存左 if(p->rchild!=NULL)stack[++top]=p->rchild;if(p->lchild!=NULL)stack[++top]=p->lchild;} } void nrinOrder(BitNode *bt){//非遞歸中序遍歷int top=-1;BitNode *stack[size],*p=bt;while(p||top>-1){if(p){stack[++top]=p;p=p->lchild;}else{p=stack[top--];cout<<p->data;p=p->rchild;}} } void nrpastOrder(BitNode *bt){//非遞歸后序遍歷int top=-1,tag[size];BitNode *stack[size],*p=bt;stack[++top]=bt; while(top>-1){//左右節(jié)點都訪問過才能訪問parent//當棧頂元素與當前元素p的parent是一個，則說明p存在兄弟節(jié)點還沒被訪問 if(stack[top]!=p->parent){p=stack[top];while(p){if(p->rchild)stack[++top]=p->rchild;if(p->lchild)stack[++top]=p->lchild;if(p->lchild)p=p->lchild;//盡量往左偏移 else if(p->rchild)p=p->rchild;//做不下去,往右走 else p=NULL;//左右都走不下去,p置空 }}p=stack[top--];cout<<p->data;} }void path(BitNode *bt,char c,BitNode *parent){//方法1.先序遍歷,找到目標節(jié)點,不斷返回父節(jié)點(即當前節(jié)點到根節(jié)點路徑),中后序遍歷一致 //方法2.迭代式查找,找到當前節(jié)點然后迭代輸出parent int top=-1;BitNode *stack[size],*p;if(bt!=NULL)stack[++top]=bt;else return;while(top>-1){p=stack[top--];if(p->data==c){while(p){cout<<p->data;p=p->parent;}return;}if(p->rchild!=NULL)stack[++top]=p->rchild;if(p->lchild!=NULL)stack[++top]=p->lchild;} }void removeBtree(BitNode *bt){if(bt){removeBtree(bt->lchild);removeBtree(bt->rchild);delete bt;} } int main(){//ABD#GJ#K###EH###C#F#I##BitNode *bt;char c;int count=0; cout<<"創(chuàng)建二叉樹:";createBtree(bt,NULL);cout<<"非遞歸前序遍歷:";nrperOrder(bt);cout<<endl; cout<<"非遞歸中序遍歷";nrinOrder(bt);cout<<endl;cout<<"非遞歸后序遍歷:";nrpastOrder(bt);cout<<endl;cout<<"樹高:"<<btreeHeight(bt);cout<<endl;cout<<"路徑,輸入查找字符:";cin>>c; path(bt,c,NULL);cout<<endl;removeBtree(bt);//刪除二叉樹return 0; }

總結

以上是生活随笔為你收集整理的二叉树先序遍历,中序遍历,后序遍历,层次遍历学习总结及完整C/C++代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。