summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main/TreeTraversal.java173
-rw-r--r--src/test/TreeTraversalTest.java60
2 files changed, 233 insertions, 0 deletions
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<Integer> inOrder() {
+ Stack<Integer> keyIndexStack = new Stack<>();
+ ArrayList<Integer> result = new ArrayList<Integer>();
+ // 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<Integer> preOrder() {
+ Stack<Integer> keyIndexStack = new Stack<>();
+ Queue<Integer> keyIndexQueue = new LinkedList<>();
+ ArrayList<Integer> result = new ArrayList<Integer>();
+ // 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<Integer> postOrder() {
+ Stack<Integer> keyIndexStack = new Stack<>();
+ ArrayList<Integer> result = new ArrayList<Integer>();
+ // 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<Integer> 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 21:26:34 +0000