本文主要是介绍重建二叉树NYOJ221题 NYOJ756题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
（一）前序中序求后序:
思路：
结点 getRoot(前序 中序)
{
c = 前序第一个字符；
pos = 在中序的位置；
len1 = 中序pos左半部分长度;
len2 = 中序pos右半部分长度；
新建结点 r，令r的元素等于c；
r 的左儿子 = getRoot(前序位置开始的len1长度部分,中序pos位置左半部分)
r 的 右儿子 = getRoot（前序位置len1开始的右半部分， 中序pos位置的有半部分）
return r;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{char data;struct node *lchild;struct node *rchild;
}Node;
char prev[30], in[30];
Node * getRoot(char *prev, int p1, int p2, char *in, int i1, int i2);
void postOrder(Node *T);
int main(void)
{while(scanf("%s%s", prev, in) != EOF){Node *T;T = getRoot(prev, 0, strlen(prev) - 1, in, 0, strlen(in) - 1);postOrder(T);printf("\n");}return 0;
}
Node * getRoot(char *prev, int p1, int p2, char *in, int i1, int i2)
{char c = prev[p1];//前序的第一个字符;int pos, i, flag;if(prev == NULL || p1 > p2 || p1 < 0 || p2 > strlen(prev) || in == NULL || i1 > i2 || i1 < 0 || i2 > strlen(in))return NULL;//返回空结点for(i = i1; i <= i2; i++)//确定pos = c在in中的位置{if(prev[p1] == in[i]){pos = i;flag = 1;//标记是否找到了c;break;}}if(flag == 0)//返回空结点return NULL;Node *r;r = (Node *)malloc(sizeof(Node));r->data = c;r->lchild = getRoot(prev, p1 + 1, p1 + pos - i1, in, i1, pos - 1);//确定好传递的数组范围;r->rchild = getRoot(prev, p1 + pos - i1 + 1, p2, in, pos + 1, i2);return r;
}
void postOrder(Node *T)
{if(T == NULL)return ;postOrder(T->lchild);postOrder(T->rchild);printf("%c", T->data);
} （二）
知道中序后序求前序：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{char data;struct node *lchild;struct node *rchild;
}Node;
char post[30], in[30];
char *strrev(char string[]);
Node * getRoot(char *post, int p1, int p2, char *in, int i1, int i2);
void prevOrder(Node *T);
int main(void)
{while(scanf("%s%s", post, in) != EOF){Node *T;strcpy(post, strrev(post));//逆转后序;T = getRoot(post, 0, strlen(post) - 1, in, 0, strlen(in) - 1);prevOrder(T);printf("\n");}return 0;
}
Node * getRoot(char *post, int p1, int p2, char *in, int i1, int i2)
{char c = post[p1];//前序的第一个字符;int pos, i, flag;if(post == NULL || p1 > p2 || p1 < 0 || p2 > strlen(post) || in == NULL || i1 > i2 || i1 < 0 || i2 > strlen(in))return NULL;//越界时，返回空结点for(i = i1; i <= i2; i++)//确定pos = c在in中的位置{if(post[p1] == in[i]){pos = i;flag = 1;//标记是否找到了c;break;}}if(flag == 0)//返回空结点return NULL;Node *r;r = (Node *)malloc(sizeof(Node));r->data = c;r->lchild = getRoot(post, p1 + i2 - pos + 1, p2, in, i1, pos - 1);//确定好传递的数组范围;r->rchild = getRoot(post, p1 + 1, p2 - (pos - i1), in, pos + 1, i2);return r;
}
void prevOrder(Node *T)
{if(T == NULL)return ;printf("%c", T->data);prevOrder(T->lchild);prevOrder(T->rchild);
}
char *strrev(char string[])//*** 字符串逆转;
{ char s[1010]; int len = strlen(string); int i, j = 0; for(i = len - 1; i >= 0; i --) { s[j ++] = string[i]; } s[j] = 0; return s;
}
这篇关于重建二叉树NYOJ221题 NYOJ756题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
