Uva Wellassa University

Faculty of Technological Studies

BICT Degree Program
ICT 143-2 Data Structures and Algorithms
Practical 4 – Tree Implementation

Tree Implementation
public class Node {
public int iData;
public double dData;
public Node leftChild; // left nod
public Node rightChild; // right node

public void diplayNode() {

System.out.print("{");
System.out.print(iData);
System.out.print("}");
System.out.println("\n");
}
}

Tree Class
class Tree {
public Node root;

public Tree() {
root = null;
}

public Node find(int key) {

Node current = root;
while (current.iData != key) {
if (key < current.iData)
current = current.leftChild;
else
current = current.rightChild;
if (current == null)
return null;
}
return current;
}

public void insert(int id) {

Node newnode = new Node();

1
 newnode.iData = id;
if (root == null) {
root = newnode;
} else {
Node current = root;
Node parent;
while (true) {
parent = current;
if (id < current.iData) {
current = current.leftChild;
if (current == null) {
parent.leftChild = newnode;
return;
}
} else {
current = current.rightChild;
if (current == null) {
parent.leftChild = newnode;
return;
}
}
}
}
}

public boolean delete(int key) {

Node current = root;
Node parent = root;
boolean isLeftChild = true;
while (current.iData != key) {
parent = current;
if (key < current.iData) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null)
return false;
}
if (current.leftChild == null && current.rightChild == null) {
if (current == root)
root = null;
else if (isLeftChild)
parent.leftChild = null;
else
parent.rightChild = null;

2
 } else if (current.rightChild == null)
if (current == root)
root = current.leftChild;
else if (isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
else if (current.leftChild == null)
if (current == root)
root = current.rightChild;
else if (isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.leftChild;
else {
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.leftChild = successor;
successor.leftChild = current.leftChild;
}
return true;
}

private Node getSuccessor(Node delNode) {

Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
if (successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}

public void traverse(int traverseType) {

switch (traverseType) {
case 1:
System.out.println("\n Preorder traversal");
preorder(root);
break;
case 2:

3
 System.out.println("\n Inorder traversal");
inorder(root);
break;
case 3:
System.out.println("\n postorder traversal");
postorder(root);
break;
}
System.out.println();
}

private void preorder(Node localRoot) {

if (localRoot != null) {
localRoot.diplayNode();
preorder(localRoot.leftChild);
preorder(localRoot.rightChild);
}
}

private void inorder(Node localRoot) {

if (localRoot != null) {
inorder(localRoot.leftChild);
localRoot.diplayNode();
inorder(localRoot.rightChild);
}
}

private void postorder(Node localRoot) {

if (localRoot != null) {
postorder(localRoot.leftChild);
postorder(localRoot.rightChild);
localRoot.diplayNode();
}
}

public void displaytree(Node t) {

if (t != null) {
displaytree(t.leftChild);
System.out.println(t.dData + t.iData);
displaytree(t.rightChild);
}
}
}

4
TreeTest class
import java.util.Scanner; // Import the Scanner class

class TreeTest {
public static void main(String[] args) {

Scanner scn = new Scanner(System.in); // Create a Scanner object

Tree thetree = new Tree();

thetree.insert(45);
thetree.insert(23);
thetree.insert(60);
thetree.traverse(1);
thetree.traverse(2);
thetree.traverse(3);
System.out.println(thetree.delete(45));
//System.out.println(thetree.find(40).iData);
while (true) {
System.out.println("Enter the option from");
System.out.println("1. Show, 2. insert, 3. find, 4. delete,or 5.
traverse");
int choice = scn.nextInt();
switch (choice) {
case 3:
System.out.println("Enter value to find:");
int value = scn.nextInt();

// Complete the rest of the code

}
}
}
}

Exercises 1
1. Study the given code and complete the main method.

5
Tree Implementation using recursion
class BinaryNode{
int data;
BinaryNode left;
BinaryNode right;
public BinaryNode(int d) {
data=d;
left=right=null;
}
public int getData(){
return data;
}
}

Binary Search Tree

class BinarySearchTree {
private BinaryNode root;

public BinarySearchTree() {
root = null;
}

public BinaryNode isEmpty() {

return root = null;
}

public BinaryNode search(BinaryNode t, int x) {

if (t == null) {
return null;
} else if (x > t.data) {
return search(t.left, x);
} else if (x < t.data) {
return search(t.right, x);
} else {
return t;
}
}

public void insert(int d) {

root = insertSubtree(root, d);
}

private BinaryNode insertSubtree(BinaryNode t, int d) {

if (t == null) {
t = new BinaryNode(d);
} else if (d < t.data) {
t.left = insertSubtree(t.left, d);

6
 } else if (d > t.data) {
t.right = insertSubtree(t.right, d);
}
return t;
}

private void visit(BinaryNode t) {

System.out.println((t.data));
}

public void preorder() {

preorderSubtree(root);
System.out.println();
}

private void preorderSubtree(BinaryNode t) {

if (t == null)
return;
visit(t);
preorderSubtree(t.left);
preorderSubtree(t.right);

public void inorder() {

inorderSubtree(root);
System.out.println();
}

private void inorderSubtree(BinaryNode t) {

if (t == null)
return;

inorderSubtree(t.left);
visit(t);
inorderSubtree(t.right);
}

public void postorder() {

postorderSubtree(root);
System.out.println();
}

private void postorderSubtree(BinaryNode t) {

if (t == null)
return;

7
 postorderSubtree(t.left);
postorderSubtree(t.right);
visit(t);
}

private BinaryNode findMin(BinaryNode t) {

if (t == null) {
return null;
} else if (t.left == null) {
return t;
} else
return findMin(t.left);
}

public void delete(int x) {

root = deleteSubtree(root, x);
}

private BinaryNode deleteSubtree(BinaryNode t, int x) {

if (t == null)
return null;
if (x < t.data) {
t.left = deleteSubtree(t.left, x);
} else if (x > t.data) {
t.right = deleteSubtree(t.right, x);
} else if (t.left != null && t.right != null) {
t.data = findMin(t.right).data;
t.right = deleteSubtree(t.right, t.data);
} else
t = (t.left != null) ? t.left : t.right;
return t;
}

public int size() {

return sizeSubtree(root);
}

private int sizeSubtree(BinaryNode t) {

if (t == null)
return 0;
return sizeSubtree(t.left) + sizeSubtree(t.right);
}

public int height() {

return heightSubtree(root);
}

private int heightSubtree(BinaryNode t) {

8
 if (t == null)
return -1;
int h = heightSubtree(t.left);
int k = heightSubtree(t.right);
return (h > k) ? h + 1 : k + 1;
}
}

Exercise 2
1. Study the given code and write the main method.
2. Insert 45, 23, 60, 20, 18 into the binary search tree.
3. Print preorder traversal.
4. Delete 45.
5. Print preorder, postorder and inorder traversals.
6. Print height of the binary tree.