資料結構
網路
關係資料庫管理系統 (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+ 瀏覽量
廣告