Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1095809
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-09-20 21:30:33

转载自http://old.blog.edu.cn/user4/ecjtuwh/archives/2007/1771114.shtml


二叉树的遍历算法在其他树操作的基础
已知先序和中序求二叉树的后序遍历算法核心是
1、从先序遍历中读入根节点
2、从中序遍历中找到与根节点相等的元素,以此节点将中序序列分成两个部分,左边的为二叉树的
   左子树,右边为二叉树的右子树;
3.递归调用上述步骤得到根节点的左右子树

#i nclude
#i nclude
#i nclude
typedef struct node
{
  char ch;
  struct node *left,*right;
}node;                   // 定义节点的结构
node * creat(char *pre,char *in,int len);
void print(node *head);
int main()
{
  int i,j,k,m,n,len;
  char pre[30],in[30];    // 存储先序和中序遍历的序列
  node *head;
  head=(node*)malloc(sizeof(node));
  while(scanf("%s%s",pre,in)!=EOF)
  { len=strlen(pre);
    head=creat(pre,in,len);
    print(head);
    printf("\n");
  }
  return 0;
}
node * creat(char *pre,char *in,int len)  // 创建后序遍历的函数
{  int k;
   if(len<=0) return NULL;
   node *head=(node*)malloc(sizeof(node));
   head->ch=*pre;
   char *p;
   for(p=in;p!=NULL;p++)
      if(*p==*pre) break;                 // 在中序遍历的序列中得到与先序相同的节点
   k=p-in;
   head->left=creat(pre+1,in,k);          //递归调用得到左子树
   head->right=creat(pre+k+1,p+1,len-k-1);//得到右子树
   return head;
}
void print(node *head)  // 打印后序遍历序列
{
  if(head==NULL) return ;
  print(head->left);
  print(head->right);
  printf("%c",head->ch);
}
阅读(3198) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-09-23 19:01:17

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com