首页 / 算法 / 非递归 前序/中序/后序 遍历二叉树
非递归 前序/中序/后序 遍历二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了非递归 前序/中序/后序 遍历二叉树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3144字,纯文字阅读大概需要5分钟。
内容图文
![非递归 前序/中序/后序 遍历二叉树](/upload/InfoBanner/zyjiaocheng/1025/177e5e76637148e5b3f126cbaa87a0e4.jpg)
非递归前序遍历二叉树
1 void preTraverse(const BiTree &T){ 2 //initialStack(stack) 3 BiTree stack[MAX]; 4 int top=-1; 5 BiTree p=T; 6 //while(!stackEmpty(stack)||p) 7 while(p||top>-1){ 8 while(p){ 9 //visit(p->data) 10 cout<<p->data<<" "; 11 //push(stack,p) 12 stack[++top]=p; 13 p=p->lChild; 14 } 15 //pop(stack,p) 16 p=stack[top--]; 17 p=p->rChild; 18 } 19 }
非递归中序遍历二叉树
1 void inTraverse(const BiTree &T){ 2 //initialStack(stack) 3 BiTree stack[MAX]; 4 int top=-1; 5 BiTree p=T; 6 //while(p||!stackEmpty(stack)) 7 while(p||top>-1){ 8 if(p){ 9 while(p){ 10 //push(stack,p) 11 stack[++top]=p; 12 p=p->lChild; 13 } 14 }else{ 15 //pop(stack,p) 16 p=stack[top--]; 17 //visit(p->data) 18 cout<<p->data<<" "; 19 p=p->rChild; 20 } 21 } 22 }
非递归后序遍历二叉树(leetcode145)
void postTraverse(const BiTree &T){ stack<BiTree>s; BiTree p=T,prev=NULL; while(p||!s.empty()){ while(p){ s.push(p); p=p->lChild; } p=s.top(); s.pop(); if(p->rChild==NULL||p->rChild==prev){ cout<<p->data<<" "; prev=p; p=NULL; }else{ s.push(p); p=p->rChild; } } }
完整实现(先用前序+中序构造二叉树)
#include<iostream> #include<stack> #define MAX 100 using namespace std; typedef struct BiTNode{ public: int data; struct BiTNode *lChild,*rChild; }BiTNode,*BiTree; void preTraverse(const BiTree &T){ //initialStack(stack) BiTree stack[MAX]; int top=-1; BiTree p=T; //while(!stackEmpty(stack)||p) while(p||top>-1){ while(p){ //visit(p->data) cout<<p->data<<" "; //push(stack,p) stack[++top]=p; p=p->lChild; } //pop(stack,p) p=stack[top--]; p=p->rChild; } } void inTraverse(const BiTree &T){ BiTree stack[MAX]; int top=-1; BiTree p=T; //while(p||!stackEmpty(stack)) while(p||top>-1){ if(p){ while(p){ //push(stack,p) stack[++top]=p; p=p->lChild; } }else{ //pop(stack,p) p=stack[top--]; //visit(p->data) cout<<p->data<<" "; p=p->rChild; } } } void postTraverse(const BiTree &T){ //initialStack(stack) stack<BiTree>s; BiTree p=T,prev=NULL; while(p||!s.empty()){ while(p){ s.push(p); p=p->lChild; } p=s.top(); s.pop(); if(p->rChild==NULL||p->rChild==prev){ cout<<p->data<<" "; prev=p; p=NULL; }else{ s.push(p); p=p->rChild; } } } bool preAndInCreate(BiTree &T,int pre[],int in[],int length){ if(length<=0){ T=NULL; }else{ int i; T=new BiTNode; T->data=pre[0]; for(i=0;i<length&&in[i]!=pre[0];++i); if(i>length) return false; preAndInCreate(T->lChild,pre+1,in,i); preAndInCreate(T->rChild,pre+i+1,in+i+1,length-1-i); } return true; } bool deleteTree(BiTree &T){ if(T){ BiTree L=T->lChild; BiTree R=T->rChild; delete T; T=NULL; deleteTree(L); deleteTree(R); } } int main(){ int n; cout<<"Input the number of nodes : "; cin>>n; cout<<"Input preorder tree : "; int pre[n],in[n]; for(int i=0;i<n;++i) cin>>pre[i]; cout<<"Input inorder tree : "; for(int i=0;i<n;++i) cin>>in[i]; BiTree T=NULL; preAndInCreate(T,pre,in,n); cout<<"\nthe tree in preorder : "; preTraverse(T); cout<<"\nthe tree in inorder : "; inTraverse(T); cout<<"\nthe tree in postorder : "; postTraverse(T); deleteTree(T); }
内容总结
以上是互联网集市为您收集整理的非递归 前序/中序/后序 遍历二叉树全部内容,希望文章能够帮你解决非递归 前序/中序/后序 遍历二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。