From acff8424e09a3531cae111a93fb0f6fce1d4404e Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 22 Mar 2019 18:02:48 -0500 Subject: In-order and pre-order binary tree traversal done I worked this out myself, using iterative approach instead of recursive to avoid stack overflow issues. Post-order traversal not done yet. I'll likely follow pseudo code from this wiki page to get that done: https://en.wikipedia.org/wiki/Tree_traversal --- .idea/encodings.xml | 4 + src/main/TreeTraversal.java | 173 ++++++++++++++++++++++++++++++++++++++++ src/test/TreeTraversalTest.java | 60 ++++++++++++++ 3 files changed, 237 insertions(+) create mode 100644 .idea/encodings.xml create mode 100644 src/main/TreeTraversal.java create mode 100644 src/test/TreeTraversalTest.java diff --git a/.idea/encodings.xml b/.idea/encodings.xml new file mode 100644 index 0000000..15a15b2 --- /dev/null +++ b/.idea/encodings.xml @@ -0,0 +1,4 @@ + + + + \ No newline at end of file diff --git a/src/main/TreeTraversal.java b/src/main/TreeTraversal.java new file mode 100644 index 0000000..fee494c --- /dev/null +++ b/src/main/TreeTraversal.java @@ -0,0 +1,173 @@ +import java.io.BufferedReader; +import java.io.IOException; +import java.io.InputStreamReader; +import java.util.*; + +public class TreeTraversal { + static class FastScanner { + StringTokenizer tok = new StringTokenizer(""); + BufferedReader in; + + FastScanner() { + in = new BufferedReader(new InputStreamReader(System.in)); + } + + String next() throws IOException { + while (!tok.hasMoreElements()) + tok = new StringTokenizer(in.readLine()); + return tok.nextToken(); + } + + int nextInt() throws IOException { + return Integer.parseInt(next()); + } + } + + public static class TreeOrders { + int n; + int[] key, left, right; + + void read() throws IOException { + FastScanner in = new FastScanner(); + n = in.nextInt(); + key = new int[n]; + left = new int[n]; + right = new int[n]; + for (int i = 0; i < n; i++) { + key[i] = in.nextInt(); + left[i] = in.nextInt(); + right[i] = in.nextInt(); + } + } + + List inOrder() { + Stack keyIndexStack = new Stack<>(); + ArrayList result = new ArrayList(); + // Finish the implementation + // You may need to add a new recursive method to do that + boolean walkLeft = true; + int currentIndex = 0; + keyIndexStack.push(currentIndex); + while (!keyIndexStack.empty() || right[currentIndex] != -1) { + if (walkLeft) { + if (left[currentIndex] != -1) { + currentIndex = left[currentIndex]; + keyIndexStack.push(currentIndex); + } else { + result.add(key[keyIndexStack.pop()]); + walkLeft = false; + } + } else { + if (right[currentIndex] != -1) { + currentIndex = right[currentIndex]; + keyIndexStack.push(currentIndex); + walkLeft = true; + } else { + if (!keyIndexStack.empty()) { + currentIndex = keyIndexStack.pop(); + result.add(key[currentIndex]); + } + } + } + } + return result; + } + + List preOrder() { + Stack keyIndexStack = new Stack<>(); + Queue keyIndexQueue = new LinkedList<>(); + ArrayList result = new ArrayList(); + // Finish the implementation + // You may need to add a new recursive method to do that + boolean walkLeft = true; + int currentIndex = 0; + keyIndexStack.push(currentIndex); + keyIndexQueue.add(currentIndex); + while (!keyIndexStack.empty() || right[currentIndex] != -1) { + if (walkLeft) { + if (left[currentIndex] != -1) { + currentIndex = left[currentIndex]; + keyIndexQueue.add(currentIndex); + keyIndexStack.push(currentIndex); + } else { + keyIndexStack.pop(); + walkLeft = false; + result.add(key[keyIndexQueue.remove()]); + } + } else { + if (right[currentIndex] != -1) { + currentIndex = right[currentIndex]; + keyIndexQueue.add(currentIndex); + keyIndexStack.push(currentIndex); + walkLeft = true; + } else { + if (!keyIndexStack.empty()) { + currentIndex = keyIndexStack.pop(); + result.add(key[keyIndexQueue.remove()]); + } + } + } + } + return result; + } + + List postOrder() { + Stack keyIndexStack = new Stack<>(); + ArrayList result = new ArrayList(); + // Finish the implementation + // You may need to add a new recursive method to do that + boolean walkLeft = true; + int currentIndex = 0; + keyIndexStack.push(currentIndex); + while (!keyIndexStack.empty() || right[currentIndex] != -1) { + if (walkLeft) { + if (left[currentIndex] != -1) { + currentIndex = left[currentIndex]; + keyIndexStack.push(currentIndex); + } else { + result.add(key[keyIndexStack.pop()]); + walkLeft = false; + } + } else { + if (right[currentIndex] != -1) { + currentIndex = right[currentIndex]; + keyIndexStack.push(currentIndex); + walkLeft = true; + } else { + if (!keyIndexStack.empty()) { + currentIndex = keyIndexStack.pop(); + result.add(key[currentIndex]); + } + } + } + } + return result; + } + } + + static public void main(String[] args) throws IOException { + new Thread(null, new Runnable() { + public void run() { + try { + new TreeTraversal().run(); + } catch (IOException e) { + } + } + }, "1", 1 << 26).start(); + } + + public void print(List x) { + for (Integer a : x) { + System.out.print(a + " "); + } + System.out.println(); + } + + public void run() throws IOException { + TreeOrders tree = new TreeOrders(); + tree.read(); + print(tree.inOrder()); + print(tree.preOrder()); + print(tree.postOrder()); + } +} diff --git a/src/test/TreeTraversalTest.java b/src/test/TreeTraversalTest.java new file mode 100644 index 0000000..336b86c --- /dev/null +++ b/src/test/TreeTraversalTest.java @@ -0,0 +1,60 @@ +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.*; + +class TreeTraversalTest { + @Test + void test() { + TreeTraversal.TreeOrders tt = new TreeTraversal.TreeOrders(); + tt.key = new int[]{4, 2, 5, 1, 3}; + tt.left = new int[]{1, 3, -1, -1, -1}; + tt.right = new int[]{2, 4, -1, -1, -1}; + + assertEquals(5, tt.inOrder().size()); + assertEquals(1, tt.inOrder().get(0)); + assertEquals(2, tt.inOrder().get(1)); + assertEquals(3, tt.inOrder().get(2)); + assertEquals(4, tt.inOrder().get(3)); + assertEquals(5, tt.inOrder().get(4)); + + assertEquals(5, tt.preOrder().size()); + assertEquals(4, tt.preOrder().get(0)); + assertEquals(2, tt.preOrder().get(1)); + assertEquals(1, tt.preOrder().get(2)); + assertEquals(3, tt.preOrder().get(3)); + assertEquals(5, tt.preOrder().get(4)); + } + + @Test + void test1() { + TreeTraversal.TreeOrders tt = new TreeTraversal.TreeOrders(); + tt.key = new int[]{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}; + tt.left = new int[]{7, -1, -1, 8, 3, -1, 1, 5, -1, -1}; + tt.right = new int[]{2, -1, 6, 9, -1, -1, -1, 4, -1, -1}; + + assertEquals(10, tt.inOrder().size()); + assertEquals(50, tt.inOrder().get(0)); + assertEquals(70, tt.inOrder().get(1)); + assertEquals(80, tt.inOrder().get(2)); + assertEquals(30, tt.inOrder().get(3)); + assertEquals(90, tt.inOrder().get(4)); + assertEquals(40, tt.inOrder().get(5)); + assertEquals(0, tt.inOrder().get(6)); + assertEquals(20, tt.inOrder().get(7)); + assertEquals(10, tt.inOrder().get(8)); + assertEquals(60, tt.inOrder().get(9)); + + assertEquals(10, tt.preOrder().size()); + assertEquals(0, tt.preOrder().get(0)); + assertEquals(70, tt.preOrder().get(1)); + assertEquals(50, tt.preOrder().get(2)); + assertEquals(40, tt.preOrder().get(3)); + assertEquals(30, tt.preOrder().get(4)); + assertEquals(80, tt.preOrder().get(5)); + assertEquals(90, tt.preOrder().get(6)); + assertEquals(20, tt.preOrder().get(7)); + assertEquals(60, tt.preOrder().get(8)); + assertEquals(10, tt.preOrder().get(9)); + } + +} \ No newline at end of file -- cgit v1.2.3