# Tree Traversals Again（Java语言）（先序和中序创建二叉树）（遍历树）

### 题目描述：

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

### Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

### Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop


Sample Output:

3 4 2 6 5 1

### 代码：

package text2;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Stack;

public class TreeTraversalsAgain {
static ArrayList<Integer> post = new ArrayList<>();
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
int pre[] = new int[n];
int in[] = new int[n];

Stack<Integer> stack = new Stack<>();
for(int i=0,j=0,k=0;i<2*n;i++) {
if(str[0].equals("Push")) {//前序
pre[j]=Integer.parseInt(str[1]);
stack.push(pre[j]);
j++;
}else {
in[k]=stack.pop();
k++;
}
}
Node root = buildTree(pre, 0, n-1, in, 0, n-1);
PrintPost(root);
//    System.out.println(post.size());
for(int i=0;i<post.size();i++) {
if(i==0) System.out.print(post.get(i));
else System.out.print(" "+post.get(i));
}

}
//根据前序与中序创建二叉树模板
public static Node buildTree(int pre[],int pbegin,int pend,int in[],int ibegin,int iend) {
if(pbegin>pend||ibegin>iend) return null;
Node root = new Node(pre[pbegin]);//根节点
for(int i=ibegin;i<=iend;i++) {
if(pre[pbegin]==in[i]) {
root.left = buildTree(pre, pbegin+1, pbegin-ibegin+i, in, ibegin, i-1);
root.right = buildTree(pre, pbegin-ibegin+i+1, pend, in, i+1, iend);
}
}
return root;
}
//后序遍历
public static void PrintPost(Node root) {
if(root!=null) {
PrintPost(root.left);
PrintPost(root.right);
}
}

}
class Node{   //树节点类
public int element; //节点值
public Node left;  //左右节点
public Node right;

public Node(int element) {
// TODO Auto-generated constructor stub
this.element = element;
left = right = null;
}
}



|
2天前
|

Java数据结构与算法：AVL树
Java数据结构与算法：AVL树
16 6
|
2天前
|

Java中，树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中，树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点，而BFS利用队列按层次访问。以下是简化的代码片段：[Java代码略]
10 4
|
1天前
|
Java
Java二叉树的遍历
Java二叉树的遍历
|
6天前
|

【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
17 5
|
5天前
|
Java 数据安全/隐私保护 开发者
Java是一种完全支持面向对象编程的语言，其面向对象特性包括封装、继承、多态和抽象等
【6月更文挑战第18天】**面向对象编程（OOP）通过对象封装状态和行为，实现问题域的抽象。Java全面支持OOP，核心特性包括**： - **封装**：保护数据安全，隐藏内部细节。 - **继承**：子类继承父类属性和行为，促进代码重用。 - **多态**：一个接口多种实现，增强灵活性和扩展性。 - **抽象**：通过接口和抽象类抽离共性，简化复杂性。 **Java的OOP便于理解和解决复杂系统问题。**
19 3
|
4天前
|

8 1
|
9天前
|

9 1
|
5天前
|
Java 大数据 API
|
9天前
|
IDE Oracle Java
[笔记] 疯狂JAVA讲义（第3版） 第1章 Java语言概述与开发环境
[笔记] 疯狂JAVA讲义（第3版） 第1章 Java语言概述与开发环境
17 0
|
13天前
|

Java遍历Map集合的方法

28 0