首页 > 试题广场 >

Tree Traversals Again (25)

[编程题]Tree Traversals Again (25)

热度指数：4021 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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.

输出描述:

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.

示例1

输入

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

输出

3 4 2 6 5 1

算法知识视频讲解

推荐

orgcheng

解题思路
step one: 首先根据输入，构造出原树的结构。
step two: 后序遍历原树。

关于第一步，需要观察Push和Pop，找出构造原树的方法：
每次Push相当于插入节点，Pop相当于回朔，为了便于回朔的实现，根据最后Pop出的节点的 Id，从已经构造的原树中查找应该回朔到的节点。

关于第二步，如果有n个节点，需要输出n-1个空格，经过观察发现，打印每个节点时，后面跟一个空格，根节点除外，这样就可以打印符合要求的结果，所以只需要能判断是否为根节点即可。

代码如下：

import java.io.PrintStream;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	// 树的定义
	public class Tree{
		int node;
		int id;
		Tree left;
		Tree right;
		public Tree(int id, int node){
			this.id = id;
			this.node = node;
			left = right = null;
		}
	}
	public void treeTraveral(){
		Tree root = recoverTree();
		
		// 后序打印树
		if(root!=null){
			postPrintTree(root, root.id);
		}
	}
	public Tree recoverTree(){
		Stack<Integer> stack = new Stack<>();
		Tree root = null,treeIndex=null;
		int n = Integer.valueOf(in.nextLine());
		
		Integer val,popId=null;
		
		int id = 1;
		// 构造树的结构
		for(int i=0;i<2*n;++i){
			String line = in.nextLine();
			if(line.startsWith("Push")){
				val = Integer.valueOf(line.substring(5));
				stack.push(id);
				
				if(root == null){
					root = new Tree(id++,val);
					treeIndex = root;
				}else{
					if(popId!=null){
						treeIndex = getNodeFromValue(root, popId);
					}
					Tree tmp = new Tree(id++,val);
					if(treeIndex.left == null){
						treeIndex.left = tmp;
					}else{
						treeIndex.right = tmp;
					}
					treeIndex = tmp;
				}
				
				popId=null;
				
			}else{
				popId = stack.pop();
			}
		}
		
		return root;
	}
	/*
	 * 根据节点值，获取树中该节点的引用
	 * 注意：节点值唯一
	 */
	public Tree getNodeFromValue(Tree root, int id){
		// 边界
		if(root == null)
			return null;
		if(root.id == id )
			return root;
		//递归搜索左子树
		Tree result = getNodeFromValue(root.left, id);
		
		//递归搜索右子树
		if(result==null){
			result = getNodeFromValue(root.right, id);
		}
		return result;
	}
	
	/*
	 * 后序打印树中的节点值 
	 */
	public void postPrintTree(Tree root, int rootId){
		if(root==null)
			return;
		
		if(root.left == null && root.right == null){
			out.print(root.node);
			if(root.id!=rootId){
				out.print(" ");
			}
			return;
		}
		// 递归打印左子树
		if(root.left!=null){
			postPrintTree(root.left,rootId);
		}
		// 递归打印右子树
		if(root.right!=null){
			postPrintTree(root.right,rootId);
		}
		
		// 打印父节点
		out.print(root.node);
		if(root.id!=rootId){
			out.print(" ");
		}
	}
	
	public static Scanner in = new Scanner(System.in);
	public static PrintStream out = System.out;
	
	public static void main(String[] args) {
		Main t = new Main();
		t.treeTraveral();
	}
}

编辑于 2015-08-18 21:33:18 回复(0)