求问个C语言问题 已知二叉树遍历的中序序列和后序序列 输出先序序列 求代码

Question

如题所述

Answer 1

#include <iostream>
#include <cstring>
#define MAX 50
using namespace std;
typedef char Elem_Type;
typedef struct BiTree
{
Elem_Type data;//数据
struct BiTree *Lchild;//左孩子
struct BiTree *Rchild;//右孩子
}BiTree;
//要查找的元素 查找的地方 数组的长度
int Search_Num(Elem_Type num, Elem_Type *array, int len)
{
for (int i = 0; i<len; i++)
if (array[i] == num)
return i;
//return -1;//没有找到
} //前序结果数组 中序结果数组 数组长度

//根据中后序生成二树
BiTree *Resume_BiTree(Elem_Type *post, Elem_Type *center, int len)
{
if (len <= 0)
return NULL;
BiTree *temp = new BiTree;
temp->data = post[len - 1]; //后序最后一个元素即为根元素
int index = Search_Num(temp->data, center, len);
//遍历左孩子 （后序结果中，从第0个元素开始到第index-1个元素都是左子树）
temp->Lchild = Resume_BiTree(post, center, index);
//遍历右孩子 （后序结果中，从第index个元素开始到第Len-2个元素都是右子树(从0计数)）
temp->Rchild = Resume_BiTree(post + index, center + index + 1, len - index - 1);
return temp;
}

void PreOrderTraverse(BiTree *root) //前序遍历输出
{
if (root != NULL)
{
cout << root->data;
PreOrderTraverse(root->Lchild);
PreOrderTraverse(root->Rchild);
}
}

int main(void)
{
Elem_Type *postorder = new Elem_Type[MAX];//后序数组
Elem_Type *inorder = new Elem_Type[MAX];//中序前序数组
cin >> postorder; //先输入后序
cin >> inorder; //再输入前序
BiTree * root = Resume_BiTree(postorder, inorder, strlen(inorder));//由于本例结构元素为char，所以可以用strlen来获元素个数，其他情况可机变
PreOrderTraverse(root);
cout << endl;
delete[] postorder; //释放内存
delete[] inorder;
return 0;
}

Answer 2

首先理解概念：
前序遍历：访问根结点的操作发生在遍历其左右子树之前.
中序遍历：访问根结点的操作发生在遍历其左右子树之中(间).
后序遍历：访问根结点的操作发生在遍历其左右子树之后.
eg：后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历（网上例子）
首先 看后序遍历DBCEFGHA,A为总根节点
然后 寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝；
重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...
最后得到AECDBHGF,再自己验证即可...本回答被提问者和网友采纳