u012987455
zh_main
2016-02-21 07:36
采纳率: 0%
浏览 2.3k

大神求教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
    把分全给哥 2016-02-21 07:38
    点赞 评论
  • KesarChen
    KesarChen 2016-02-21 07:57

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

    点赞 评论

相关推荐