A binary search tree is a binary tree in which every node contains a key that satisfies following criteria:
Following diagram represents a binary search tree:
Following are three different kind of traversals:
If the numbers such as {20, 15, 200, 25, -5, 0, 100, 20, 12, 126, 1000, -150} are to be stored in a BinaryTree (represented by code below), following would get printed using different kind of traversal mechanism:
//Preorder traversal
20, 15, -5, -150, 0, 12, 200, 25, 20, 100, 126, 1000
// Inorder traversal
-150, -5, 0, 12, 15, 20, 20, 25, 100, 126, 200, 1000
//Postorder traversal
-150, 12, 0, -5, 15, 20, 126, 100, 25, 1000, 200, 20
Following is the code for creating binary tree that uses following BinaryTree class and traversals:
BinaryTree tree = new BinaryTree( 20 );
int[] nums = {15, 200, 25, -5, 0, 100, 20, 12, 126, 1000, -150};
for(int i : nums ) {
tree.addNode( i );
}
tree.traversePreOrder();
tree.traverseInOrder();
tree.traversePostOrder();
Following is the code for BinaryTree class:
public class BinaryTree {
private int data;
private BinaryTree left;
private BinaryTree right;
public BinaryTree(int num) {
this.data = num;
this.left = null;
this.right = null;
}
// As a convention, if the key to be inserted is less than the key of root node, then key is inserted in
// left sub-tree; If key is greater, it is inserted in right sub-tree. If it is equal, as a convention, it
// is inserted in right sub-tree
public void addNode(int num) {
if (num < this.data) {
if (this.left != null) {
this.left.addNode(num);
} else {
this.left = new BinaryTree(num);
}
} else {
if (this.right != null) {
this.right.addNode(num);
} else {
this.right = new BinaryTree(num);
}
}
}
// Visit the node first, then left and right sub-trees
public void traversePreOrder() {
System.out.println( this.data );
if( this.left != null ) {
this.left.traversePreOrder();
}
if( this.right != null ) {
this.right.traversePreOrder();
}
}
// Visit left sub-tree, then node and then, right sub-tree
public void traverseInOrder() {
if( this.left != null ) {
this.left.traverseInOrder();
}
System.out.println( this.data );
if( this.right != null ) {
this.right.traverseInOrder();
}
}
// Visit left sub-tree, then right sub-tree and then the node
public void traversePostOrder() {
if( this.left != null ) {
this.left.traversePostOrder();
}
if( this.right != null ) {
this.right.traversePostOrder();
}
System.out.println( this.data );
}
}
In recent years, artificial intelligence (AI) has evolved to include more sophisticated and capable agents,…
Adaptive learning helps in tailoring learning experiences to fit the unique needs of each student.…
With the increasing demand for more powerful machine learning (ML) systems that can handle diverse…
Anxiety is a common mental health condition that affects millions of people around the world.…
In machine learning, confounder features or variables can significantly affect the accuracy and validity of…
Last updated: 26 Sept, 2024 Credit card fraud detection is a major concern for credit…