【二叉树】前序遍历+中序遍历->建树

描述输入一棵二叉树的先序和中序遍历序列,输出其后序遍历序列。输入输入文件为tree.in,共两行,第一行一个字符串,表示树的先序遍历,第二行一个字符串,表示树的中序遍历。树的结点一律用小写字母表示。输出输出文件为tree.out,仅一行,表示树的后序遍历序列。

样例输入

abdec
dbeac

样例输出

debca

#include <iostream>
#include <cstring>
#define MAX 50+3
using namespace std;
typedef char Elem_Type;
typedef struct BiTree
{
  Elem_Type data;//数据
  BiTree *Lchild;//左孩子
  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 *front, Elem_Type *center, int len)
//前序遍历         中序遍历   中序数组长度
{
  if (len <= 0)
    return NULL;
  BiTree *temp = new BiTree;
  temp->data = *front;
  int index = Search_Num(*front, center, len);
  temp->Lchild = Resume_BiTree(front + 1, center, index);
  temp->Rchild = Resume_BiTree(front + index + 1, center + index + 1, len - index - 1);
  return temp;
}

void PostOrder_Traverse(BiTree *root)//后序
{
  if (root != NULL)
  {
    PostOrder_Traverse(root->Lchild);
    PostOrder_Traverse(root->Rchild);
    cout << root->data;
  }

}

int main()
{
  Elem_Type *preorder = new Elem_Type[MAX];//前序
  Elem_Type *inorder = new Elem_Type[MAX];//中序
  cin >> preorder; 
  cin >> inorder;
  BiTree *root = Resume_BiTree(preorder, inorder, strlen(inorder));
  PostOrder_Traverse(root);
  cout << endl;
  return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 2 =