Create a Binary Search Tree in Java

A binary search tree is a node-based data structure, the whole idea of a binary search tree is to keep the data in sorted order so we can search the data in a little faster.There are three kinds of nodes are playing key role in this tree (Parent Node,Left Child Node & Right Child Node).The value of the left child node is always lesser than the value of the parent node, the same as the value of the right child node is always greater than the value of the parent node. Each parent node can have a link to one or two child nodes but not more than two child nodes.

[Download Source code]

BinaryTree.java
1 package info.algonuts;
2 import java.util.ArrayList;
3 import java.util.Arrays;
4 import java.util.Iterator;
5
6 class BinaryTreeNode {
7 int nodeValue;
8 BinaryTreeNode leftChildNode;
9 BinaryTreeNode rightChildNode;
10
11 public BinaryTreeNode(int nodeValue) {
12 this.nodeValue = nodeValue;
13 this.leftChildNode = null;
14 this.rightChildNode = null;
15 }
16
17 public void preorder() {
18 System.out.print(this.nodeValue+" ");
19 if(this.leftChildNode != null) {
20 this.leftChildNode.preorder();
21 }
22 if(this.rightChildNode != null) {
23 this.rightChildNode.preorder();
24 }
25 }
26
27 public void inorder() {
28 if(this.leftChildNode != null) {
29 this.leftChildNode.inorder();
30 }
31 System.out.print(this.nodeValue+" ");
32 if(this.rightChildNode != null) {
33 this.rightChildNode.inorder();
34 }
35 }
36
37 public void postorder() {
38 if(this.leftChildNode != null) {
39 this.leftChildNode.postorder();
40 }
41 if(this.rightChildNode != null) {
42 this.rightChildNode.postorder();
43 }
44 System.out.print(this.nodeValue+" ");
45 }
46 }
47
48 class BinaryTreeCompute {
49 private static BinaryTreeNode temp;
50 private static BinaryTreeNode newNode;
51 private static BinaryTreeNode headNode;
52
53 public static void setNodeValue(int nodeValue) {
54 newNode = new BinaryTreeNode(nodeValue);
55 temp = headNode;
56 if(temp != null)
57 { mapping(); }
58 else
59 { headNode = newNode; }
60 }
61
62 private static void mapping() {
63 if(newNode.nodeValue < temp.nodeValue) { //Check value of new Node is smaller than Parent Node
64 if(temp.leftChildNode == null)
65 { temp.leftChildNode = newNode; } //Assign new Node to leftChildNode of Parent Node
66 else
67 {
68 temp = temp.leftChildNode; //Parent Node is already having leftChildNode,so temp object reference variable is now pointing leftChildNode as Parent Node
69 mapping();
70 }
71 }
72 else
73 {
74 if(temp.rightChildNode == null)
75 { temp.rightChildNode = newNode; } //Assign new Node to rightChildNode of Parent Node
76 else
77 {
78 temp = temp.rightChildNode; //Parent Node is already having rightChildNode,so temp object reference variable is now pointing rightChildNode as Parent Node
79 mapping();
80 }
81 }
82 }
83
84 public static void preorder() {
85 if(headNode != null) {
86 System.out.println("Preorder Traversal:");
87 headNode.preorder();
88 System.out.println("\n");
89 }
90 }
91
92 public static void inorder() {
93 if(headNode != null) {
94 System.out.println("Inorder Traversal:");
95 headNode.inorder();
96 System.out.println("\n");
97 }
98 }
99
100 public static void postorder() {
101 if(headNode != null) {
102 System.out.println("Postorder Traversal:");
103 headNode.postorder();
104 System.out.println("\n");
105 }
106 }
107 }
108
109 public class BinaryTree {
110 //Entry Point
111 public static void main(String[] args) {
112 ArrayList <Integer> intList = new ArrayList <Integer>(Arrays.asList(50,2,5,78,90,20,4,6,98));
113 Iterator<Integer> ptr = intList.iterator();
114 while(ptr.hasNext())
115 { BinaryTreeCompute.setNodeValue(ptr.next()); }
116
117 BinaryTreeCompute.preorder();
118 BinaryTreeCompute.inorder();
119 BinaryTreeCompute.postorder();
120
121 }
122 }

0 Comments

Leave a Comment:

(Your email address will not be published. Required fields are marked *)

Name *

Email *

Message *