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

记录创意的火花

天天学习,好好向上

 
 
 

日志

 
 

已知二叉树的先序和中序求后序  

2009-11-06 14:44:11|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

 二叉树的根结点(根据三种遍历)只可能在左右(子树)之间,或这左子树的左边,或右子树的右边。
如果已知先序和中序(如果是中序和后序已知也可以,注意:如果是前序和后序的求中序是不可能实现的),先确定这棵二叉树。
步骤:1,初始化两个数组,存放先序合中序。
2,对比先序和中序,在中序忠查找先序的第一个元素,则在中序遍历中将这个元素的左右各元素分成两部分。即的左边的部分都在这个元素的左子树中,右边的部分都在右子树中。
3,然后从从先序的第二个元素开始继续上面的步骤。
// tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "string.h"

typedef struct node
{
char data;
struct node *lchild,*rchild;
}BinNode;
typedef BinNode *BinTree;
BinNode *CreateNode(char c)
{
BinNode *n1=new BinNode;
n1->data=c;
n1->lchild=NULL;
n1->rchild=NULL;
return n1;
}
int searchchar(char c,char *order)
{
for(int i=0;i<strlen(order);i++)
{
if(c==order[i])
return i;

}
return -1;
}

BinNode* CreateTree(char *pre,char *in)
{
char c=pre[0];
char temppre[100];
char tempin[100];
char *p;
int i=0;
BinNode* bnode;
if(pre=='\0')
return NULL;

memset(temppre,0,100);
memset(tempin,0,100);

bnode=CreateNode(c);
i=searchchar(pre[0],in);
if(i==-1)
return 0;
p=in;
strncpy(tempin,p,i);
p=pre;
strncpy(temppre,p+1,i);
bnode->lchild=CreateTree(temppre,tempin);//left

memset(tempin,0,100);
memset(temppre,0,100);

p=in+i+1; 
strncpy(tempin,p,strlen(in)-i);
p=pre+i+1;
strncpy(temppre,p,strlen(in)-i);
bnode->rchild=CreateTree(temppre,tempin); //right
return bnode;
}

void POSTORDER(BinNode *t) 

if(t) /*二叉树t非空*/ 

POSTORDER(t->lchild); /*后序遍历*t的左子树*/ 
POSTORDER(t->rchild); /*后序遍历*t的右子树*/ 
printf("\t%c",t->data); /*访问结点*/ 



int main(int argc, char* argv[])
{
char preorder[100];
char inorder[100];

BinNode* Head;

do{
printf("请输入前序序列\n");
scanf("%s",preorder);
printf("请输入中序序序列\n");
scanf("%s",inorder);
}while(strlen(preorder)!=strlen(inorder));

Head=CreateTree(preorder,inorder);
printf("后序序列为:");
POSTORDER(Head);
printf("\n");
// printf("%ld",strlen(readin));
return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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