数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究在C++中根据先序遍历查找二叉搜索树的后序遍历
在这个问题中，我们得到一个数组preOrder[]，它表示二叉搜索树的先序遍历。我们的任务是从先序遍历中找到二叉搜索树的后序遍历。
让我们举个例子来理解这个问题：
输入
preOrder[] = {5, 2, 4, 7, 12}输出
{4, 2, 12, 7, 5}解决方案
解决这个问题的一个简单方法是从给定的先序遍历创建一个二叉搜索树。然后进行树的后序遍历。这个解决方案还可以，但是更有效率的解决方案是：
我们将使用对值的限制遍历先序数组，以分离左子树和右子树的值。
遍历顺序为：
preOrder : Root -> Left -> Right postOrder : Left -> Right -> Root
对于先序遍历中的第一个元素（根元素），其限制为{INT_MIN, 根}。然后遍历先序数组和第一个元素，并将限制中的所有元素与限制的最后一个值交换。类似地，我们将对右子树执行此操作，并将根添加到末尾。
演示我们解决方案的程序：
示例
#include <iostream>
using namespace std;
void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int
upperLimit, int& index){
if (index == n)
return;
if (pre[index] < lowerLimit || pre[index] > upperLimit)
return;
int currNode = pre[index];
index++;
findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index);
findPostOrderTraversalRec(pre, n, currNode, upperLimit, index);
cout<<currNode<<" ";
}
void findPostOrderTraversalFromPreOrder(int pre[], int n){
int index = 0;
findPostOrderTraversalRec(pre, n, -1000, 1000, index);
}
int main(){
int pre[] = { 5, 2, 4, 7, 12 };
int n = sizeof(pre) / sizeof(pre[0]);
cout<<"PreOrder Traversal : \t";
for(int i = 0; i < n ; i++)
cout<<pre[i]<<" ";
cout<<endl<<"Post Order Traversal : \t";
findPostOrderTraversalFromPreOrder(pre, n);
return 0;
}输出
PreOrder Traversal − 5 2 4 7 12 Post Order Traversal − 4 2 12 7 5
另一种解决这个问题的方法是使用迭代。我们知道先序遍历是根->左->右，而后序遍历是左->右->根。这可以使用循环计算，并计算枢轴元素（左元素的最后一个元素所在的位置）。使用它，我们将先打印左子树，然后打印右子树，最后打印根。
枢轴是通过查找小于根的较大元素的索引找到的。
演示我们解决方案的程序：
示例
#include <iostream>
using namespace std;
void findPostOrderTraversalFromPreOrder(int pre[], int n){
int pivot = 0;
for(int i = 1; i < n; i++){
if (pre[0] <= pre[i]) {
pivot = i;
break;
}
}
for(int i = pivot - 1; i > 0; i--){
cout << pre[i] << " ";
}
for(int i = n - 1; i >= pivot; i--) {
cout << pre[i] << " ";
}
cout << pre[0];
}
int main(){
int pre[] = { 5, 2, 4, 7, 12 };
int n = sizeof(pre) / sizeof(pre[0]);
cout<<"PreOrder Traversal : \t";
for(int i = 0; i < n ; i++)
cout<<pre[i]<<" ";
cout<<endl<<"Post Order Traversal : \t";
findPostOrderTraversalFromPreOrder(pre, n);
return 0;
}输出
PreOrder Traversal − 5 2 4 7 12 Post Order Traversal − 4 2 12 7 5
更新于：2021年3月16日
1K+ 浏览量
广告