重建二叉树——输入前序、中序遍历构建二叉树并输出后序遍历

拼搏现实的明天。 2022-08-07 07:37 157阅读 0赞

重建二叉树（轻量级）

输入某二叉树的前序遍历和中序遍历的结果，重新建立该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。

//输入某二叉树的谦虚遍历和中续遍历的结果，重新简历该二叉树。  
//假设输入的前序遍历和中续遍历的结果中都不含重复的数字  
// 前提：前序遍历\*p1、中序遍历\*p2是正确的  
// by nby  
\#include<iostream>  
using namespace std;  
  
  
struct btnode  
\{  
int data;  
btnode \*pr;  
btnode \*pl;  
\};  
  
  
btnode \*ConstructCode(int \*p1s, int \*p1e, int \*p2s, int \*p2e)  
\{  
btnode \*root = new btnode;  
root->data = \*p1s;  
root->pl = root->pr = NULL;  
if (p1s == p1e)  
return root;  
int i = 0;  
while (1)  
\{  
if (p1s\[0\] == p2s\[i\]) //只有一个节点  
break;  
i++;  
\}  
//root->pl = NULL;  
/\*if (i == 0)  
root->pl = NULL;\*/  
if (i > 0) //左子树  
root->pl = ConstructCode(p1s + 1, p1s + i, p2s, p2e + i - 1);  
//root->pr = NULL;  
/\*if (p1e - p1s == i)  
root->pr = NULL;\*/  
if (p1e-p1s>i)//右子树  
root->pr = ConstructCode(p1s + i + 1, p1e, p2s + i+1, p2e);  
  
  
return root;  
  
  
\}  
  
  
// 前提：前序遍历\*p1、中序遍历\*p2是正确的  
btnode \*Construct(int \*p1, int \*p2, int length)  
\{  
if (p1 == NULL || p2 == NULL || length <= 0)  
return NULL;  
else  
return ConstructCode(p1, p1 + length - 1, p2, p2 + length - 1);  
\}  
  
  
// 后续遍历输出二叉树  
void CoutBree(btnode \*root)  
\{  
if (root == NULL)  
return;  
CoutBree(root->pl);  
CoutBree(root->pr);  
cout << root->data << " ";  
\}  
  
  
  
  
int main()  
\{  
int p1\[\] = \{ 1, 2, 4, 7, 3, 5, 6, 8 \};  
int p2\[\] = \{ 4, 7, 2, 1, 5, 3, 8, 6 \};  
  
btnode \*root = Construct(p1, p2, sizeof(p1) / sizeof(p1\[0\]));  
cout << "后续遍历输出二叉树： ";  
CoutBree(root);  
cout << endl;  
\}