数据结构
网络
关系数据库管理系统 (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+ 次浏览
广告