从C++中的前序遍历中找到BST的后序遍历

2023-06-16 12:20:03 271

在这个问题中，我们给出了一个数组preOrder[]，它表示二叉搜索树的前序遍历。我们的任务是从前序遍历中找到BST的后序遍历。

让我们举个例子来理解这个问题，

输入

preOrder[] = {5, 2, 4, 7, 12}

输出结果

{4, 2, 12, 7, 5}

解决方法

该问题的一个简单解决方案是从给定的前序遍历创建一个BST。然后对树进行后序遍历。这个解决方案是好的，但更有效的解决方案是，

我们将遍历具有值限制的前序数组以分隔左子树和右子树的值。

遍历的顺序是-

preOrder : Root -> Left -> Right
postOrder : Left -> Right -> Root

对于预序中的第一个元素，即根元素。为此，限制为{INT_MIN,Root}。然后遍历preorder数组和第一个元素，并将limit中的所有元素与limit的最后一个值交换。同样，我们将对右子树执行此操作并在末尾添加根。

程序来说明我们的解决方案的工作，

示例

#include 
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<输出结果PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5
解决问题的另一种方法是使用迭代。我们知道root->left->right和postOrder中的preorder是left->right->root。这可以使用循环并计算左元素的最后一个元素所在的枢轴元素来计算。使用这个，我们将首先打印左边，然后是右边，然后是根。
枢轴是通过找到比根更小的更大元素的索引来找到的。
程序来说明我们的解决方案的工作，
示例
#include 
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<输出结果PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5

从C++中的前序遍历中找到BST的后序遍历

输入

解决方法

示例

示例

热门推荐

随机推荐