[个人日记]
设置置顶
转载到我空间
复制本文网址 隐藏签名档 大字体选用该信纸 上一篇|下一篇|编辑|删除|返回
C++
发表时间:2007年11月28日 22时47分53秒
本文链接:[url]http://user.qzone.[/url]评论/阅读(0/4)
C++
//功能:中序遍历非递归算法
//时间:2006.11.3
//作者:lwh
//二叉树四种遍历方法:前序、中序、后序、层次
#include<fstream>
using namespace std;
typedef char TElemType;
ifstream in("input.txt");
ofstream out("output.txt");
//二叉树的二叉链表存储表示
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
//功能:由先序次序序列创建二叉树
//参数:引用指针
//说明:可应付空树 参见bitree.cpp中的同名函数
//结论:建立链式二叉树最好的方法
void CreateBiTree(BiTree &t)//按先序次序输入二叉树中结点的值,"#"表示空子树,"@"表示输入结束标志!
{
//t为指针引用传递
char ch;
ch=in.get(); //读取先序次序二叉树中的结点值
if(ch=='@')return;//结尾
if(ch=='#') t=NULL;//空子树
else{
t=new BiTNode;
t->data=ch;t->lchild=NULL;t->rchild=NULL;
CreateBiTree(t->lchild);
CreateBiTree(t->rchild);
}
}//CreateBiTree
void PreOrderTraverse(BiTree t)
{
if(t) {
out<<t->data;
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
}
void InOrderTraverse(BiTree t)
{
if(t) {
InOrderTraverse(t->lchild);
out<<t->data;
InOrderTraverse(t->rchild);
}
}
void PostOrderTraverse(BiTree t)
{
if(t) {
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
out<<t->data;
}
}
void LevelTraverse(BiTree t)
{
BiTNode Qu[100];
int front=-1,rear=-1;
if(t) Qu[++rear]=*t;
while(front!=rear)
{
out<<Qu[++front].data;
if(Qu[front].lchild)
Qu[++rear]=*Qu[front].lchild;
if(Qu[front].rchild)
Qu[++rear]=*Qu[front].rchild;
}
}
void InorderStackTraverse(BiTree t)//中序非递归算法
{
BiTree p,stack[100];//假设的最大栈空间数
int top=-1;
p=t;
while((p!=NULL)||top!=-1)
{
while(p!=NULL)
{ top++;stack[top]=p;p=p->lchild;}
if(top!=-1)
{ p=stack[top];top--;out<<p->data<<' ';p=p->rchild;}
}
}
void main()
{
BiTree tt=NULL;
CreateBiTree(tt);
PreOrderTraverse(tt);
out<<endl;
InOrderTraverse(tt);
out<<endl;
PostOrderTraverse(tt);
out<<endl;
LevelTraverse(tt);
out<<endl;
InorderStackTraverse(tt);
out<<endl;
in.close();
out.close();
}