首页 > 代码库 > 数据结构重建二叉树

数据结构重建二叉树

2024-10-18 11:46:02   203人阅读

重建二叉树，知道先序和中序   输出二叉树的后序。。

技术分享
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int M = 1005;int i,j,k;int Max (int x ,int y){return x>y?x:y ;}void build(int n,char *s1,char *s2){    if(n<=0) return ;    int p = strchr(s2,s1[0]) - s2; //找到根节点在中序遍历中的位置    build(p,s1+1,s2);    build(n-p-1,s1+p+1,s2+p+1);    printf("%c",s1[0]);}int main (){    char s1[30],s2[30];    scanf("%s%s",s1,s2);    int len = strlen(s1);    build(len,s1,s2);return 0;}
View Code

 

 

下面是NYOJ上的数据结构的一道题，知道中序和后序 求先序。。之前看什么指针真是醉了，不过昨天复习数据结构的时候，还是将它用结构体和指针实现了

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;const int M = 1005;typedef struct BTNode{    char data;    BTNode  *lchild,*rchild;};BTNode *Creat(char *post,char *in ,int n){    BTNode *s;    char r,*p;    int k;    if(n<=0) return NULL;    r = *(post + n-1);    s = (BTNode *)malloc(sizeof(BTNode));    s->data =http://www.mamicode.com/ r;    for(p=in;p<in+n;p++){        if(*p == r) break;    }    k = p - in;    s->lchild = Creat(post,in,k);    s->rchild = Creat(post+k,p+1,n-k-1);    return s;}void pre(BTNode *s){    if(s!=NULL){          printf("%c",s->data);          pre(s->lchild);          pre(s->rchild);    }}int main (){  char s1[30],s2[30];  BTNode *p;  while(scanf("%s%s",s1,s2)!=EOF){  int len = strlen(s1); p = Creat(s1,s2,len);  pre(p);  printf("\n");  }return 0;}

 

数据结构重建二叉树


联系
我们