二叉树中序遍历的非递归实现_huifeng00的空间_百度空间

今天在百度知道,回答别人的问题,写的。

特此记录

#include<iostream>
using namespace std;
class tree
{
public:
tree(){lchild=NULL;rchild=NULL;}
char data;
class tree *lchild;
class tree *rchild;
};
void build(tree *&t)//先序建树
{
char c;
cin>>c;
if(c=='#')
{
t=NULL;
}
else
{
t=new tree;
t->data=c;
build(t->lchild);
build(t->rchild);
}
}

void preorder(tree *root)//这是递归实现
{
if (root!=NULL)
{
preorder(root->lchild);
cout<<root->data;
preorder(root->rchild);
}

}
class stack
{
public:
tree *top,*base;
};
void init (stack *s)//初始化栈
{
s->base=new tree[100];
s->top=s->base;
}
void push(stack *s,tree *t)//入栈
{
*(s->top++)=*t;
}
void pop(stack *s,tree &t)//取栈顶元素
{
t=*(--(s->top));
}
void inorder(tree *t)//这是非递归实现
{
stack *s=new stack;
tree *p;
init(s);
p=t;
tree temp=*t;
while(p||s->top!=s->base)
{
while(p)
{
   push(s,p);
   p=p->lchild;
}
if(s->top!=s->base)
{
   pop(s,temp);
   cout<<temp.data;
   p=temp.rchild;
}
}
}
int main()
{
tree *t;
build(t);
preorder(t);
cout<<"非递归中序遍历"<<endl;
inorder(t);
cout<<endl;
return 0;
}

如下输入

234##5#6##7##回车
就可以看到结果。

树的图形对应为



郑重声明:资讯 【二叉树中序遍历的非递归实现_huifeng00的空间_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——