#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
using namespace std;
char in[30],pre[30],last[30];
typedef struct mynode
{
char data;
struct mynode* leftchild;
struct mynode* rightchild;
} Node,*pNode;
void build(char *pre,char *in,int len,pNode &root)
{
if(len<1)
return;
int i=0;
while(pre[0]!=in[i])i++;
root = (pNode)malloc(sizeof(Node));
root->data = pre[0];
root->rightchild = root->leftchild = NULL;
build(pre+1,in,i,root->leftchild);
build(pre+i+1,in+i+1,len-i-1,root->rightchild);
}
//层序遍历
void seqorder(pNode root)
{
pNode temp;
queue<pNode> qe1;
queue<pNode> qe2;
qe1.push(root);
while(!qe1.empty())
{
temp = qe1.front();
qe1.pop();
printf("%c",temp->data);
if(temp->leftchild)
qe2.push(temp->leftchild);
if(temp->rightchild)
qe2.push(temp->rightchild);
if(qe1.empty() && !qe2.empty()){
swap(qe1,qe2);
printf("\n");
}
}
}
//中序遍历
void inorder(pNode root)
{
if(NULL==root) return;
inorder(root->leftchild);
printf("%c",root->data);
inorder(root->rightchild);
}
//前序遍历
void preorder(pNode root)
{
if(NULL==root) return;
printf("%c",root->data);
preorder(root->leftchild);
preorder(root->rightchild);
}
//后续遍历
void lastorder(pNode root)
{
if(NULL==root)return;
lastorder(root->leftchild);
lastorder(root->rightchild);
printf("%c",root->data);
}
//前序非递归
void _preorder(pNode root)
{
stack<pNode> stk;
while(!stk.empty()||root!=NULL)
{
while(root)
{
stk.push(root);
printf("%c",root->data);
root = root->leftchild;
}
root = stk.top();
root = root->rightchild;
stk.pop();
}
}
//中序遍历非递归
void _inorder(pNode root)
{
stack<pNode> stk;
while(root||!stk.empty())
{
while(root)
{
stk.push(root);
root = root->leftchild;
}
root = stk.top();
stk.pop();
printf("%c",root->data);
root = root->rightchild;
}
}
//后续遍历非递归
void _lastorder(pNode root)
{
stack<pNode> stk1;
stack<pNode> stk2;
stk1.push(root);
while(!stk1.empty())
{
root = stk1.top();
stk1.pop();
stk2.push(root);
if(root->leftchild){
stk1.push(root->leftchild);
}
if(root->rightchild){
stk1.push(root->rightchild);
}
}
while(!stk2.empty()){
printf("%d",stk2.top()->data);
stk2.pop();
}
}
int main(void)
{
scanf("%s %s",pre,in);
pNode root;
build(pre,in,strlen(pre),root);
//lastorder(root);
_lastorder(root);
return 0;
}
二叉树先序,中序,后序遍历非递归实现
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 递归 比较简单,直接看代码即可. 非递归 先序遍历 申请一个栈,记为s1,将头结点压栈. 每次从栈顶弹出节点nod...
- 注:本文来自 左程云的书《程序员代码面试指南》 题目:分别用递归和非递归方法,实现二叉树的先序遍历(根左右)、中序...
- 二叉树的遍历口诀 前序:根左右 中序:左根右 后序:左右根 递归解法: 前序遍历: 中序遍历: 后序遍历: 递归解...