Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1523
Question Name: Print Binary Tree By Level
Question Description: Give a binary tree, print it out in level-order.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one interger N (0 <= N <= 1000), saying the size of the binary tree. The second line includes N integers, as the value of each node in the tree (the first node is the root node). Then the following N lines have three four formations. The i(th) line is
1. Character “z” means the (i)th node has no child; OR
2. Character “l” and one integer LS, means the (i)th node has (LS)th node as its left son; OR
3. Character “r” and one integer RS, means the (i)th node has (RS)th node as its right son; OR
4. Character “d” and two integers LS and RS, means the (i)th node has (LS)th node as its left son, and (RS)th node as its right son.
PS: both the line NO. and the nodes are 1-based index.
Output: “NULL” if the tree is empty. Otherwise, print out the value of the tree in level-order.
1 2 3 4 5 6 7 8 9 10 11 12 | Input: 7 8 6 5 7 10 9 11 d 2 5 d 3 4 z z d 6 7 z z Output: 8 6 10 5 7 9 11 |
The solution is easy with queue in Java.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/11/2014 * Last updated: 08/11/2014 * * Filename: PrintBinaryTreeByLevel.java * Compilation: javac PrintBinaryTreeByLevel.java * Execution: java PrintBinaryTreeByLevel * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.LinkedList; import java.util.Queue; /** * This class include a definition of binary tree, and the function to * travel the tree by level. * @author Sheng Yu codesays.com */ public class PrintBinaryTreeByLevel { /** * The definition of binary tree. * @author Sheng Yu codesays.com * @param <T> the type of the value in the node. */ private static class BinaryTreeNode<T> { /** The value of current node. */ private T value = null; /** The left of current node. */ private BinaryTreeNode<T> left = null; /** The right son of current node. */ private BinaryTreeNode<T> right = null; /** @return the value of this node. */ public T getValue() { return value; } /** @param newValue the new value of this node. */ public void setValue(final T newValue) { value = newValue; } /** @return the left son of this node. */ public BinaryTreeNode<T> getLeft() { return left; } /** @param newLeft the new left son of this node. */ public void setLeft(final BinaryTreeNode<T> newLeft) { left = newLeft; } /** @return the right son of this node. */ public BinaryTreeNode<T> getRight() { return right; } /** @param newRight the new right son of this node. */ public void setRight(final BinaryTreeNode<T> newRight) { right = newRight; } } /** * Do a level-order visit to the given tree. * @param root the root node of the binary tree. * @return a string representing the content in the tree. */ @SuppressWarnings("rawtypes") public final String levelOrderVisit(final BinaryTreeNode root) { if (root == null) { // Empty tree. return "NULL"; } StringBuilder sb = new StringBuilder(); Queue<BinaryTreeNode> nodes = new LinkedList<BinaryTreeNode>(); nodes.offer(root); BinaryTreeNode current = null; boolean enqueueRes = true; while (!nodes.isEmpty()) { current = (BinaryTreeNode) nodes.poll(); // Get it successfully. assert current != null; sb.append(current.getValue().toString()); sb.append(" "); if (current.getLeft() != null) { // Left sub-tree enqueueRes = nodes.offer(current.getLeft()); // Enqueue the item successfully. assert enqueueRes; } if (current.getRight() != null) { // Right sub-tree enqueueRes = nodes.offer(current.getRight()); // Enqueue the item successfully. assert enqueueRes; } } sb.setLength(sb.length() - 1); // Skip the last space. return sb.toString(); } /** * Test stub. * @param args the command line arguments. * @throws IOException when input gets error. */ @SuppressWarnings("unchecked") public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); BinaryTreeNode<Integer>[] tree = null; BinaryTreeNode<Integer> root = null; PrintBinaryTreeByLevel visitor = new PrintBinaryTreeByLevel(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the size of the two trees. tree = null; if ((int) st.nval > 0) { tree = (BinaryTreeNode<Integer>[]) new BinaryTreeNode[(int) st.nval]; } // Get the content of the two trees. if (tree != null) { // Get the value of each node. for (int i = 0; i < tree.length; ++i) { st.nextToken(); tree[i] = new BinaryTreeNode<Integer>(); tree[i].setValue((int) st.nval); } // Get the son information. for (int i = 0; i < tree.length; ++i) { st.nextToken(); if (st.sval.equals("d")) { // Has both left and right sons. st.nextToken(); tree[i].setLeft(tree[((int) st.nval) - 1]); st.nextToken(); tree[i].setRight(tree[((int) st.nval) - 1]); } else if (st.sval.equals("l")) { // Has only left son. st.nextToken(); tree[i].setLeft(tree[((int) st.nval) - 1]); } else if (st.sval.equals("r")) { // Has only right son. st.nextToken(); tree[i].setRight(tree[((int) st.nval) - 1]); } else if (st.sval.equals("z")) { // No son. NOPE. assert true; } else { // Invalid input. throw new IllegalArgumentException("Invalid son info."); } } } // Find the root node. if (tree == null) { root = null; } else { root = tree[0]; } // Print the tree by level. System.out.println(visitor.levelOrderVisit(root)); } } } |