binarytreesearch.txt

包含中序遍历二叉树的递归和非递归算法的源代码

//中序遍历二叉树的递归和非递归算法
//递归算法
#include<stdio.h>
#include<iostream.h>
struct btnode
{
  char data;
  btnode *lchild;
  btnode *rchild;
};
btnode * createbtree()  //建立二叉树
{
   char ch;
   ch=getchar();
   btnode  *root;
   if(ch=='*')
        root=NULL;
   else
      {
        root=new  btnode;
        root->data=ch ;
        root->lchild=createbtree() ;//建立左子树
        root->rchild=createbtree() ;//建立右子树
      }
    return (root);
}
void inorder(btnode * root)  //中序遍历二叉树的递归算法
{
   if(root==NULL)
     return;        //递归结束的条件
   else
     {
        inorder(root->lchild);   //中序遍历左子树 
        cout<<root->data<<"    ";  //访问根结点
        inorder(root->rchild);   //中序遍历右子树
     }
}
void main()
{
  btnode *p1;
  cout<<"输入二叉树:"<<endl;
  p1= createbtree();  //建立二叉树
  cout<<"中序遍历二叉树的递归序列:"<<endl;
  inorder(p1);
}
//非递归算法
#include<stdio.h>
#include<iostream.h>
#define maxsize 100
struct btnode
{
  char data;
  btnode *lchild;
  btnode *rchild;
};
btnode * createbtree()  //建立二叉树
{
   char ch;
   ch=getchar();
   btnode  *root;
   if(ch=='*')
        root=NULL;
   else
      {
        root=new  btnode;
        root->data=ch ;
        root->lchild=createbtree() ; //建立左子树
        root->rchild=createbtree() ;  //建立右子树
      }
    return (root);
}
void nrinorder( btnode *root)  // 中序遍历二叉树的非递归算法
{
    btnode * stack[maxsize],*p;   //定义局部变量并初始化
    int top=0;
    p=root;
    do
     {
       while(p!=NULL)                 //一直深入到最左下结点
         {
           stack[++top]=p;          //所遇结点进栈
           p=p->lchild;           //继续探索p的左子树
         }
       if(top>=0)
         {
           p=stack[top--];        //出栈第一个结点
           cout<<p->data<<"    "; //访问结点
           p=p->rchild;       //继续探索右子树
         }
      }while(top>=0);        //当栈不空时继续遍历
}
void main()
{
  btnode *p1;
  cout<<"输入二叉树:"<<endl;
  p1= createbtree();  //建立二叉树
  cout<<"中序遍历二叉树的非递归序列:"<<endl;
  nrinorder(p1);
}