二叉树的遍历代码

二叉树的遍历代码
#include<stdio.h>
#include<stdlib.h>
#define num 100
typedef char DataType;
//二叉树的二叉链表存储结构
typedef struct node {
 DataType data;
 struct node *lchild,*rchild;
}BinTNode;
 
 
typedef BinTNode *BinTree; 
 
int found;
BinTNode*p;

void Preorder(BinTree bt)//先序遍历二叉树
{
 BinTNode *stack[num];
 int top=0;
 BinTNode *s;
 stack[top]=bt;
 while(top>=0)
 {
  s=stack[top];
  top--;
  if(s!=NULL)
  {
   printf("%c",s->data);
   top++;
   stack[top]=s->rchild;
   top++;
   stack[top]=s->lchild;
  }
 }
}
void Inorder(BinTree bt)//中序遍历二叉树
{
 BinTNode *stack[num];
 int top=0;
 stack[top]=bt;
 do
 {
  while(stack[top]!=NULL)
  {
   top=top+1;
   stack[top]=stack[top-1]->lchild;
  }
  top=top-1;
  if(top>=0)
  {
   printf("%c",stack[top]->data);
   stack[top]=stack[top]->rchild;
  }
 }while(top>=0);
}
void Postorder(BinTree bt)//后序遍历二叉树
{
 BinTNode *stack[num];
 int tag[num];
 int top;
 BinTNode *s;
 top=0;
 s=bt;
 do
 {
  while(s!=NULL)
  {
   top++;
   stack[top]=s;
   tag[top]=0;
   s=s->lchild;
  }
  if(top>0)
  {
   s=stack[top];
   if(tag[top]==1)
   {
    printf("%c",stack[top]->data);
    top--;
    s=stack[top];
   }
   if(top>0)
   {
    if(tag[top]!=1)
    {
     s=s->rchild;
     tag[top]=1;
    }
    else s=NULL;
   }
  }
 }while(top!=0);
}
BinTree CreateBinTree(BinTree bt)//先序遍历生成二叉树
{
 BinTNode * Q[num];
 BinTNode *s;
 int front,rear;
 char ch;
 ch=getchar(); bt=NULL;
 front=1; rear=0;
 while(ch!='#'){
  s=NULL;
  if(ch!=' '){
   s=(BinTNode *)malloc(sizeof(BinTNode));
   s->data=ch;s->lchild=s->rchild=NULL;
  }
  rear++;
  Q[rear]=s;
  if(rear==1)
   bt=s;
  else
  { if(s!=NULL&&Q[front]!=NULL)
    if(rear % 2==0)
     Q[front]->lchild=s;
    else
     Q[front]->rchild=s;
    if(rear % 2!=0)
     front++;
  }
  ch=getchar();
 }
 return bt;
}
 
 
void main()
{
 BinTree bt;
 int xz;
 
 while(1){
  printf("**************二叉树的遍历**************\n");
     printf("         1.建立二叉树储存结构   \n");
  printf("         2.求二叉树的先序遍历   \n");
  printf("         3.求二叉树的中序遍历   \n");
  printf("         4.求二叉树的后序遍历   \n");
  printf("         5.退出. \n");
          
        printf("Input your choice:");
  scanf("%d",&xz);
  switch(xz){
   case 1: printf("输入二叉树的按层结点值(按#号键结束):");
         bt=CreateBinTree(bt);
      printf("二叉树的链式存储结构建立完成!\n");
      break;
            case 2: printf("该二叉树的先序遍历序列为:");
         Preorder(bt);
      printf("\n");
      break;
            case 3: printf("该二叉树的中序遍历序列为:");
         Inorder(bt);
      printf("\n");
      break;
            case 4: printf("该二叉树的后序遍历序列为:") ;
         Postorder(bt);
      printf("\n");
      break;
   case 5:  break;
   default: printf("error input!\n");break;
  }
  if(xz==5)  break;
 }
}619

  • 上一篇文章:
  • 下一篇文章:
  • Copyright © 2007-2012 www.chuibin.com 六维论文网 版权所有