【實(shí)現(xiàn)二叉樹的 3 種遍歷算法】

問題描述：該算法的設(shè)計(jì)，要求運(yùn)行結(jié)果如下所示：

二叉樹 bt:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

***層次遍歷序列:A B C D E F G H I J K L M N

先序遍歷序列:

遞歸算法:A B D E H J K L M N C F G I

非遞歸算法:A B D E H J K L M N C F G I

中序遍歷序列:

遞歸算法:D B J H L K M N E A F C G I

非遞歸算法:D B J H L K M N E A F C G I

后序遍歷序列:

遞歸算法:D J L N M K H E B F I G C A

***非遞歸算法:D J L N M K H E B F I G C A
二叉樹的遍歷，是二叉樹最基本的也是最重要的。有三種遍歷方式，先序，中序和后序。
同樣，各種遍歷方式分為遞歸和非遞歸的兩種。而層次遍歷則是一遍bfs就可以了。最基礎(chǔ)的bfs。非遞歸遍歷的時(shí)候，我們需要結(jié)合棧的數(shù)據(jù)結(jié)構(gòu)，先進(jìn)后出。主要看代碼：

#include<bits/stdc++.h> #define telemtype char using namespace std;typedef struct node{telemtype data;struct node *lchild,*rchild;int vis; } *Bitree; void creatree(Bitree &tt) {char c;cin>>c;if(c=='#') tt=NULL;else{tt=(node *)malloc(sizeof(node));tt->data=c;tt->vis=0;creatree(tt->lchild);creatree(tt->rchild);} }void bfs(Bitree &t)//層次遍歷 {queue<Bitree>p;p.push(t);while(!p.empty()){Bitree q;q=p.front();p.pop();printf("%c ",q->data);if(q->lchild) p.push(q->lchild);if(q->rchild) p.push(q->rchild);} }void xprinttree(Bitree &t)//先序遍歷遞歸算法 {if(t){printf("%c ",t->data);xprinttree(t->lchild);xprinttree(t->rchild);} }void zprinttree(Bitree &t)//中序遍歷遞歸算法 {if(t){zprinttree(t->lchild);printf("%c ",t->data);zprinttree(t->rchild);} }void hprinttree(Bitree &t)//后序遍歷遞歸算法 {if(t){hprinttree(t->lchild);hprinttree(t->rchild);printf("%c ",t->data);} }void InOrderTraversal_NoRecursion(node *T)//中序遍歷非遞歸算法 {node *Stack[1010];int top = -1;while(T || (top != -1)) {while(T) {Stack[++top] = T;T = T->lchild;} if(top != -1) {T = Stack[top--];printf("%c ", T->data);T = T->rchild;}} }void outOrderTraversal_NoRecursion(node *T)//先序遍歷非遞歸算法 {node *Stack[1010];int top=-1;while(T||(top!=-1)){while(T){cout<<T->data<<" ";Stack[++top]=T;T=T->lchild;}if(top!=-1){T=Stack[top--];T=T->rchild;}} }void laterOrderTraversal_NoRecursion(node *T)//后序遍歷非遞歸算法 {node *Stack[1010];int top=-1;while(T||(top!=-1)){while(T){Stack[++top]=T;T=T->lchild;}if(top!=-1){T=Stack[top--];if(T->vis==0){T->vis=1;Stack[++top]=T;T=T->rchild;}else{cout<<T->data<<" ";T=NULL; //如果加這一句，會(huì)無限循環(huán)跳不出去。}}} }int main() {Bitree t;creatree(t);cout<<"二叉樹創(chuàng)建完成。"<<endl;cout<<"先序遍歷二叉樹(遞歸算法)："<<endl;xprinttree(t);cout<<"\n中序遍歷二叉樹(遞歸算法)："<<endl;zprinttree(t);cout<<"\n后序遍歷二叉樹(遞歸算法)："<<endl;hprinttree(t);cout<<"\n層次遍歷二叉樹(廣搜bfs)："<<endl;bfs(t);cout<<"\n先序遍歷二叉樹(非遞歸算法): "<<endl;outOrderTraversal_NoRecursion(t);cout<<"\n中序遍歷二叉樹(非遞歸算法): "<<endl;InOrderTraversal_NoRecursion(t);cout<<"\n后序遍歷二叉樹(非遞歸算法): "<<endl;laterOrderTraversal_NoRecursion(t); }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的二叉树的操作2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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