2016-02-21 07:36

# 大神求教C语言，知道二叉树先序中序遍历序列，求后序遍历序列。

#include
#include
#include

using namespace std;

typedef struct Btree
{
struct Btree *left;
struct Btree *right;
char data;
}Node;

void Create_Btree(Node *tree, char *pre, int pre_low, int pre_high, char *middle, int middle_low, int middle_high)
{
tree = (Node *)malloc(sizeof(Node));
tree->data = pre[pre_low];
tree->left = NULL;
tree->right = NULL;
printf("shuju:%c %d %d\n", tree->data, tree->left, tree->right);
//计算树根在中序遍历中的下标
int root = middle_low;
int i = root;
while(pre[pre_low] != middle[i])
{
i++;
root++;
}
printf("root : %d\n", root);
//中序左子树的长度
int left_length = root - middle_low;
printf("%d--%d %d--%d\n", pre_low + 1, pre_low + left_length, middle_low, root - 1);
printf("%d--%d %d--%d\n", pre_low + left_length + 1, pre_high, root + 1, middle_high);

`````` //遍历创建左子树
if(root > middle_low)
{
printf("left\n");
Create_Btree(tree->left, pre, pre_low + 1, pre_low + left_length, middle, middle_low, root - 1);
}
//遍历创建右子树
if(root < middle_high)
{
printf("right\n");
Create_Btree(tree->right, pre, pre_low + left_length + 1, pre_high, middle, root + 1, middle_high);
}
``````

}

{
return;
else
}

int main()
{
char pre_order[27];
char middle_order[27];
while(~scanf("%s %s", pre_order, middle_order) && pre_order != "")
{
printf("%s\n%s\n", pre_order, middle_order);
if(pre_order[1] == '\0')
{
printf("%c\n", pre_order[0]);
continue;
}
else
{
Node *tree;
int len = strlen(pre_order);
Create_Btree(tree, pre_order, 0 , len - 1, middle_order, 0, len - 1);
Post_order(tree);
printf("\n");
}
}
}