A binary tree is a non-linear data structure. In a binary tree, each node can have a maximum of two children.
A binary tree in which its information is sorted in inorder way is a binary search tree (BST), meaning, the value of each node is greater than or equal to every value in its left subtree, and is less than every value in its right subtree.
The depth of a node is the number of edges in the path from the root to that node.
The height of a node is the number of edges in the longest path from that node to a leaf node.
The size of a tree is the count of the total number of nodes in it.
A binary tree is of degree 2 because it can have a maximum of two children.
A node with no successor is a leaf node.
The internal nodes are the ones with at least one successive node.
A line connecting a node to its successor is an edge. A sequence of continuous edges make a path.
Two nodes with the same parent are siblings.
A node with no parent is the root.
Every node other than the root can have exactly one parent.
A full binary tree is one in which each node can have either 0 or 2 children.
A complete binary tree is a full binary tree except at the deepest level of the tree.
The process of going through a tree and visiting each node at least once is known as tree traversal. The three standard ways of tree traversals are:
- Inorder traversal
a) Traverse the left subtree of root in inorder
b) Visit the root
c) Traverse the right subtree of root in inorder - Preorder traversal
a) Visit the root
b) Traverse the left subtree of root in preorder
c) Traverse the right subtree of root in preorder - Postorder traversal
a) Traverse the left subtree of root in postorder
b) Traverse the right subtree of root in postorder
c) Visit the root
The following Java program implements the following functionalities on a binary search:
- Insert a node
- Count the nodes
- Search for a node
- Delete a node
- Inorder traversal
- Preorder traversal
- Postorder traversal
import java.util.Scanner;
class Node{
Node left;
Node right;
int data;
public Node(){
left = null;
right = null;
data = 0;
}
public Node(int d){
data = d;
left = null;
right = null;
}
}
class BinaryTree{
Node root;
public BinaryTree(){
root = null;
}
public int countNodes(Node r){
if(r == null)
return 0;
return 1 + countNodes(r.left) + countNodes(r.right);
}
public boolean search(Node r, int d){
boolean found = false;
while(r != null && !found){
if(r.data == d){
found = true;
break;
}
else if(d < r.data)
r = r.left;
else
r = r.right;
}
return found;
}
public void inorder(Node r){
if(r != null){
inorder(r.left);
System.out.print(r.data + " ");
inorder(r.right);
}
}
public void preorder(Node r){
if(r != null){
System.out.print(r.data + " ");
preorder(r.left);
preorder(r.right);
}
}
public void postorder(Node r){
if(r != null){
postorder(r.left);
postorder(r.right);
System.out.print(r.data + " ");
}
}
public Node insert(Node n, int d){
if(n == null)
n = new Node(d);
else{
if(d <= n.data)
n.left = insert(n.left, d);
else
n.right = insert(n.right, d);
}
return n;
}
public Node delete(Node r, int d){
if(r == null)
return r;
if(d > r.data)
r.right = delete(r.right, d);
else if(d < r.data)
r.left = delete(r.left, d);
else{
if(r.left == null && r.right == null)
r = null;
else if(r.right != null){
r.data = successor(r);
r.right = delete(r.right, r.data);
}
else{
r.data = predecessor(r);
r.left = delete(r.left, r.data);
}
}
return r;
}
private int successor(Node r){
r = r.right;
while(r.left != null)
r = r.left;
return r.data;
}
private int predecessor(Node r){
r = r.left;
while(r.right != null)
r = r.right;
return r.data;
}
public static void main(String args[]){
Scanner in = new Scanner(System.in);
BinaryTree bt = new BinaryTree();
while(true){
System.out.println("1. Insert node");
System.out.println("2. Search node");
System.out.println("3. Count nodes");
System.out.println("4. Delete node");
System.out.println("5. Inorder traversal");
System.out.println("6. Preorder traversal");
System.out.println("7. Postorder traversal");
System.out.print("Enter your choice: ");
int choice = Integer.parseInt(in.nextLine());
switch(choice){
case 1:
System.out.print("Node to be inserted: ");
int d = Integer.parseInt(in.nextLine());
bt.root = bt.insert(bt.root, d);
break;
case 2:
System.out.print("Node to be searched: ");
d = Integer.parseInt(in.nextLine());
if(bt.search(bt.root, d))
System.out.println(d + " found!");
else
System.out.println(d + " not found.");
break;
case 3:
int c = bt.countNodes(bt.root);
System.out.println("Number of nodes: " + c);
break;
case 4:
System.out.println("Node to be deleted: ");
d = Integer.parseInt(in.nextLine());
bt.root = bt.delete(bt.root, d);
break;
case 5:
bt.inorder(bt.root);
System.out.println();
break;
case 6:
bt.preorder(bt.root);
System.out.println();
break;
case 7:
bt.postorder(bt.root);
System.out.println();
break;
default:
System.out.println("Bye!");
return;
}
}
}
}
Comments
Post a Comment