資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 中的中序和後序遍歷的先序遍歷
在這個問題中，我們得到了二叉樹的中序和後序遍歷。我們的任務是列印樹的後序遍歷。
讓我們來看一個例子來理解這個問題
Input:inorder: 16 7 21 12 1 5 9 postorder: 16 21 7 1 9 5 12 Output: preorder: 12 7 16 21 5 1 9 Explanation: the binary tree is :
為了解決這個問題，一個簡單的解決方案可能是使用給定的遍歷建立一棵樹，然後找到樹的先序遍歷。但是這種方法對於系統來說會更加複雜。
解決這個問題一個更有效的解決方案是使用棧資料結構。讓我們看看樹的每個節點。樹的根節點是後序遍歷中的最後一個元素。現在我們必須分離二叉樹的左子樹和右子樹。由於我們知道樹的根節點。在後序遍歷中，根節點之前的所有元素都是左子樹的，根節點之後的元素都是右子樹的。
像這樣，我們將找到所有元素並將節點儲存在棧中，然後列印棧的元素，這將給出先序遍歷。
我們在Java中的解決方案實現
示例
import java.util.Stack;
public class Main {
static int postIndex;
void preOrder(int[] in, int[] post, int inStrt, int inEnd, Stack<Integer> preorder) {
if (inStrt > inEnd)
return;
int val = post[postIndex];
int inIndex = searchValue(in, val);
postIndex--;
preOrder(in, post, inIndex + 1, inEnd, preorder);
preOrder(in, post, inStrt, inIndex - 1, preorder);
preorder.push(val);
}
void printPreOrderTraversal(int[] in, int[] post) {
int len = in.length;
postIndex = len - 1;
Stack<Integer> preorder = new Stack<Integer>();
preOrder(in, post, 0, len - 1, preorder);
while (preorder.empty() == false)
System.out.print(preorder.pop()+" ");
}
int searchValue(int[] in, int data){
int i = 0;
for (i = 0; i < in.length; i++)
if (in[i] == data)
return i;
return i;
}
public static void main(String ars[]){
int in[] = { 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90 };
int post[] = { 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25 };
Main tree = new Main();
System.out.println("Preorder Traversal of the tree is: ");
tree.printPreOrderTraversal(in, post);
}
}輸出
Preorder Traversal of the tree is: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
更新於：2020年2月3日
1K+ 次瀏覽
廣告