二叉树遍历序列还原-蒲公英云

二叉树遍历序列还原

迷南。 2022-06-02 07:23 284阅读 0赞

成绩	10	开启时间	2017年11月6日星期一 12:20
折扣	0.8	折扣时间	2017年11月28日星期二 18:20
允许迟交	否	关闭时间	2018年01月8日星期一 18:20

给出二叉树的中序遍历序列和后序遍历序列，编程还原该二叉树。

输入：
　　第1行为二叉树的中序遍历序列
　　第2行为二叉树的后序遍历序列

输出：
　　二叉树的按层遍历序列

	测试输入	期待的输出	时间限制	内存限制
测试用例 1	以文本方式显示 badcfeg↵ bdfgeca↵	以文本方式显示 abcdefg↵	1秒	64M
测试用例 2	以文本方式显示 cbdafeg↵ cbdfgea↵	以文本方式显示 adebfgc↵	1秒	64M
测试用例 3	以文本方式显示 edcba↵ edcba↵	以文本方式显示 abcde↵	1秒	64M
测试用例 6	以文本方式显示 bdfgeca↵ gfedcba↵	以文本方式显示 abcdefg↵	1秒	64M

此题有一定的借鉴成分。

这题多写了几个与本体无关的函数。BuildTree这个函数是有用的俄，而PostMidCreateTree这个函数是从网上看到的，但没成功。

InOrderTravers这个函数是因为当时没看懂题就写了个中序遍历，其实应该是Leveltravers这个函数

#include <string>   
#include <iostream>   
#include<queue> 
using namespace std; 
//二叉链表表示二叉树   
typedef struct BiNode 
{ 
    char data;//节点数据   
 struct BiNode * lchild;//左孩子   
 struct BiNode * rchild;//右孩子   
}BiNode, *BiTree; 
void BuildTree(BiTree &t,string Inorder,string Postorder) 
{ 
  if (Inorder.length()==0) 
   { 
      //t = NULL; 
        return; 
    } 
  int length_Post = Postorder.length(); 
  char Rootnode = Postorder[length_Post- 1]; 
 int index = Inorder.find(Rootnode); 
    string lchild_inorder = Inorder.substr(0, index);//左孩子的中序序列 
    string rchild_inorder = Inorder.substr(index + 1);//右孩子的中序序列 
   int lchild_length = lchild_inorder.length();//左孩子长度 
    int rchild_length = rchild_inorder.length();//右孩子长度 
    string rchild_postorder = Postorder.substr(lchild_length, length_Post - 1 - lchild_length);//右孩子的后序序列 
  string lchild_postorder = Postorder.substr(0,lchild_length);//左孩子的后序序列 
    t = (BiTree)malloc(sizeof(BiNode)); 
    if (t) 
 { 
      t->data = Rootnode; t->lchild = t->rchild = NULL; 
     BuildTree(t->lchild,lchild_inorder,lchild_postorder);//创建左孩子 
        BuildTree(t->rchild, rchild_inorder, rchild_postorder);//创建右孩子 
  } 
} 
char post[50]; 
char mid[50]; 
int Position(char c) 
 { 
     return strchr(mid, c) - mid; 
} 
void PostMidCreateTree(BiTree &pn, int i, int j, int len) 
{ 
     if (len <= 0) 
         return; 
  pn = new BiNode; pn->lchild = pn->rchild = NULL; 
     pn->data = post[i]; 
     int m = Position(post[i]); 
     PostMidCreateTree(pn->lchild, i - 1 - (len - 1 - (m - j)), j, m - j);//注意参数:m-j左子树的长度,len-1-(m-j)右子树的长度 
     PostMidCreateTree(pn->rchild, i - 1, m + 1, len - 1 - (m - j)); 
 } 
void InOrderTraverse(BiTree & t) 
{ 
 if (t != NULL) 
 { 
     InOrderTraverse(t->lchild); 
     cout << t->data; 
      InOrderTraverse(t->rchild); 
 } 
} 
void leveltravers(BiTree t) 
{ 
 queue<BiTree> Q; 
 BiTree cur = t; 
    Q.push(cur); 
   while (!Q.empty()) 
 { 
      cur = Q.front(); 
       Q.pop(); 
       printf("%c", cur->data); 
       if (cur->lchild) 
        { 
          Q.push(cur->lchild); 
        } 
      if (cur->rchild) 
            Q.push(cur->rchild); 
    } 
} 
int main() 
{ 
    BiTree t; 
  string Inorder; 
    string Postorder; 
  getline(cin, Inorder); 
 getline(cin, Postorder); 
   BuildTree(t, Inorder, Postorder); 
  leveltravers(t); 
   printf("\n"); 
  return 0; 
}