Skip to content

Commit 7b6aa8f

Browse files
BIO2CSBIO2CS
committed
Adding Tree Traversal APIs Using Threaded Tree
1 parent fbbb976 commit 7b6aa8f

File tree

3 files changed

+180
-71
lines changed

3 files changed

+180
-71
lines changed

‎BinarySearchTree/BST.java‎

Lines changed: 0 additions & 68 deletions
Original file line numberDiff line numberDiff line change
@@ -171,72 +171,4 @@ public void printTree() {
171171
}
172172
}
173173
}
174-
175-
private void printUtil(List<Integer> list, String traversalType) {
176-
System.out.println("Binary Search Tree Iterative " + traversalType + " Traversal");
177-
for (int d : list) {
178-
System.out.print(d + " ");
179-
}
180-
System.out.println();
181-
}
182-
183-
public void inorderTraversal() {
184-
List<Integer> list = new ArrayList<Integer>();
185-
Stack<TreeNode> stack = new Stack<TreeNode>();
186-
TreeNode runner = root;
187-
while (runner != null || !stack.isEmpty()) {
188-
if (runner != null) {
189-
stack.push(runner);
190-
runner = runner.left;
191-
}
192-
else {
193-
TreeNode top = stack.pop();
194-
list.add(top.key);
195-
runner = top.right;
196-
}
197-
}
198-
printUtil(list, "Inorder");
199-
}
200-
201-
public void preorderTraversal() {
202-
List<Integer> list = new ArrayList<Integer>();
203-
Stack<TreeNode> stack = new Stack<TreeNode>();
204-
TreeNode runner = root;
205-
while (runner != null || !stack.isEmpty()) {
206-
if (runner != null) {
207-
list.add(runner.key);
208-
if (runner.right != null) {
209-
stack.add(runner.right);
210-
}
211-
runner = runner.left;
212-
}
213-
else {
214-
runner = stack.pop();
215-
}
216-
}
217-
printUtil(list, "Preorder");
218-
}
219-
220-
public void postorderTraversal() {
221-
List<Integer> list = new ArrayList<Integer>();
222-
Stack<TreeNode> stack = new Stack<TreeNode>();
223-
TreeNode runner = root, pre = null;
224-
while (runner != null || !stack.isEmpty()) {
225-
if (runner != null) {
226-
stack.push(runner);
227-
runner = runner.left;
228-
}
229-
else {
230-
TreeNode top = stack.peek();
231-
if (top.right == null || top.right == pre) {
232-
list.add(top.key);
233-
pre = stack.pop();
234-
}
235-
else {
236-
runner = top.right;
237-
}
238-
}
239-
}
240-
printUtil(list, "Postorder");
241-
}
242174
}

‎BinarySearchTree/TestClient.java‎

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -18,9 +18,15 @@ public static void main(String[] args) {
1818
bst.insert(18);
1919
bst.insert(23);
2020

21-
bst.inorderTraversal();
22-
bst.preorderTraversal();
23-
bst.postorderTraversal();
21+
TreeTraversal tr = new TreeTraversal();
22+
tr.inorderTraversal(bst.root);
23+
tr.inorderWithTreadedTree(bst.root);
24+
System.out.println("#############################");
25+
tr.preorderTraversal(bst.root);
26+
tr.preorderWithThreadedTree(bst.root);
27+
System.out.println("#############################");
28+
tr.postorderTraversal(bst.root);
29+
tr.postorderWithTreadedTree(bst.root);
2430

2531
//bst.printTree();
2632

‎BinarySearchTree/TreeTraversal.java‎

Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
package BinarySearchTree;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
import java.util.Stack;
7+
8+
public class TreeTraversal {
9+
private void printUtil(List<Integer> list, String traversalType) {
10+
System.out.println("Binary Search Tree Iterative " + traversalType + " Traversal");
11+
for (int d : list) {
12+
System.out.print(d + " ");
13+
}
14+
System.out.println();
15+
}
16+
17+
public void inorderTraversal(TreeNode root) {
18+
List<Integer> list = new ArrayList<Integer>();
19+
Stack<TreeNode> stack = new Stack<TreeNode>();
20+
TreeNode runner = root;
21+
while (runner != null || !stack.isEmpty()) {
22+
if (runner != null) {
23+
stack.push(runner);
24+
runner = runner.left;
25+
}
26+
else {
27+
TreeNode top = stack.pop();
28+
list.add(top.key);
29+
runner = top.right;
30+
}
31+
}
32+
printUtil(list, "Inorder");
33+
}
34+
35+
public void preorderTraversal(TreeNode root) {
36+
List<Integer> list = new ArrayList<Integer>();
37+
Stack<TreeNode> stack = new Stack<TreeNode>();
38+
TreeNode runner = root;
39+
while (runner != null || !stack.isEmpty()) {
40+
if (runner != null) {
41+
list.add(runner.key);
42+
if (runner.right != null) {
43+
stack.add(runner.right);
44+
}
45+
runner = runner.left;
46+
}
47+
else {
48+
runner = stack.pop();
49+
}
50+
}
51+
printUtil(list, "Preorder");
52+
}
53+
54+
public void postorderTraversal(TreeNode root) {
55+
List<Integer> list = new ArrayList<Integer>();
56+
Stack<TreeNode> stack = new Stack<TreeNode>();
57+
TreeNode runner = root, pre = null;
58+
while (runner != null || !stack.isEmpty()) {
59+
if (runner != null) {
60+
stack.push(runner);
61+
runner = runner.left;
62+
}
63+
else {
64+
TreeNode top = stack.peek();
65+
if (top.right == null || top.right == pre) {
66+
list.add(top.key);
67+
pre = stack.pop();
68+
}
69+
else {
70+
runner = top.right;
71+
}
72+
}
73+
}
74+
printUtil(list, "Postorder");
75+
}
76+
77+
/**
78+
* Traversal using treaded tree: non-recursive, no-stack
79+
*/
80+
81+
public void inorderWithTreadedTree(TreeNode root) {
82+
List<Integer> list = new ArrayList<Integer>();
83+
TreeNode runner = root;
84+
while (runner != null) {
85+
if (runner.left == null) {
86+
list.add(runner.key);
87+
runner = runner.right;
88+
}
89+
else {
90+
TreeNode pre = runner.left;
91+
while (pre.right != null && pre.right != runner) {
92+
pre = pre.right;
93+
}
94+
if (pre.right == null) {
95+
pre.right = runner;
96+
runner = runner.left;
97+
}
98+
else {
99+
list.add(runner.key);
100+
runner = runner.right;
101+
pre.right = null;
102+
}
103+
}
104+
}
105+
printUtil(list, "Inorder Morris Traversal Using Treaded Tree");
106+
}
107+
108+
public void preorderWithThreadedTree(TreeNode root) {
109+
List<Integer> list = new ArrayList<Integer>();
110+
TreeNode runner = root;
111+
while (runner != null) {
112+
if (runner.left == null) {
113+
list.add(runner.key);
114+
runner = runner.right;
115+
}
116+
else {
117+
TreeNode pre = runner.left;
118+
while (pre.right != null && pre.right != runner) {
119+
pre = pre.right;
120+
}
121+
if (pre.right == null) {
122+
list.add(runner.key);
123+
pre.right = runner;
124+
runner = runner.left;
125+
}
126+
else {
127+
pre.right = null;
128+
runner = runner.right;
129+
}
130+
}
131+
}
132+
printUtil(list, "Preorder Morris Traversal Using Treaded Tree");
133+
}
134+
135+
public void postorderWithTreadedTree(TreeNode root) {
136+
List<Integer> list = new ArrayList<Integer>();
137+
TreeNode dummy = new TreeNode(0);
138+
dummy.left = root;
139+
TreeNode runner = dummy;
140+
while (runner != null) {
141+
if (runner.left == null) {
142+
runner = runner.right;
143+
}
144+
else {
145+
TreeNode pre = runner.left;
146+
while (pre.right != null && pre.right != runner) {
147+
pre = pre.right;
148+
}
149+
if (pre.right == null) {
150+
pre.right = runner;
151+
runner = runner.left;
152+
}
153+
else {
154+
List<Integer> subList = new ArrayList<Integer>();
155+
TreeNode temp = runner.left;
156+
while (temp != pre) {
157+
subList.add(temp.key);
158+
temp = temp.right;
159+
}
160+
subList.add(temp.key);
161+
Collections.reverse(subList);
162+
list.addAll(subList);
163+
pre.right = null;
164+
runner = runner.right;
165+
}
166+
}
167+
}
168+
dummy.left = null;
169+
printUtil(list, "Postorder Morris Traversal Using Treaded Tree");
170+
}
171+
}

0 commit comments

Comments
 (0)