注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

倚楼听风雨

没有理想的人,永远也不能翱翔与蓝天白云之上~

 
 
 

日志

 
 

二叉树的各种遍历  

2007-11-29 01:30:28|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include <stdio.h>
#include <malloc.h>
#define maxsize  100
typedef char elemtype;
typedef struct node
{
 elemtype data;
 struct node *lchild;
 struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str)
{
 BTNode *St[maxsize],*p=NULL;
 int top=-1,k,j=0;
 char ch;
 b=NULL;
 ch=str[j];
 while(ch!='\0')
 {
  switch(ch)
  {
  case '(':top++;St[top]=p;k=1;
   break;
  case ')':top--;
   break;
  case ',':k=2;
   break;
  default:p=(BTNode*)malloc(sizeof(BTNode));
   p->data=ch;
   p->lchild=p->rchild=NULL;
   if(b==NULL)
    b=p;
   else
   {
    switch(k)
    {
    case 1:St[top]->lchild=p;
     break;
    case 2:St[top]->rchild=p;
     break;
    }
   }
  }
  j++;
  ch=str[j];
 }
}
void DispBTNode(BTNode *b)
{
 if(b!=NULL)
 {
  printf("%c",b->data);
  if(b->lchild!=NULL || b->rchild!=NULL)
  {
   printf("(");
   DispBTNode(b->lchild);
   if(b->rchild!=NULL)
    printf(",");
   DispBTNode(b->rchild);
   printf(")");
  }
 }
}
void TravLevel(BTNode *b)
{
 BTNode *Qu[maxsize];
 int front,rear;
 front=rear=0;
 if(b!=NULL)
  printf("%c",b->data);
 rear++;
 Qu[rear]=b;
 while(rear!=front)
 {
  front=(front+1)%maxsize;
  b=Qu[front];
  if(b->lchild!=NULL)
  {
   printf("%c",b->lchild->data);
   rear=(rear+1)%maxsize;
   Qu[rear]=b->lchild;
  }
  if(b->rchild!=NULL)
  {
   printf("%c",b->rchild->data);
   rear=(rear+1)%maxsize;
   Qu[rear]=b->rchild;
  }
 }
 printf("\n");
}
void PreOrder(BTNode *b)
{
 if(b!=NULL)
 {
  printf("%c",b->data);
  PreOrder(b->lchild);
  PreOrder(b->rchild);
 }
}
void InOrder(BTNode *b)
{
 if(b!=NULL)
 {
  InOrder(b->lchild);
  printf("%c",b->data);
  InOrder(b->rchild);
 }
}
void PosOrder(BTNode *b)
{
 if(b!=NULL)
 {
  PosOrder(b->lchild);
  PosOrder(b->rchild);
  printf("%c",b->data);
 }
}
void PreOrder1(BTNode *b)
{
 BTNode *p;
 struct
 {
  BTNode *pt;
  int tag;
 }St[maxsize];
 int top=-1;
 top++;
 St[top].pt=b;
 St[top].tag=1;
 while(top>-1)
 {
  if(St[top].tag==1)
  {
   p=St[top].pt;
   top--;
   if(p!=NULL)
   {
    top++;
    St[top].pt=p->rchild;
    St[top].tag=1;
    top++;
    St[top].pt=p->lchild;
    St[top].tag=1;
    top++;
    St[top].pt=p;
    St[top].tag=0;
   }
  }
  if(St[top].tag==0)
  {
   printf("%c",St[top].pt->data);
   top--;
  }
 }
}
void InOrder1(BTNode *b)
{
 BTNode *p;
 struct
 {
  BTNode *pt;
  int tag;
 }St[maxsize];
 int top=-1;
 top++;
 St[top].pt=b;
 St[top].tag=1;
 while(top>-1)
 {
  if(St[top].tag==1)
  {
   p=St[top].pt;
   top--;
   if(p!=NULL)
   {
    top++;
    St[top].pt=p->rchild;
    St[top].tag=1;
    top++;
    St[top].pt=p;
    St[top].tag=0;
    top++;
    St[top].pt=p->lchild;
    St[top].tag=1;
   }
  }
  if(St[top].tag==0)
  {
   printf("%c",St[top].pt->data);
   top--;
  }
 }
}
void PosOrder1(BTNode *b)
{
 BTNode *p;
 struct
 {
  BTNode *pt;
  int tag;
 }St[maxsize];
 int top=-1;
 top++;
 St[top].pt=b;
 St[top].tag=1;
 while(top>-1)
 {
  if(St[top].tag==1)
  {
   p=St[top].pt;
   top--;
   if(p!=NULL)
   {
    top++;
    St[top].pt=p;
    St[top].tag=0;
    top++;
    St[top].pt=p->rchild;
    St[top].tag=1;
    top++;
    St[top].pt=p->lchild;
    St[top].tag=1;
   }
  }
  if(St[top].tag==0)
  {
   printf("%c",St[top].pt->data);
   top--;
  }
 }
}
void PreOrder2(BTNode *b)
{
 BTNode *St[maxsize],*p;
 int top=-1;
 if(b!=NULL)
 {
  top++;
  St[top]=b;
  while(top>-1)
  {
   p=St[top];
   top--;
   printf("%c",p->data);
    if(p->rchild!=NULL)
    {
     top++;
     St[top]=p->rchild;
    }
    if(p->lchild!=NULL)
    {
     top++;
     St[top]=p->lchild;
    }
  }
  printf("\n");
 }
}

void main()
{
 BTNode *b;
 CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
 printf("(1)输出二叉树:");
 DispBTNode(b);
 printf("\n");
 printf("层次遍历序列:");
 TravLevel(b);
 printf("\n");
 printf("先序遍历序列:");
 PreOrder(b);
 printf("\n");
 printf("中序遍历序列:");
 InOrder(b);
 printf("\n");
 printf("后序遍历序列:");
 PosOrder(b);
 printf("\n");
 printf("非递归先序遍历序列:");
 PreOrder1(b);
 printf("\n");
 printf("非递归中序遍历序列:");
 InOrder1(b);
 printf("\n");
 printf("非递归后序遍历序列:");
 PosOrder1(b);
 printf("\n");
 printf("第二种非递归先序遍历序列:");
 PreOrder2(b);
 printf("\n");
}

  评论这张
 
阅读(171)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017