Tree Traversals Again(Java语言)(先序和中序创建二叉树)(遍历树)

简介: 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.


f8533843d15949c3972ab8f5cd5d5ab6.png

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

解题思路:

通过题目可以发现push是先序遍历,pop是中序遍历,然后根据先序和中序构造树,后序遍历出结果。

代码:

package text2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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
    BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(read.readLine());
    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++) {
      String[] str = read.readLine().split(" ");
      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);
      post.add(root.element);
    }
  }

}
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;
  }
}

相关文章
|
4天前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
16 4
|
1天前
|
算法 Java
垃圾回收机制(Garbage Collection,GC)是Java语言的一个重要特性,它自动管理程序运行过程中不再使用的内存空间。
【6月更文挑战第24天】Java的GC自动回收不再使用的内存,关注堆中的对象。通过标记-清除、复制、压缩和分代等算法识别无用对象。GC分为Minor、Major和Full类型,针对年轻代、老年代或整个堆进行回收。性能优化涉及算法选择和参数调整。
13 3
|
4天前
|
算法 Java 机器人
Java数据结构与算法:AVL树
Java数据结构与算法:AVL树
|
1天前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
10 2
|
1天前
|
缓存 Java 测试技术
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
6 1
|
4天前
|
Java
Java二叉树的遍历
Java二叉树的遍历
|
7天前
|
Java 数据安全/隐私保护 开发者
Java是一种完全支持面向对象编程的语言,其面向对象特性包括封装、继承、多态和抽象等
【6月更文挑战第18天】**面向对象编程(OOP)通过对象封装状态和行为,实现问题域的抽象。Java全面支持OOP,核心特性包括**: - **封装**:保护数据安全,隐藏内部细节。 - **继承**:子类继承父类属性和行为,促进代码重用。 - **多态**:一个接口多种实现,增强灵活性和扩展性。 - **抽象**:通过接口和抽象类抽离共性,简化复杂性。 **Java的OOP便于理解和解决复杂系统问题。**
20 3
|
6天前
|
算法 搜索推荐 Java
二叉树的基本概念、常见操作以及如何使用Java代码
二叉树的基本概念、常见操作以及如何使用Java代码
10 1
|
1天前
|
Java
java使用递归遍历文件目录
java使用递归遍历文件目录
5 0
|
7天前
|
Java 大数据 API