Skip to Main Content

New to Java

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Breadth First Traversal of a Tree...

843785Feb 8 2009 — edited Feb 24 2009
Hi,

I want to make a program to print every node of a tree in a Breadth First Search (BFS)/Traversal. Since, BFS searches a tree in levels (i.e. 1st the root, then it's Children, then Grand Children etc from left to right), this is where I'm stuck. Here is my TreeNode class:
class TreeNode {
  Object element;
  TreeNode left;
  TreeNode right;

  public TreeNode(Object o) {
    element = o;
  }
}
Each node has a reference to its Children nodes etc. Here is how my tree looks like. Mine is similar to this: http://www.codeproject.com/KB/vb/SimpleBTree.aspx

All the lectures I have read in the net are talking about Queue, but my problem is reading the tree in BFS Traversal order. It's almost 4 days I'm trying to solve this probelm, but can't come up with something. Any help is greatly appreciated.

Here is my Binary Tree class:
 public class BinaryTree {
     private TreeNode root;
     private int size = 0;

     /** Create a default binary tree */
     public BinaryTree() {
     }

     /** Create a binary tree from an array of objects */
    public BinaryTree(Object[] objects) {
      for (int i = 0; i < objects.length; i++)
        insert(objects);
}

/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(Object o) {
if (root == null)
root = new TreeNode(o); // Create a new root
else {
// Locate the parent node
TreeNode parent = null;
TreeNode current = root;
while (current != null)
if (((Comparable)o).compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (((Comparable)o).compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted

// Create the new node and attach it to the parent node
if (((Comparable)o).compareTo(parent.element) < 0)
parent.left = new TreeNode(o);
else
parent.right = new TreeNode(o);
}

size++;
return true; // Element inserted
}

/** Inorder traversal */
public void inorder() {
inorder(root);
}

/** Inorder traversal from a subtree */
private void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}

/** Postorder traversal */
public void postorder() {
postorder(root);
}

/** Postorder traversal from a subtree */
private void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}

/** Preorder traversal */
public void preorder() {
preorder(root);
}

/** Preorder traversal from a subtree */
private void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}

/** Inner class tree node */
private static class TreeNode {
Object element;
TreeNode left;
TreeNode right;

public TreeNode(Object o) {
element = o;
}
}

/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Search element o in this binary tree */
public boolean search(Object o){
TreeNode temp = root;

boolean found = false;
if(temp == null)
found = false;
else if(((Comparable)(temp.element)).compareTo(o) == 0 && temp != null)
found = true;
else if(((Comparable)temp.element).compareTo(o) > 0){
root = temp.left;
found = search(o);
}
else{
root = temp.right;
found = search(o);
}
return found;
}
/** Display the nodes in breadth-first traversal */
public void breadthFirstTraversal(){
TreeNode temp = root;
// TreeNode leftChild = temp.left;
// TreeNode rightChild = temp.right;

MyQueue s = new MyQueue();
s.enqueue(root);
// while (s.getSize() == 0){
System.out.println(s);
// }
}
// private void breadthFirstTraversal(TreeNode node){
//
// }
}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Mar 24 2009
Added on Feb 8 2009
37 comments
1,358 views