最近自己学习数据结构这本书，看到 二叉树的前序，中序，后序 那部分，很是不明白。 请教大家，前序输出里面的两个递归函数，是如何完成目的的？  

//功能：中序遍历非递归算法
//时间：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();
}
 

 
发表评论 共 0篇评论，第 1页/共 0页
第一页 上一页 下一页 最后页

共 0篇评论，第 1页/共 0页
第一页 上一页 下一页 最后页上一篇|下一篇|返回
发表评论
日志新版升级特性介绍  使用签名档    请选择道具  请选择道具 隐身草 彩虹炫 天使之爱
 
温馨提示：点击验证码输入框，以获取验证码
请输入验证码：     提交  取消