-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBidirectionalBinaryTree.java
More file actions
163 lines (143 loc) · 3.34 KB
/
Copy pathBidirectionalBinaryTree.java
File metadata and controls
163 lines (143 loc) · 3.34 KB
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
151
152
153
154
155
156
157
158
159
160
161
162
package partof;
public class BidirectionalBinaryTree<T extends Comparable<T>> {
protected Node<T> root = null;
private static class Node<T> {
private T value;
private Node<T> left = null;
private Node<T> right = null;
private Node<T> previous = null;
/**
* build a node with no subtrees
* @param value to be stored
*/
private Node(T value) {
this.value = value;
}
/**
* build a node with param
* @param value to be stored
* @param left subtree for this node
* @param right subtree for this node
*/
private Node(T value, Node<T> left, Node<T> right, Node<T> previous) {
this.value = value;
this.left = left;
this.right = right;
this.previous = previous;
}
}// Node
/**
* add a value to the tree
* @param value
* @return boolean result of operation
*/
public boolean insert(T value){
return insert(root, value);
}
/**
* add a value to the tree
* @param node == root the subtree
* @param value to be stored
* @return boolean result of operation
*/
protected boolean insert(Node<T> node, T value) {
if (value == null)
return false;
if (node == null) {
root = new Node<T>(value);
return true;
}
if (value.compareTo(node.value) > 0)
if (node.left != null) {
return insert(node.left, value);
} else {
node.left = new Node<T>(value);
node.left.previous = node;
return true;
}
else if (value.compareTo(node.value) < 0)
if (node.right != null) {
return insert(node.right, value);
} else {
node.right = new Node<T>(value);
node.right.previous = node;
return true;
}
else
return false;
}
/**
* find a value in the tree
* @param key identifies the node value
* @return the node value if found, or null if not found
*/
public T get(T key) {
Node<T> node = root;
while (node != null) {
if (key.compareTo(node.value) == 0) {
return node.value;
} else if (key.compareTo(node.value) < 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}
/**
* find a value in the tree
* @param key that identifies the node
* @return the Node<T> if found by key, or null if not found
*/
protected Node<T> getNode(T key) {
Node<T> node = root;
while (node != null) {
if (key.compareTo(node.value) == 0) {
return node;
} else if (key.compareTo(node.value) < 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}
/**
*
* @param node to start reverse access
* @return string result of reverse process
*/
protected String toStringReverse(Node<T> node) {
if (node.previous == null) {
return "";
}
return node.previous.value.toString() + " "
+ toStringReverse(node.previous);
}
/**
* node is the root of the subtree to start represent
* @returns the string representation of the tree.
*/
protected String toString(Node<T> node) {
if (node == null) {
return "";
}
return node.value.toString() + " "
+ toString(node.left) + " "
+ toString(node.right);
}
/**
* @returns the string representation of the tree.
*/
public String toString() {
return toString(root);
}
/**
* reverse representation of branch (in the tree)
* @param value to start
* @returns the string representation .
*/
public String toString(T value) {
return toStringReverse(getNode(value));
}
}