Linked Queue
In contiguous storage (using arrays), queues were
harder to manipulate than were stacks. It causes
difficulties to handle full queues and empty queues.
It is for queues that linked storage really comes
into its own. The linked implementation has two
advantages over the array implementation: (1) it is
faster – locations for insertion and deletion are
same – at the back and at the front, and (2) it wastes no
space – removed nodes are deleted by the automatic
garbage collector process.
Linked queues are just as easy to handle as are
linked stacks. This section presents a queue
implementation which makes use of the singly linked
list. We keep two pointers, front and rear. The
operations of LinkedQueue class is given Program
21(b) and LinkedQueue class is tested in
Program 21(c).
Program 21(b): A LinkedQueue Class
public class LinkedQueue
{
class Node
{ Object
data;
Node next;
Node(Object
item) // constructor
{ data =
item; }
}
Node front,
rear;
int count;
public void
insert(Object item)
{
Node p = new
Node(item);
if(front ==
null) // queue is empty; insert first item
{ front =
rear = p;
rear.next =
null;
}
if(front ==
rear) // queue contains one item; insert second item
{ rear = p;
front.next =
rear;
rear.next =
null;
} 46 Lab
Manual Data Structures through Java
else // queue
contains 2 or more items
{ rear.next =
p; // old rear.next refers to p
rear = p; //
new rear refers to p
rear.next =
null;
}
count++; //
increment queue size
}
public Object
remove()
{
if(isEmpty())
{
System.out.println("Q is empty"); return null; }
Object item =
front.data;
front =
front.next;
count--; //
decrement queue size
return item;
}
public
boolean isEmpty()
{ return
(front == null); }
public Object
peek()
{ return
front.data; }
public int
size()
{ return
count; }
public void
display()
{ Node p =
front;
System.out.print("Linked Q: ");
if(p == null)
System.out.println("empty");
while( p !=
null )
{
System.out.print(p.data
+ " ");
p = p.next;
}
System.out.println();
}
}
Program 21(c): Testing LinkedQueue Class
class LinkedQueueDemo
{ public static void main(String[] args)
{
LinkedQueue q
= new LinkedQueue();
q.display();
q.insert('A');
q.insert('B');
q.insert('C');
q.insert('D');
q.display();
System.out.println("delete(): " +
q.remove());
q.display();
System.out.println("peek(): " +
q.peek());
q.insert('E');
q.insert('F');
4. Stacks and Queues
47
System.out.println("delete(): " +
q.remove());
q.display();
System.out.println("size(): " +
q.size());
}
}
Here is the
output of this program:
Linked Q:
empty
Linked Q: A B
C D
remove(): A
Linked Q: B C
D
peek(): B
remove(): B
Linked Q: C D
E F
size(): 4
Deque ADT
22. Write Java programs to implement the deque
(double ended queue) ADT using
(a) Array
(b) Doubly linked list.
A deque is a double-ended queue. You can insert
items at either end and delete them from either end.
Methods are addFirst(), addLast(), removeFirst() and
removeLast().
If you restrict yourself to addFirst() and
removeFirst() (or their equivalents on the right),
then the deque acts like a stack. If you restrict
yourself to addFirst() and removeLast() (or the
opposite pair), then it acts like a queue.
A deque
provides a more versatile data structure than either a stack or a queue, and is
sometimes
used in container class libraries to serve both
purposes. However, it is not used as often as stacks and
queues.
The deque is
maintained by either an array or linked list with pointers first and last which
point to the two ends of the deque. Such a structure
is represented by the following figure.
first last
Insertion
Deletion
Deletion
Insertion
The methods of deque ADT are as follows:
addFirst(Object) Inserts an item at the left side of
deque.
addLast(Object) Inserts an item at the right side of
deque.
removeFirst() Deletes an item from the left of
deque.
removeLast() Deletes an item from the right of
deque.
getFirst() Returns an item from the left, without deleting
the item.
getLast() Returns an item from right, without
deleting the item.
size() Returns the current number of items in the
deque.
isEmpty() Returns true, if deque is empty else
returns false. 48 Lab Manual Data Structures through Java
ArrayDeque
Program 22(a) is an array implementation of
ArrayDeque class and it is tested in Program 22(b).
Program 22(a): An ArrayDeque Class
public class ArrayDeque
{
private int
maxSize;
private
Object[] que;
private int
first;
private int
last;
private int count;
// current number of items in deque
public
ArrayDeque(int s) // constructor
{ maxSize =
s;
que = new
Object[maxSize];
first = last
= -1;
count = 0;
}
public void
addLast(Object item)
{ if(count ==
maxSize)
{
System.out.println("Deque is full"); return; }
last =
(last+1) % maxSize;
que[last] =
item;
if(first ==
-1 && last == 0) first = 0;
count++;
}
public Object
removeLast()
{ if(count ==
0)
{
System.out.println("Deque is empty"); return(' ');}
Object item =
que[last];
que[last] = ‘
’;
if(last >
0) last = (last-1) % maxSize;
count--;
if(count ==
0) first = last = -1;
return(item);
}
public void
addFirst(Object item)
{ if(count ==
maxSize)
{
System.out.println("Deque is full"); return; }
if(first >
0) first = (first-1) % maxSize;
else if(first
== 0) first = maxSize-1;
que[first] =
item;
count++;
}
public Object
removeFirst()
{ if(count ==
0)
{
System.out.println("Deque is empty");
return(' ');
}
Object item =
que[first];
que[first] =
‘ ’;
if(first == maxSize-1)
first = 0; 4. Stacks and Queues
49
else first =
(first+1) % maxSize;
count--;
if(count ==
0) first = last = -1;
return(item);
}
void
display()
{
System.out.println("----------------------------");
System.out.print("first:"+first +
", last:"+ last);
System.out.println(", count: " +
count);
System.out.println(" 0 1 2 3 4 5");
System.out.print("Deque: ");
for( int i=0;
i<maxSize; i++ )
System.out.print(que[i]+ " ");
System.out.println("\n----------------------------");
}
public
boolean isEmpty() // true if queue is empty
{ return
(count == 0); }
public
boolean isFull() // true if queue is full
{ return
(count == maxSize); }
}
Program 22(b): Testing ArrayDeque Class
class ArrayDequeDemo
{ public static void main(String[] args)
{ ArrayDeque
q = new ArrayDeque(6); // queue holds a max of 6 items
q.insertLast('A'); /* (a) */
q.insertLast('B');
q.insertLast('C');
q.insertLast('D');
System.out.println("deleteFirst():"+q.deleteFirst());
q.display();
q.insertLast('E'); /* (b) */
q.display();
/* (c) */
System.out.println("deleteLast():"+q.deleteLast());
System.out.println("deleteLast():"+q.deleteLast());
q.display();
q.insertFirst('P'); q.insertFirst('Q'); /* (d)
*/
q.insertFirst('R'); q.display();
q.deleteFirst(); q.display(); /* (e) */
q.insertFirst('X'); q.display(); /* (f) */
q.insertLast('Y'); q.display(); /* (g) */
q.insertLast('Z'); q.display(); /* (h) */
}
}
Output of
this program is as follows:
deleteFirst(): A
----------------------------
first:1, last:3, count: 3
0 1 2 3 4 5
50 Lab Manual Data Structures through Java
Deque: B C D
----------------------------
first:1, last:4, count: 4
0 1 2 3 4 5
Deque: B C D E
----------------------------
deleteLast(): E
deleteLast(): D
----------------------------
first:1, last:2, count: 2
0 1 2 3 4 5
Deque: B C
----------------------------
first:4, last:2, count: 5
0 1 2 3 4 5
Deque: P B C R Q
----------------------------
first:5, last:2, count: 4
0 1 2 3 4 5
Deque: P B C Q
----------------------------
first:4, last:2, count: 5
0 1 2 3 4 5
Deque: P B C X Q
----------------------------
first:4, last:3, count: 6
0 1 2 3 4 5
Deque: P B C Y X Q
----------------------------
Deque is full
----------------------------
first:4, last:3, count: 6
0 1 2 3 4 5
Deque: P B C Y X Q
----------------------------
Linked Deque
A deque is implemented by using a doubly linked list
with references to first and last. Following
figure illustrates the linked deque operations. Each
node of the doubly linked list contains three fields:
data, prev and next. The fields prev and next refer
to the node itself. Program 22(c) implements
LinkedDeque class which is tested in Program 22(d).
Program 22(c): A LinkedDeque class
public class LinkedDeque
{
public class
DequeNode
{
DequeNode
prev;
Object data;
DequeNode
next;
DequeNode(
Object item ) // constructor
{
data = item;
} // prev
& next automatically refer to null
} 4. Stacks and Queues
51
private
DequeNode first, last;
private int
count;
public void
addFirst(Object item)
{ if(
isEmpty() )
first = last
= new DequeNode(item);
else
{ DequeNode
tmp = new DequeNode(item);
tmp.next =
first;
first.prev =
tmp;
first = tmp;
}
count++;
}
public void
addLast(Object item)
{
if( isEmpty()
)
first = last
= new DequeNode(item);
else
{ DequeNode
tmp = new DequeNode(item);
tmp.prev =
last;
last.next =
tmp;
last = tmp;
}
count++;
}
public Object
removeFirst()
{
if( isEmpty()
)
{
System.out.println("Deque is empty");
return null;
}
else
{ Object item
= first.data;
first =
first.next;
first.prev =
null;
count--;
return item;
}
}
public Object
removeLast()
{
if( isEmpty()
)
{
System.out.println("Deque is empty");
return null;
}
else
{ Object item
= last.data;
last =
last.prev;
last.next =
null;
count--;
return item;
}
}
public Object
getFirst()
{
if(
!isEmpty() ) return( first.data );
else return
null; 52 Lab Manual Data Structures through Java
}
public Object
getLast()
{
if(
!isEmpty() ) return( last.data );
else return
null;
}
public
boolean isEmpty()
{ return
(count == 0); }
public int
size()
{
return(count); }
public void
display()
{ DequeNode p
= first;
System.out.print("Deque: [ ");
while( p !=
null )
{
System.out.print( p.data + " " );
p = p.next;
}
System.out.println("]");
}
}
Program 22(d): Testing LinkedDeque Class
public class LinkedDequeDemo
{
public static
void main( String args[])
{
LinkedDeque
dq = new LinkedDeque();
System.out.println("removeFirst():"
+ dq.removeFirst());
dq.addFirst('A');
dq.addFirst('B');
dq.addFirst('C');
dq.display();
dq.addLast('D');
dq.addLast('E');
System.out.println("getFirst():" +
dq.getFirst());
System.out.println("getLast():" +
dq.getLast());
dq.display();
System.out.println("removeFirst():"+dq.removeFirst());
System.out.println("removeLast():"+
dq.removeLast());
dq.display();
System.out.println("size():" +
dq.size());
}
}
Output of this program is:
Deque is empty
removeFirst(): null
Deque: [ C B
A ]
getFirst(): C
getLast(): E
Deque: [ C B
A D E ]
removeFirst(): C 4. Stacks and Queues
53
removeLast():
E
Deque: [ B A
D ]
size(): 3
Priority Queue
23. Write a Java program to implement a priority
queue ADT.
In many situations, ordinary queues are inadequate,
as when FIFO arrangement has to be overruled
using some priority criteria.
The problem with a priority queue is in finding an
efficient implementation that allows relatively
fast insertion and deletion. Because items may arrive
randomly to the queue, there is no guarantee that
the items at front will be the most likely to be
removed and that the items inserted at the rear will be
the last items for deletion. Priority queues are
implemented by using (1) arrays, (2) linked lists, (3)
binary heaps
Linked Implementation of a Priority Queue
We can represent a priority queue as an ordered
linked list. The items of the queue are in ascending
order – the items of higher priority are at starting
of the list. Each list node consists of three fields:
data, priority number and next. A node of higher
priority is processed (removed) before any item of
lower priority. The items with the same priority are
deleted according to the order in which they were
added to the queue – that is, FIFO discipline. The
priority numbers work like this: the lower the
priority number, the higher the priority. The Node
class is declared as follows (data field is a String
type, priority number, prn is an int, and next
refers to the next node in the list):
class Node
{ data prn next
Node
String data;
int prn;
Node next;
}
The head indicates (or refers to) first node of the
list. The delete routine removes the head node
and makes the new head to refer to head next node.
Adding an
item to the priority queue is complicated than deleting a node from the queue,
because
we need to find the correct location to insert the
node.
The insert
method traverses the list until finding a node (call it N) whose priority
number is
greater than priority number of new node to be added.
Insert new node in front of N. If no such node is
found, insert new node after the end of the list
(that is, as a last node of the list). While traversing the
list, the object reference of preceding node of the
new node is to be saved.
LinkedPriorityQueue class implemented as a linked
list is given in Program 23(b), and it is tested
in Program 23(c). Node class is defined in Program
23(a).
Program 23(a): Linked Priority Queue Node Class
public class Node
{ String data; // data item
int prn; //
priority number (minimum has highest priority)
Node next; //
"next" refers to the next node
Node( String
str, int p ) // constructor
{ data = str;
54 Lab Manual Data Structures through Java
prn = p;
} //
"next" is automatically set to null
}
Program 23(b): LinkedPriorityQueue Class
class LinkedPriorityQueue
{
Node head; //
“head” refers to first node
public void
insert(String item, int pkey) // insert item after pkey
{
Node newNode
= new Node(item, pkey); // create new node
int k;
if( head ==
null ) k = 1;
else if(
newNode.prn < head.prn ) k = 2;
else k = 3;
switch( k )
{ case 1:
head = newNode; // Q is empty, add head node
head.next =
null;
break;
case 2: Node
oldHead = head; // add one item before head
head =
newNode;
newNode.next
= oldHead;
break;
case 3: Node
p = head; // add item before a node
Node prev =
p;
Node
nodeBefore = null;
while( p !=
null )
{
if(
newNode.prn < p.prn )
{ nodeBefore
= p;
break;
}
else
{ prev = p;
// save previous node of current node
p = p.next;
// move to next node
}
} // end of
while
newNode.next
= nodeBefore;
prev.next =
newNode;
} // end of
switch
} // end of
insert() method
public Node
delete()
{
if( isEmpty()
)
{
System.out.println("Queue is empty");
return null;
}
else
{ Node tmp =
head;
head =
head.next;
return tmp;
} 4. Stacks and Queues
55
}
public void
displayList()
{
Node p =
head; // assign address of head to p
System.out.print("\nQueue: ");
while( p !=
null ) // start at beginning of list until end of list
{
System.out.print(p.data+"(" +p.prn+
")" + " ");
p = p.next;
// move to next node
}
System.out.println();
}
public
boolean isEmpty() // true if list is empty
{ return
(head == null); }
public Node
peek() // get first item
{ return
head; }
}
Program 23(c): Testing of LinkedPriorityQueue Class
class LinkedPriorityQueueDemo
{
public static
void main(String[] args)
{
LinkedPriorityQueue pq = new
LinkedPriorityQueue(); // create new queue list
Node item;
pq.insert("Babu", 3);
pq.insert("Nitin", 2);
pq.insert("Laxmi", 2);
pq.insert("Kim", 1);
pq.insert("Jimmy", 3);
pq.displayList();
item =
pq.delete();
if( item !=
null )
System.out.println("delete():" +
item.data
+
"(" +item.prn+")");
pq.displayList();
pq.insert("Scot",
2);
pq.insert("Anu", 1);
pq.insert("Lehar", 4);
pq.displayList();
}
}
Output of
this program is:
Queue: Kim(1)
Nitin(2) Laxmi(2) Babu(3) Jimmy(3)
delete():
Kim(1)
Queue:
Nitin(2) Laxmi(2) Babu(3) Jimmy(3)
Queue: Anu(1)
Nitin(2) Laxmi(2) Scot(2) Babu(3) Jimmy(3) Lehar(4)Binary Trees
A binary tree is a special form of a tree. A binary
tree is more important and frequently used in various
applications of computer science. When binary trees
are in sorted form, they facilitate quick search,
insertion and deletion.
A binary tree is either empty, or it consists of a
node called the root together with two binary trees
called the left subtree or the right subtree of the
root. This definition is that of a mathematical
structure. To specify binary trees as an abstract
data type, we must state what operations can be
performed on binary trees.
Binary Tree Traversals
24. Write Java programs that use recursive and
non-recursive functions to traverse the given
binary tree in
(a) Preorder
(b) Inorder, and
(c) Postorder.
Java Program - Binary Tree
We now implement a Java program for the following
operations on binary trees:
• Representation of binary tree: a single array
represents the node data linearly – this array is the
input for building the binary tree.
• Linked implementation of binary tree in memory:
binary tree is being built by reading the node
data. In the process, the object reference of the
tree root is saved - this is very important to do any
further tree operations.
• Traversals: inorder, preorder and postorder
traversals are performed recursively and iteratively;
and their linear orders are printed.
The buildTree() method
This is a recursive method that builds a linked
binary tree. It uses input node data which is represented
as a linear array (null links are added to complete
the tree).
Array representation of a binary tree
E C G A D F H x B x x x x x x x x x x
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
E
C G
A D F H
0
1 2
x B x x
x x
x x x x
x x
3 4 5 6
7 8
9 10 11 12 13 14
18
x indicates null
15 16 17 5.
Binary Trees
57
The buildTree() method takes the index of the array
as an input parameter. Initially, the index is
0 (root node). The method calls recursively with
updated index – for left child, the index is
(2*index+1) and for right child, it is (2*index+2).
The routine in Java is as follows:
public Node buildTree( int index )
{ Node p =
null; // ‘p’ refers to current node
if(
tree[index] != null )
{ p = new
Node(tree[index]); // create a node from array data
// call
buildTree() to create a left node
p.left = buildTree(2*index+1);
// call buildTree() to create a right node
p.right =
buildTree(2*index+2);
}
return p;
}
The recursive
algorithms for tree traversals are simple and easy. The non-recursive
algorithms use
stack to temporarily hold the addresses of nodes for
further processing.
Given a
binary tree whose root node address is given by a reference variable root and
whose
structure is {left, data, right}. The left and right
are reference variables referring to left and right
subtrees respectively. We define another data
structure stack that is used to save node reference as the
tree is traversed. The stack is an array of nodes
that stores the node addresses of the tree. The reference
variable p denotes the current node in the tree.
The iterative
inorder and postorder traversals are straight forward, whereas the postorder
traversal
is complicated. In non-recursive postorder
traversal, we may have to save a node twice in two different
situations.
Program 24 implements the binary tree traversals
recursively and iteratively.
Program 24: Binary Tree Traversals
class Node
{ Object data;
Node left;
Node right;
Node( Object
d ) // constructor
{ data = d; }
}
class BinaryTree
{
Object
tree[];
int maxSize;
java.util.Stack<Node> stk = new
java.util.Stack<Node>();
BinaryTree(
Object a[], int n ) // constructor
{ maxSize =
n;
tree = new
Object[maxSize];
for( int i=0;
i<maxSize; i++ )
tree[i] =
a[i];
}
public Node
buildTree( int index )
{ Node p =
null;
if(
tree[index] != null )
{ p = new
Node(tree[index]); 58 Lab Manual Data Structures through Java
p.left =
buildTree(2*index+1);
p.right =
buildTree(2*index+2);
}
return p;
}
/* Recursive
methods - Binary tree traversals */
public void
inorder(Node p)
{
if( p != null
)
{
inorder(p.left);
System.out.print(p.data + " ");
inorder(p.right);
}
}
public void
preorder(Node p)
{
if( p != null
)
{
System.out.print(p.data + " ");
preorder(p.left);
preorder(p.right);
}
}
public void
postorder(Node p)
{
if( p != null
)
{
postorder(p.left);
postorder(p.right);
System.out.print(p.data + " ");
}
}
/*
Non-recursive methods - Binary tree traversals */
public void
preorderIterative(Node p)
{
if(p == null
)
{
System.out.println("Tree is empty");
return;
}
stk.push(p);
while(
!stk.isEmpty() )
{
p =
stk.pop();
if( p != null
)
{
System.out.print(p.data + " ");
stk.push(p.right);
stk.push(p.left);
}
}
}
public void
inorderIterative(Node p)
{
if(p == null
)
{
System.out.println("Tree is empty");
return; 5. Binary Trees
59
}
while(
!stk.isEmpty() || p != null )
{
if( p != null
)
{
stk.push(p); // push left-most path onto stack
p = p.left;
}
else
{
p =
stk.pop(); // assign popped node to p
System.out.print(p.data + " "); //
print node data
p = p.right;
// move p to right subtree
}
}
}
public void
postorderIterative(Node p)
{
if(p == null
)
{
System.out.println("Tree is empty");
return;
}
Node tmp = p;
while( p !=
null )
{
while( p.left
!= null )
{
stk.push(p);
p = p.left;
}
while( p !=
null && (p.right == null || p.right == tmp ))
{
System.out.print(p.data + " "); // print node data
tmp = p;
if(
stk.isEmpty() )
return;
p =
stk.pop();
}
stk.push(p);
p = p.right;
}
}
} // end of BinaryTree class
//////////////////////// BinaryTreeDemo.java
//////////////////////
class BinaryTreeDemo
{
public static
void main(String args[])
{
Object arr[]
= {'E', 'C', 'G', 'A', 'D', 'F', 'H',
null,'B',
null, null, null, null,
null, null,
null, null, null, null};
BinaryTree t
= new BinaryTree( arr, arr.length );
Node root =
t.buildTree(0); // buildTree() returns reference to root
System.out.print("\n Recursive Binary
Tree Traversals:");
System.out.print("\n inorder: ");
t.inorder(root); 60 Lab Manual Data Structures
through Java
System.out.print("\n preorder: ");
t.preorder(root);
System.out.print("\n
postorder: ");
t.postorder(root);
System.out.print("\n Non-recursive Binary
Tree Traversals:");
System.out.print("\n inorder: ");
t.inorderIterative(root);
System.out.print("\n preorder: ");
t.preorderIterative(root);
System.out.print("\n postorder: ");
t.postorderIterative(root);
}
}
Output of this binary tree program is:
Recursive Binary Tree Traversals:
inorder: A B
C D E F G H
preorder: E C
A B D G F H
postorder: B
A D C F H G E
Non-recursive
Binary Tree Traversals:
inorder: A B
C D E F G H
preorder: E C
A B D G F H
postorder: B
A D C F H G E
Level Order Traversal
25. Write a Java program that displays node values
in a level order traversal (Traverse the tree
one level at a time, starting at the root node) for
a binary tree.
Traverse a binary tree level by level. That is, the
root is visited first, then the immediate children of the
root (from left to right), then grandchildren of the
root (from left to right), and so on. The algorithm
uses a queue to keep track of the children of a node
until it is time to visit them. This algorithm is also
known as breadth-first traversal.
1. Initialize a queue.
2. Insert the root into the queue.
3. Repeat steps 4 to 7 until the queue is empty.
4. Delete the node from the queue.
5. Process the node being deleted.
6. If the left child of node exists (is not null),
insert it into the queue.
7. If the
right child of node exists (is not null), insert it into the queue 5. Binary Trees
61
Program 25: Level order traversal
class Node
{
Object data;
Node left;
Node right;
Node( Object
d ) // constructor
{ data = d; }
}
class BinaryTree
{ Object tree[];
int maxSize;
java.util.LinkedList<Node> que =
new
java.util.LinkedList<Node>();
BinaryTree(
Object a[], int n ) // constructor
{ maxSize =
n;
tree = new
Object[maxSize];
for( int i=0;
i<maxSize; i++ )
tree[i] =
a[i];
}
public Node
buildTree( int index )
{ Node p =
null;
if(
tree[index] != null )
{ p = new
Node(tree[index]);
p.left =
buildTree(2*index+1);
p.right =
buildTree(2*index+2);
}
return p;
}
public void
levelorder(Node p)
{
que.addLast(p);
while(
!que.isEmpty() )
{
p =
que.removeFirst();
System.out.print(p.data + " ");
if(p.left !=
null)
que.addLast(p.left);
if(p.right !=
null)
que.addLast(p.right);
}
}
} // end of BinaryTree class
//////////////////////// LevelOrderTraversal.java
//////////////////////
class LevelOrderTraversal
{
public static
void main(String args[])
{
Object arr[]
= {'E', 'C', 'G', 'A', 'D', 'F', 'H',
null,'B',
null, null, null, null,
null, null,
null, null, null, null};
BinaryTree t
= new BinaryTree( arr, arr.length );
Node root =
t.buildTree(0); // buildTree() returns reference to root 62 Lab Manual Data
Structures through Java
System.out.print("\n Level Order Tree
Traversal: ");
t.levelorder(root);
}
}
Output of this program is:
Level Order Tree Traversal: E C G A D F H B Search
Trees
26. Write a Java program that uses recursive
functions.
(a) To create a binary search tree.
(b) To count the number of leaf nodes.
(c) To copy the above binary search tree.
27. Write a Java program to perform the following
operations:
(a) Insert an element into a binary search tree.
(b) Delete an element from a binary search tree.
(c) Search for a key element in a binary search
tree.
Binary Search Tree
A binary search tree is a binary tree that is either
empty or in which every node contains a key and
satisfies the conditions:
(1) The key in the left child of a node (if it
exists) is less than the key in its parent node.
(2) The key in the right child of a node (if it
exists) is greater than the key in its parent node.
(3) The left and right subtrees of the root are
again binary search trees.
The first two properties describe the ordering
relative to the key in the root node, and that the third
property extends them to all nodes in the tree;
hence we can continue to use the recursive structure of
the binary tree. After we examine the root of the
tree, we shall move to either its left or right subtree,
and this subtree is again a binary search tree. Thus
we can use the same method again on this smaller
tree. This definition assumes that no duplicate keys
are permitted.
30
45
25
15
10 20
65
55
50 60
75
80
Program 26 & 27: Binary search tree operations
class BSTNode
{
int data;
BSTNode left;
BSTNode
right;
BSTNode( int
d ) // constructor
{ data = d; }
}
class BinarySearchTree
{ 64 Lab Manual Data Structures through Java
public
BSTNode insertTree(BSTNode p, int key) // create BST
{
if( p == null
)
p = new
BSTNode(key);
else if( key
< p.data)
p.left =
insertTree( p.left, key);
else p.right
= insertTree( p.right, key);
return p; //
return root
}
public
BSTNode search(BSTNode root, int key)
{
BSTNode p =
root; // initialize p with root
while( p !=
null )
{ if( key ==
p.data ) return p;
else if( key
< p.data ) p = p.left;
else p =
p.right;
}
return null;
}
public int
leafNodes(BSTNode p)
{
int count =
0;
if( p !=
null)
{ if((p.left
== null) && (p.right == null))
count = 1;
else
count = count
+ leafNodes(p.left)
+
leafNodes(p.right);
}
return count;
}
public
BSTNode deleteTree(BSTNode root, int key)
{
BSTNode p; //
refer to node to be deleted
BSTNode
parent = root; // refer to parent of node to be deleted
BSTNode
inorderSucc; //refer to inorder succ. of node to be deleted
if(root ==
null)
{
System.out.println("Tree is empty");
return null;
}
p = root; //
initialize p with root
/* find node
being deleted & its parent */
while( p !=
null && p.data != key)
{ parent = p;
if( key <
p.data) p = p.left;
else p =
p.right;
}
if( p == null
)
{
System.out.println("\n Node " + key + " not found for
deletion");
return null;
}
/* find
inorder successor of the node being deleted and its parent */ 6. Search Trees
65
if(p.left !=
null && p.right != null) // case-3
{ parent = p;
inorderSucc =
p.right;
while(inorderSucc.left != null)
{
parent =
inorderSucc;
inorderSucc =
inorderSucc.left;
}
p.data =
inorderSucc.data;
p =
inorderSucc;
}
if(p.left ==
null && p.right == null) // case-1
{
if(
parent.left == p ) parent.left = null;
else
parent.right = null;
}
if(p.left ==
null && p.right != null) // case-2(a)
{
if(parent.left == p) parent.left = p.right;
else
parent.right = p.right;
}
if(p.left !=
null && p.right == null) // case-2(b)
{
if(parent.left == p) parent.left = p.left;
else
parent.right = p.left;
}
return root;
}
public void
inorder(BSTNode p) // 'p' starts with root
{ if( p !=
null )
{
inorder(p.left);
System.out.print(p.data + " ");
inorder(p.right);
}
}
public void
preorder(BSTNode p)
{ if( p !=
null )
{
System.out.print(p.data + " ");
preorder(p.left);
preorder(p.right);
}
}
public void
postorder(BSTNode p)
{ if( p !=
null )
{
postorder(p.left);
postorder(p.right);
System.out.print(p.data + " ");
}
}
} // end of BinarySearchTree class
////////////////////// BinarySearchTreeDemo.java
////////////////////
class BinarySearchTreeDemo
{ public static void main(String args[])
{
int arr[] = {
45, 25, 15, 10, 20, 30, 65, 55, 50, 60, 75, 80 };
BinarySearchTree bst = new BinarySearchTree();
66 Lab Manual Data Structures through Java
BSTNode root
= null;
// build tree
by repeated insertions
for( int i =
0; i < arr.length; i++ )
root =
bst.insertTree( root, arr[i]);
BSTNode root2
= root; // copy BST
int key = 66;
BSTNode item
= bst.search(root2, key);
if( item !=
null )
System.out.print("\n item found: " +
item.data);
else
System.out.print("\n Node " + key + " not found");
System.out.print("\n Number of leaf
nodes: " + bst.leafNodes(root));
System.out.print("\n Inorder: ");
bst.inorder(root);
System.out.print("\n Preorder: ");
bst.preorder(root);
System.out.print("\n Postorder: ");
bst.postorder(root);
key = 55; //
delete 55
bst.deleteTree(root, key);
System.out.print("\n Inorder, after
deletion of " + key + ": ");
bst.inorder(root);
key = 44; //
insert 44
bst.insertTree(root, key);
System.out.print("\n Inorder, after
insertion of " + key + ": ");
bst.inorder(root);
}
}
Output of this program is as follows:
Node 66 not found
Number of
leaf nodes: 6
Inorder: 10
15 20 25 30 45 50 55 60 65 75 80
Preorder: 45
25 15 10 20 30 65 55 50 60 75 80
Postorder: 10
20 15 30 25 50 60 55 80 75 65 45
Inorder,
after deletion of 55: 10 15 20 25 30 45 50 60 65 75 80
Inorder,
after insertion of 44: 10 15 20 25 30 44 45 50 60 65 75 80
No comments:
Post a Comment