7 Replies Latest reply: Oct 2, 2008 1:46 AM by 800282 RSS

    How to extend  breadth first Search for Binary Tree to any kind of Tree??

    756081
      Dear Friends,
      I am thinking a problem, How to extend breadth first Search for Binary Tree to any kind of Tree?? ie each node has more than 2 leaves such as 1, 2,3,4 or any,

      I have following code to successfully apply for breadth first Search in Binary Tree as follows,
      package a.border;
      
      
      import java.util.ArrayList;
      import java.util.LinkedList;
      
      public class Tree
          {
      
          int root;
          Tree left;
          Tree right;
          static ArrayList<Integer> list = new ArrayList<Integer>();
          static ArrayList<Tree> treeList = new ArrayList<Tree>();
          private static LinkedList<Tree> queue = new LinkedList<Tree>();
      
          /** 
           * 
           * @param root root value
           * @param left left node
           * @param right right node
           */
          public Tree(int root, Tree left, Tree right)
              {
              this.root = root;
              this.left = left;
              this.right = right;
              }
      
          /** Creates a new instance of Tree
           * You really should know what this does...
           * 
           * @param root 
           */
          public Tree(int root)
              {
              this.root = root;
              this.left = null;
              this.right = null;
              }
      
          /**
           * Simply runs a basic left then right traversal.
           */
          public void basicTraversal()
              {
              //Check if we can go left
              if (left != null)
                  {
                  left.basicTraversal();
                  }
      
              //Add the root
              list.add(root);
      
              //Check if we can go right
              if (right != null)
                  {
                  right.basicTraversal();
                  }
             }
      
          public ArrayList<Integer> getBreadthTraversal(ArrayList<Integer> list)
              {
              
              //Add the root to the arraylist, we know it is always the first entry.
              list.add(root);
      
              //Basically we add the first set of nodes into the queue for
              //traversing.
              
              //Query if left exists
              if (left != null)
                  {
                  //Then add the node into the tree for traversing later
                  queue.add(left);
                  }
              //Same for right
              if (right != null)
                  {
                  queue.add(right);
                  }
      
              //Then we call the traverse method to do the rest of the work
              return traverse(list);
              }
      
          private ArrayList<Integer> traverse(ArrayList<Integer> list)
              {
              //Keep traversing until we run out of people
              while (!queue.isEmpty())
                  {
             
                  Tree p = queue.remove();
                  
                  
                  //Check if it has any subnodes
                  if (p.left != null)
                      {
                      //Add the subnode to the back of the queue
                      queue.add(p.left);
                      }
      
                  //Same for left
                  if (p.right != null)
                      {
                      //Same here, no queue jumping!
                      queue.add(p.right);
                      }
      
                  //Append to the ArrayList
                  list.add(p.root);
                  }
              
              //And return
              return list;
              }
      
          /**
           * Makes a tree and runs some operations
           * @param args
           */
          public static void main(String[] args)
              {
              /* 
               *                             4
               *                           /   \ 
               *                          /     \
               *          t =           2       6
               *                        / \      / \ 
               *                      1   3    5   7
               */
      
              Tree leaf6 = new Tree(1);
              Tree leaf7 = new Tree(3);
              Tree leaf8 = new Tree(5);
              Tree leaf9 = new Tree(7);
              Tree t4 = new Tree(2, leaf6, leaf7);
              Tree t5 = new Tree(6, leaf8, leaf9);
              Tree t = new Tree(4, t4, t5);
              t.basicTraversal();
              System.out.println("Here is basicTraversal ="+list.toString());
      
              list.clear();
      
              t.getBreadthTraversal(list);
      
              System.out.println("getBreadthTraversal= " +list.toString());
      
              list.clear();
      
              }
          }
      Can Guru help how to update to any kind of tree??


      here this code is for the tree like:
             
      
       /* 
               *                             4
               *                           /   \ 
               *                          /     \
               *          t =           2       6
               *                        / \      / \ 
               *                      1   3    5   7
               */
      But i hope the new code can handle tree like:

              /* 
               *                             4
               *                           /   | \ 
               *                          /     |   \
               *          t =            2     8   6
               *                        / |  \    |    /| \ 
               *                      1 11  3 9   5 10  7
               */
      Thanks
        • 1. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree??
          800282
          sunnymanman wrote:
          Dear Friends,
          I am thinking a problem, How to extend breadth first Search for Binary Tree to any kind of Tree?? ...
          The answer is interfaces.

          What do all trees have in common? And what do all nodes in trees have in common?
          At least these things:
          interface Tree<T> {
              Node<T> getRoot();
          }
          
          interface Node<T> {
              T getData();
              List<Node<T>> getChildren();
          }
          Now write concrete classes implementing these interfaces. Let's start with a binary tree (nodes should have comparable items) and an n-tree:
          class BinaryTree<T extends Comparable<T>> implements Tree<T> {
              
              protected BTNode<T> root;
          
              public Node<T> getRoot() {
                  return root;
              }
              
              // ...
          }
          
          class BTNode<T> implements Node<T> {
              
              private T data;
              private Node<T> left, right;
              
              // ...
              
              public List<Node<T>> getChildren() {
                  List<Node<T>> children = new ArrayList<Node<T>>();
                  children.add(left);
                  children.add(right);
                  return children;
              }
              
              public T getData() {
                  return data;
              }
          }
          
          class NTree<T> implements Tree<T> {
             
              private NTNode<T> root;
          
              public Node<T> getRoot() {
                  return root;
              }
              
              // ...
          }
          
          class NTNode<T> implements Node<T> {
              
              private T data;
              private List<Node<T>> children;
              
              // ...
              
              public List<Node<T>> getChildren() {
                  return children;
              }
          
              public T getData() {
                  return data;
              }
          }
          Now with these classes, you can wite a more generic traversal class. Of course, every traversal class (breath first, depth first) will also have something in common: they return a "path" of nodes (if the 'goal' node/data is found). So, you can write an interface like this:
          interface Traverser<T> {
              List<Node<T>> traverse(T goal, Tree<T> tree);
          }
          And finally write an implementation for it:
          class BreathFirst<T> implements Traverser<T> {
          
              public List<Node<T>> traverse(T goal, Tree<T> tree) {
                  Node<T> start = tree.getRoot();
                  List<Node<T>> children = start.getChildren();
                  // your algorithm here
                  return null; // return your traversal
              }
          }
          ... which can be used to traverse any tree! Here's a small demo of how to use it:
          public class Test {
              public static void main(String[] args) {
                  Tree<Integer> binTree = new BinaryTree<Integer>();
                  // populate your binTree
                  
                  Tree<Integer> nTree = new NTree<Integer>();
                  // populate your nTree
                  
                  Traverser<Integer> bfTraverser = new BreathFirst<Integer>();
                  
                  // Look for integer 6 in binTree
                  System.out.println("bTree bfTraversal -> "+bfTraverser.traverse(6, binTree));
                  
                  // Look for integer 6 in nTree
                  System.out.println("bTree bfTraversal -> "+bfTraverser.traverse(6, nTree));
              }
          }
          Good luck!
          • 2. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree
            756081
            really great code. But not familiar with your implementation,
            how to do
            1
                    Tree<Integer> binTree = new BinaryTree<Integer>();
                    // populate your binTree
             
            How to populate my binTree?? can you teach me some sample??

            2
            class BreathFirst<T> implements Traverser<T> {
             
                public List<Node<T>> traverse(T goal, Tree<T> tree) {
                    Node<T> start = tree.getRoot();
                    List<Node<T>> children = start.getChildren();
                    // your algorithm here
                    return null; // return your traversal
                }
            }
            based on methods above in my sample, how to put my algorithm here, just do a simple demo.

            Thanks
            • 3. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree
              800364
              Just a small out-of-band remark:
              class BinaryTree<T extends Comparable<T>> implements Tree<T> {
              should be
              class BinaryTree<T extends Comparable<? super T>> implements Tree<T> {
              to allow for data classes whose instances are mutually comparable with instances of some superclass.

              That is... if we're using BinaryTree for implementing search trees... otherwise, there's no need to impose the Comparable constraint in the first place, is there?

              Edited by: nygaard on Oct 2, 2008 12:25 AM
              • 4. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree
                756081
                Dear prometheuzz:
                How to complete your code and test it?? I am really confused and stopped .
                Thanks
                • 5. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree
                  800282
                  sunnymanman wrote:
                  Dear prometheuzz:
                  How to complete your code and test it?? I am really confused and stopped .
                  Thanks
                  Add some more methods to the Tree interface (like add(T value), contains(T value), etc.) and implement them in your concrete classes (BinaryTree and NTree). I was under the impression you already knew how to perform basic operations on tree structures.
                  • 6. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree
                    800282
                    nygaard wrote:
                    ...
                    That is... if we're using BinaryTree for implementing search trees... otherwise, there's no need to impose the Comparable constraint in the first place, is there?
                    Correct: there is no order in a "regular" BT, in a BST there is a natural ordering. I should've named the class differently.
                    • 7. Re: How to extend  breadth first Search for Binary Tree to any kind of Tree
                      800282
                      sunnymanman wrote:
                      really great code. But not familiar with your implementation,
                      how to do
                      1
                           Tree<Integer> binTree = new BinaryTree<Integer>();
                      // populate your binTree
                      How to populate my binTree?? can you teach me some sample??

                      2
                      class BreathFirst<T> implements Traverser<T> {
                      
                      public List<Node<T>> traverse(T goal, Tree<T> tree) {
                      Node<T> start = tree.getRoot();
                      List<Node<T>> children = start.getChildren();
                      // your algorithm here
                      return null; // return your traversal
                      }
                      }
                      based on methods above in my sample, how to put my algorithm here, just do a simple demo.

                      Thanks
                      No sorry, if the sample code I posted is beyond you, then first make sure you master the basics of creating, and performing actions on tree-like structures before attempting to modify my sample. It is of no use to provide more "sample code" if you don't fully understand it (yet).

                      Best of luck.