Binary Tree in Java

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 {  
  2. public Node parentElement; // parent element of the node
  3. public Node leftElement; // left child element of the node
  4. public Node rightElement; // right child element of the node
  5. public String value; // the value of the node
  6. }  
  7. public class TestNode {  
  8. public static void main(String args[]) {  
  9. //String sentence = “The fox is jump over that fence”;
  10.         String sentence = “The three fox are jump over that fence”;  
  11. // Break each word into array
  12.         String word[] = sentence.split(” “);  
  13. // Initialize the main tree
  14.         Node node = new Node();  
  15. // SetTree
  16. for(int i=0; i<WORD.LENGTH; {<br i++) />  
  17. if(i == 0) {  
  18.                 node.value = word[i];  
  19.                 node.parentElement = null;  
  20.             } else
  21.                 setNode(node, word[i]);  
  22.         }  
  23. // GetTree
  24.         System.out.println(“Demonstration of Mathematic for Computing: Tree”);  
  25.         System.out.println(“Sentence: ” + sentence);  
  26.         System.out.println(“Height of tree: ” + getNodeHeight(node));  
  27.         System.out.println(“Leaf: ” + getLeaf(node));  
  28.         System.out.println(“Parent of jump: ” + getParent(node, getNode(node, “jump”)).value);  
  29.         System.out.println(“Parent of fence: ” + getParent(node, getNode(node, “fence”)).value);  
  30.         System.out.println(“Height of sub-tree on fox: ” + getNodeHeight(getNode(node, “fox”)));  
  31.     }  
  32. // Set the structure of the tree on each node
  33. // @param Tree of node, word (value)
  34. public static void setNode(Node node, String word) {  
  35.         Node childNode;  
  36. if(node.value != null) {  
  37.             childNode = new Node();  
  38.             childNode.parentElement = node;  
  39.             childNode.value = word;  
  40. // compare ignore case
  41.             word = word.toLowerCase();  
  42.             node.value = node.value.toLowerCase();  
  43. if(word.compareTo(node.value) == 0)  
  44. return; // if equal, break out of method
  45. else if(word.compareTo(node.value) < 0) {  
  46. if(node.leftElement != null)  
  47.                     setNode(node.leftElement, word);  
  48. else
  49.                     node.leftElement = childNode;  
  50.             } else {  
  51. if(node.rightElement != null)  
  52.                     setNode(node.rightElement, word);  
  53. else
  54.                     node.rightElement = childNode;  
  55.             }  
  56.         }  
  57.     }  
  58. // Get node by value
  59. // @param Tree of node, value
  60. // @return the node want to get
  61. public static Node getNode(Node node, String value) {  
  62.         Node targetNode = null;  
  63. if(value.equals(node.value))  
  64.             targetNode = node;  
  65. else {  
  66. // check if left or right got target, then only one target found only, strange problem, getParent also encountered, maybe not very good
  67. if(node.leftElement != null)  
  68.                targetNode = targetNode == null ? getNode(node.leftElement, value) : targetNode;  
  69. if(node.rightElement != null)  
  70.                targetNode = targetNode == null ? getNode(node.rightElement, value) : targetNode;  
  71.         }  
  72. return targetNode;  
  73.     }  
  74. // Get height of the tree
  75. // @param Tree node
  76. // @return height of tree
  77. public static int getNodeHeight(Node node) {  
  78. int height = 1;  
  79. int leftHeight = 0, rightHeight = 0;  
  80. if(node.leftElement == null && node.rightElement == null)  
  81. return height;  
  82. else {  
  83. if(node.leftElement != null)  
  84.                 leftHeight += getNodeHeight(node.leftElement);  
  85. if(node.rightElement != null)  
  86.                 rightHeight += getNodeHeight(node.rightElement);  
  87.         }  
  88. return height + Math.max(leftHeight, rightHeight);  
  89.     }  
  90. // Get number of leafs in the tree
  91. // @param Tree node
  92. // @return number of leaf
  93. public static int getLeaf(Node node) {  
  94. int leaf = 0;  
  95. if(node.leftElement == null && node.rightElement == null)  
  96. return 1;  
  97. else {  
  98. if(node.leftElement != null)  
  99.                 leaf += getLeaf(node.leftElement);  
  100. if(node.rightElement != null)  
  101. &
    nbsp;               leaf += getLeaf(node.rightElement);  

  102.         }  
  103. return leaf;  
  104.     }  
  105. // Get parent of node by value
  106. // @param Tree of node, child of node
  107. // @return the parent of node
  108. public static Node getParent(Node node, Node childNode) {  
  109. // found that node
  110.         Node parentNode = null;  
  111. if(node.value.equals(childNode.value))  
  112. return node.parentElement;  
  113. else {  
  114. if(node.leftElement != null)  
  115.                 parentNode = parentNode == null ? getParent(node.leftElement, childNode) : parentNode;  
  116. if(node.rightElement != null)  
  117.                 parentNode = parentNode == null ? getParent(node.rightElement, childNode) : parentNode;  
  118.          }       
  119. return parentNode;  
  120.     }  

Author: fyhao

Jebsen & Jessen Comms Singapore INTI University College Bsc (Hon) of Computer Science, Coventry University

Leave a Reply