Say one starts from the root node (3) and wants to visit all the nodes to make record of all the elements. There are two most fundamental ways to do this: breadth-first search and depth-first search algorithms.
In the breadth-first search, the main idea is to explore the closest nodes from the starting node before moving any further. This is like how a very careful person would do in a maze. With the binary tree example above, the order of first-time visit to the nodes would be 3-1-4-1-3-5-2-9-6-9-5-8-5. This is as if we are scanning elements from left to right (breadth) before we get to move to the next depth.
On the contrary, the depth-first search would first scan elements from top to bottom (depth) before we get to move to the right (breadth). So, the first-time visit order would be 3-1-1-2-4-3-5-9-6-5-5-8-9. In fact, we can tweak this a bit to print in the ascending order, i.e., 1-1-2-3-3-4-5-5-5-6-8-9-9, which I will discuss in a moment.
To implement breadth-first search, it is the easiest to use a queue. Implementation in words would be something like:
1. Start from the root node
2. Print the current node number
3. If the current node has left child, enqueue the address of the left child node
4. If the current node has the right child, enqueue the address of the right child node
5. If there is nothing in the queue, exit.
6. Otherwise, dequeue the node address and move to that node
7. Go to step 2
The reason for using the queue structure is because it is first-in first-out (FIFO). That is, the order in which I save the data is preserved as I retrieve the saved data. The opposite would be last-in first-out (LIFO), which is implemented by a stack. With stack, the order in which I save the data is reversed as I retrieve the data. With stack, push/pop means to save/retrieve the data.
To implement depth-first search, we use a stack. Implementation is most easily done by recursive function that does the following:
function DFS (node)
1. Print the node number
2. If node has left child, call DFS (left child)
3. If node has right child, call DFS (right child)
Of course, we would start it by calling DFS (root), and it will print out 3-1-1-2-4-3-5-9-6-5-5-8-9. If, however, we want to print in the ascending order, we simply swap step 1 and 2 in the DFS function. That is, we first check for the left child, then print the node number, and then check the right child.
The reason we use recursive function here is because function calls are implemented by stack. Therefore, the recursive implementation is indeed making use of the stack structure. It is possible to implement it using the stack and not recursive function. In order to do this, we will need to store not only the node address but also where we are left off in the process.
Below are implementation files in Java. They may not be the best implementation, but they do the job well.
// Queue.java
public class Queue <T> {
/** construct
Queue
*/
Queue () {
enque_node = null;
deque_node = null;
}
/** insert data
into the queue
*
* @param data to be
queued
*/
public void enque (T data) {
if (enque_node == null) {
enque_node = new Node (data);
deque_node = enque_node;
return;
}
enque_node.next = new Node (data);
enque_node = enque_node.next;
if (deque_node == null)
deque_node = enque_node;
}
/** remove data
from the queue
*
* @return the first queued
data among remaining
*/
public T deque () {
if (deque_node == null) {
System.out.println ("Nothing in the
queue");
return null;
}
T val = deque_node.data;
deque_node = deque_node.next;
return val;
}
/** indicate
whether the queue is empty
*
* @return true if empty;
false if not
*/
public boolean isEmpty () {
return (deque_node == null) ? true : false;
}
private Node enque_node,
deque_node;
private class Node {
T data;
Node next;
/** constructor
*
* @param data to be
inserted
*/
Node (T data) {
this.data = data;
next = null;
}
}
}
// Stack.java
public class Stack <T> {
/** construct
Stack
*/
Stack () {
current_node = null;
}
/** insert data
into the stack
*
* @param data to be
stacked
*/
public void push (T data) {
if (current_node == null) {
current_node = new Node (data);
return;
}
current_node.next = new Node (data);
current_node.next.prev = current_node;
current_node = current_node.next;
}
/** remove data
from the stack
*
* @return the last stacked
data
*/
public T pop () {
if (current_node == null) {
System.out.println ("Nothing in the
stack");
return null;
}
T val = current_node.data;
current_node = current_node.prev;
return val;
}
/** indicate
whether the stack is empty
*
* @return true if empty;
false if not
*/
public boolean isEmpty () {
return (current_node == null) ? true : false;
}
private Node current_node;
private class Node {
T data;
Node next, prev;
/** constructor
*
* @param data to be
inserted
*/
Node (T data) {
this.data = data;
next = null;
prev = null;
}
}
}
// Tree.java
public class Tree
{
private static class Node
{
int data;
Node left;
Node right;
/** Node constructor that adds the data
*
* @param data to be
inserted
*/
Node (int data)
{
this.data = data;
left = null;
right = null;
}
}
private Node root;
/** Tree
constructor
*/
Tree ()
{
root = null;
}
/** insert a new data into the tree
* incapsulation method
*
* @param data to be
inserted
*/
public void insert (int data)
{
root = insert (root, data);
}
/** insert data implementation method
* in this version of binary tree, the data will be appended
* to the right tree if it is equal
*
* @param node is the
current node
* @param data to be
inserted
* @return the node in
which data is inserted
*/
private Node insert (Node
node, int data)
{
if (node == null)
node = new Node (data);
else if (data < node.data)
node.left = insert (node.left, data);
else // if (data >= node.data)
node.right = insert (node.right, data);
return node;
}
/** print out all the data using breadth first algorithm
* from left to right and top to bottom
* implemented by queue
*/
public void breadthFirstSearch () {
if (root == null) {
System.out.println ("Tree is empty");
return;
}
Queue <Node> queue = new Queue <Node> ();
queue.enque (root);
do {
Node node = queue.deque ();
System.out.print (node.data + " ");
if (node.left != null)
queue.enque (node.left);
if (node.right != null)
queue.enque (node.right);
} while (!queue.isEmpty ());
System.out.println ();
}
/** print out all
the data using depth first algorithm
* implemented using stack structure
* print the data in the ascending order
*/
public void depthFirstSearchUsingStack () {
if (root == null) {
System.out.println ("Tree is empty");
return;
}
/* There are 5 stages in the while loop below */
int stage = 1;
Stack <Node> node_stack = new Stack <Node> ();
/* if state_stack is true, then it needs to resume from
stage 2
* if stage_stack is false, then it needs to resume from stage 4 */
Stack <Boolean> state_stack = new Stack <Boolean> ();
Node node = root;
while (stage != 5) {
if (stage == 1) {
/* search for the left child */
if (node.left != null) {
node_stack.push (node);
node = node.left;
state_stack.push (true);
}
else {
stage = 2;
}
}
if (stage == 2) {
/* print out the current data */
System.out.print (node.data + " ");
stage = 3;
}
if (stage == 3) {
/* search for the right child */
if (node.right != null) {
node_stack.push (node);
node = node.right;
stage = 1;
state_stack.push (false);
}
else {
stage = 4;
}
}
if (stage == 4) {
if (node_stack.isEmpty ()) {
stage = 5;
}
else {
node = node_stack.pop ();
if (state_stack.pop ()) {
stage = 2;
}
else {
stage = 4;
}
}
}
}
System.out.println ();
}
/** print out all the data using
depth first algorithm
* this
is the encapsulation function
*/
public void depthFirstSearchUsingRecursion () {
if (root == null) {
System.out.println ("Tree is empty");
return;
}
depthFirstSearch (root);
System.out.println ();
}
/** actual
implementation fuction using recursion
*
* @param node is the
recursive root of the subtree
*/
private void depthFirstSearch (Node node) {
if (node.left != null)
depthFirstSearch (node.left);
System.out.print (node.data + " ");
if (node.right != null)
depthFirstSearch (node.right);
}
}
// Main.java
public class Main
{
/** main method
*
* @param args is the
argument strings passed from the user
*/
public static void main (String[]args)
{
Tree tree = new Tree ();
tree.insert (3);
tree.insert (1);
tree.insert (4);
tree.insert (1);
tree.insert (5);
tree.insert (9);
tree.insert (2);
tree.insert (6);
tree.insert (5);
tree.insert (3);
tree.insert (5);
tree.insert (8);
tree.insert (9);
tree.breadthFirstSearch ();
tree.depthFirstSearchUsingStack ();
tree.depthFirstSearchUsingRecursion ();
}
}
No comments:
Post a Comment