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

相关文章
|
2天前
|
算法 Java 机器人
Java数据结构与算法:AVL树
Java数据结构与算法:AVL树
|
2天前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
10 4
|
1天前
|
Java
Java二叉树的遍历
Java二叉树的遍历
|
6天前
|
算法 Java 索引
【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
17 5
|
5天前
|
Java 数据安全/隐私保护 开发者
Java是一种完全支持面向对象编程的语言,其面向对象特性包括封装、继承、多态和抽象等
【6月更文挑战第18天】**面向对象编程(OOP)通过对象封装状态和行为,实现问题域的抽象。Java全面支持OOP,核心特性包括**: - **封装**:保护数据安全,隐藏内部细节。 - **继承**:子类继承父类属性和行为,促进代码重用。 - **多态**:一个接口多种实现,增强灵活性和扩展性。 - **抽象**:通过接口和抽象类抽离共性,简化复杂性。 **Java的OOP便于理解和解决复杂系统问题。**
19 3
|
4天前
|
算法 搜索推荐 Java
二叉树的基本概念、常见操作以及如何使用Java代码
二叉树的基本概念、常见操作以及如何使用Java代码
8 1
|
9天前
|
存储 安全 Java
深入解析Java HashMap的高性能扩容机制与树化优化
深入解析Java HashMap的高性能扩容机制与树化优化
9 1
|
5天前
|
Java 大数据 API
|
9天前
|
IDE Oracle Java
[笔记] 疯狂JAVA讲义(第3版) 第1章 Java语言概述与开发环境
[笔记] 疯狂JAVA讲义(第3版) 第1章 Java语言概述与开发环境
|
13天前
|
存储 缓存 Java
Java遍历Map集合的方法
在Java中,遍历Map集合主要有四种方式:1) 使用`keySet()`遍历keys并用`get()`获取values;2) 使用`entrySet()`直接遍历键值对,效率较高;3) 通过`Iterator`遍历,适合在遍历中删除元素;4) Java 8及以上版本可用`forEach`和Lambda表达式,简洁易读。`entrySet()`通常性能最佳,而遍历方式的选择应考虑代码可读性和数据量。
28 0