Category: Computer and IT

I have learnt binary tree in Mathematics Computing last two semester in universities. And after I have completed the double module of Java, I know a little knowledge of Object-oriented Programming, so as I have tried to build a Java program which using object-oriented concept to construct a binary tree in Java.

This is my source code which written by me, fyhao.

1. class Node {  
3. public Node parentElement; // parent element of the node
5. public Node leftElement; // left child element of the node
7. public Node rightElement; // right child element of the node
9. public String value; // the value of the node
11. }  
13. public class TestNode {  
15. public static void main(String args[]) {  
17. //String sentence = “The fox is jump over that fence”;
19.         String sentence = “The three fox are jump over that fence”;  
23. // Break each word into array
25.         String word[] = sentence.split(” “);  
29. // Initialize the main tree
31.         Node node = new Node();  
35. // SetTree
37. for(int i=0; i<WORD.LENGTH; {<br i++) />  
38. if(i == 0) {  
40.                 node.value = word[i];  
42.                 node.parentElement = null;  
44.             } else
46.                 setNode(node, word[i]);  
50.         }  
54. // GetTree
56.         System.out.println(“Demonstration of Mathematic for Computing: Tree”);  
58.         System.out.println(“Sentence: ” + sentence);  
60.         System.out.println(“Height of tree: ” + getNodeHeight(node));  
62.         System.out.println(“Leaf: ” + getLeaf(node));  
64.         System.out.println(“Parent of jump: ” + getParent(node, getNode(node, “jump”)).value);  
66.         System.out.println(“Parent of fence: ” + getParent(node, getNode(node, “fence”)).value);  
68.         System.out.println(“Height of sub-tree on fox: ” + getNodeHeight(getNode(node, “fox”)));  
70.     }  
74. // Set the structure of the tree on each node
76. // @param Tree of node, word (value)
78. public static void setNode(Node node, String word) {  
80.         Node childNode;  
82. if(node.value != null) {  
84.             childNode = new Node();  
86.             childNode.parentElement = node;  
88.             childNode.value = word;  
92. // compare ignore case
94.             word = word.toLowerCase();  
96.             node.value = node.value.toLowerCase();  
100. if(word.compareTo(node.value) == 0)  
102. return; // if equal, break out of method
104. else if(word.compareTo(node.value) < 0) {  
106. if(node.leftElement != null)  
108.                     setNode(node.leftElement, word);  
110. else
112.                     node.leftElement = childNode;  
116.             } else {  
118. if(node.rightElement != null)  
120.                     setNode(node.rightElement, word);  
122. else
124.                     node.rightElement = childNode;  
128.             }  
132.         }  
134.     }  
138. // Get node by value
140. // @param Tree of node, value
142. // @return the node want to get
144. public static Node getNode(Node node, String value) {  
146.         Node targetNode = null;  
148. if(value.equals(node.value))  
150.             targetNode = node;  
152. else {  
154. // check if left or right got target, then only one target found only, strange problem, getParent also encountered, maybe not very good
156. if(node.leftElement != null)  
158.                targetNode = targetNode == null ? getNode(node.leftElement, value) : targetNode;  
162. if(node.rightElement != null)  
164.                targetNode = targetNode == null ? getNode(node.rightElement, value) : targetNode;  
166.         }  
170. return targetNode;  
172.     }  
176. // Get height of the tree
178. // @param Tree node
180. // @return height of tree
182. public static int getNodeHeight(Node node) {  
184. int height = 1;  
186. int leftHeight = 0, rightHeight = 0;  
188. if(node.leftElement == null && node.rightElement == null)  
190. return height;  
192. else {  
194. if(node.leftElement != null)  
196.                 leftHeight += getNodeHeight(node.leftElement);  
200. if(node.rightElement != null)  
202.                 rightHeight += getNodeHeight(node.rightElement);  
206.         }  
210. return height + Math.max(leftHeight, rightHeight);  
212.     }  
216. // Get number of leafs in the tree
218. // @param Tree node
220. // @return number of leaf
222. public static int getLeaf(Node node) {  
224. int leaf = 0;  
226. if(node.leftElement == null && node.rightElement == null)  
228. return 1;  
230. else {  
232. if(node.leftElement != null)  
234.                 leaf += getLeaf(node.leftElement);  
238. if(node.rightElement != null)  
240. &
     nbsp;               leaf += getLeaf(node.rightElement);  

244.         }  
248. return leaf;  
250.     }  
254. // Get parent of node by value
256. // @param Tree of node, child of node
258. // @return the parent of node
260. public static Node getParent(Node node, Node childNode) {  
262. // found that node
264.         Node parentNode = null;  
268. if(node.value.equals(childNode.value))  
270. return node.parentElement;  
272. else {  
274. if(node.leftElement != null)  
276.                 parentNode = parentNode == null ? getParent(node.leftElement, childNode) : parentNode;  
280. if(node.rightElement != null)  
282.                 parentNode = parentNode == null ? getParent(node.rightElement, childNode) : parentNode;  
286.          }       
288. return parentNode;  
290.     }  
292. }