2 u012987455 u012987455 于 2016.02.21 15: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);
 }

}

void Post_order(Node *head)
{
printf("%d\n", head);
if(head == NULL)
return;
else
Post_order(head->left);
Post_order(head->right);
printf("%c", head->data);
}

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");
}
}
}

哪位大神能运行一下 每次读地址就是post_order()函数里面 读取head-》left 就错误了。
printf("%c:::%d:::%d\n", head->data, head->left, head->right);

2个回答

enpterexpress
enpterexpress   2016.02.21 15:38
KesarChen
KesarChen   2016.02.21 15:57

由先序和中序可还原得到一颗完整的二叉树(先序特点:根左右,根节点在第一位;中序特点:左根右,知道根节点,就知道左右子树的范围,在中序序列的数组中,左子树在根节点左边,右子树在根节点的右边),然后再根据整棵二叉树做一次后续遍历就可以了。

u012987455
u012987455 你运行一下我的代码看看那里有问题
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!