Results 1 to 5 of 5
  1. #1
    Meta is offline Member
    Join Date
    Mar 2010
    Posts
    78
    Rep Power
    0

    Default I need help for the love of god. Binayr tree

    how can i edit this program to make it accept a string of letters and output each letter as its own node down a tree?

    [Java] import java.io.*; import java.util.*; // for Stack class /////// - Pastebin.com

  2. #2
    Meta is offline Member
    Join Date
    Mar 2010
    Posts
    78
    Rep Power
    0

    Default

    if i put 'A' 'B', etc in the insert method, what do i have to change to make it actually be able to isnert characters?

  3. #3
    ozzyman's Avatar
    ozzyman is offline Senior Member
    Join Date
    Mar 2011
    Location
    London, UK
    Posts
    797
    Blog Entries
    2
    Rep Power
    4

    Default

    Next time paste the code here between [CODE] /CODE brackets and you might get faster results. I've done it for you this time:

    Java Code:
    44.   public void insert(int id, double dd)
    45.      {
    46.      Node newNode = new Node();    // make new node
    47.      newNode.iData = id;           // insert data
    48.      newNode.dData = dd;
    49.      if(root==null)                // no node in root
    50.         root = newNode;
    51.      else                          // root occupied
    52.         {
    53.         Node current = root;       // start at root
    54.         Node parent;
    55.         while(true)                // (exits internally)
    56.            {
    57.            parent = current;
    58.            if(id < current.iData)  // go left?
    59.               {
    60.               current = current.leftChild;
    61.               if(current == null)  // if end of the line,
    62.                  {                 // insert on left
    63.                  parent.leftChild = newNode;
    64.                  return;
    65.                  }
    66.               }  // end if go left
    67.            else                    // or go right?
    68.               {
    69.               current = current.rightChild;
    70.               if(current == null)  // if end of the line
    71.                  {                 // insert on right
    72.                  parent.rightChild = newNode;
    73.                  return;
    74.                  }
    75.               }  // end else go right
    76.            }  // end while
    77.         }  // end else not root
    78.      }  // end insert()

  4. #4
    Jodokus's Avatar
    Jodokus is offline Senior Member
    Join Date
    Jan 2011
    Location
    Amsterdam, the Netherlands
    Posts
    230
    Rep Power
    4

    Default

    First I'll complete the work of Ozzyman to make it a LSCEE (variation of SSCEE):
    Java Code:
    package tree;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class TreeApp {
    
    public static void main(String[] args) throws IOException
       {
       int value;
       Tree theTree = new Tree();
    
       theTree.insert(50, 1.5);
       theTree.insert(25, 1.2);
       theTree.insert(75, 1.7);
       theTree.insert(12, 1.5);
       theTree.insert(37, 1.2);
       theTree.insert(43, 1.7);
       theTree.insert(30, 1.5);
       theTree.insert(33, 1.2);
       theTree.insert(87, 1.7);
       theTree.insert(93, 1.5);
       theTree.insert(97, 1.5);
    
       while(true)
          {
          System.out.print("Enter first letter of show, ");
          System.out.print("insert, find, delete, or traverse: ");
          int choice = getChar();
          switch(choice)
             {
             case 's':
                theTree.displayTree();
                break;
             case 'i':
                System.out.print("Enter value to insert: ");
                value = getInt();
                theTree.insert(value, value + 0.9);
                break;
             case 'f':
                System.out.print("Enter value to find: ");
                value = getInt();
                Node found = theTree.find(value);
                if(found != null)
                   {
                   System.out.print("Found: ");
                   found.displayNode();
                   System.out.print("\n");
                   }
                else
                   System.out.print("Could not find ");
                   System.out.print(value + '\n');
                break;
             case 'd':
                System.out.print("Enter value to delete: ");
                value = getInt();
                boolean didDelete = theTree.delete(value);
                if(didDelete)
                   System.out.print("Deleted " + value + '\n');
                else
                   System.out.print("Could not delete ");
                   System.out.print(value + '\n');
                break;
             case 't':
                System.out.print("Enter type 1, 2 or 3: ");
                value = getInt();
                theTree.traverse(value);
                break;
             default:
                System.out.print("Invalid entry\n");
             }  // end switch
          }  // end while
       }  // end main()
    //-------------------------------------------------------------
    public static String getString() throws IOException
       {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
       }
    //-------------------------------------------------------------
    public static char getChar() throws IOException
       {
       String s = getString();
       return s.charAt(0);
       }
    //-------------------------------------------------------------
    public static int getInt() throws IOException
       {
       String s = getString();
       return Integer.parseInt(s);
       }
    //-------------------------------------------------------------
    }  // end class TreeApp

    Java Code:
    package tree;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Stack;
    
    public class Tree{
    private Node root;             // first node of tree
    
    //-------------------------------------------------------------
    public Tree()                  // constructor
       { root = null; }            // no nodes in tree yet
    //-------------------------------------------------------------
    public Node find(int key)      // find node with given key
       {                           // (assumes non-empty tree)
       Node current = root;               // start at root
       while(current.iData != key)        // while no match,
          {
          if(key < current.iData)         // go left?
             current = current.leftChild;
          else                            // or go right?
             current = current.rightChild;
          if(current == null)             // if no child,
             return null;                 // didn't find it
          }
       return current;                    // found it
       }  // end find()
    //-------------------------------------------------------------
    public void insert(int id, double dd)
       {
       Node newNode = new Node();    // make new node
       newNode.iData = id;           // insert data
       newNode.dData = dd;
       if(root==null)                // no node in root
          root = newNode;
       else                          // root occupied
          {
          Node current = root;       // start at root
          Node parent;
          while(true)                // (exits internally)
             {
             parent = current;
             if(id < current.iData)  // go left?
                {
                current = current.leftChild;
                if(current == null)  // if end of the line,
                   {                 // insert on left
                   parent.leftChild = newNode;
                   return;
                   }
                }  // end if go left
             else                    // or go right?
                {
                current = current.rightChild;
                if(current == null)  // if end of the line
                   {                 // insert on right
                   parent.rightChild = newNode;
                   return;
                   }
                }  // end else go right
             }  // end while
          }  // end else not root
       }  // end insert()
    //-------------------------------------------------------------
    public boolean delete(int key) // delete node with given key
       {                           // (assumes non-empty list)
       Node current = root;
       Node parent = root;
       boolean isLeftChild = true;
    
       while(current.iData != key)        // search for node
          {
          parent = current;
          if(key < current.iData)         // go left?
             {
             isLeftChild = true;
             current = current.leftChild;
             }
          else                            // or go right?
             {
             isLeftChild = false;
             current = current.rightChild;
             }
          if(current == null)             // end of the line,
             return false;                // didn't find it
          }  // end while
       // found node to delete
    
       // if no children, simply delete it
       if(current.leftChild==null &&
                                    current.rightChild==null)
          {
          if(current == root)             // if root,
             root = null;                 // tree is empty
          else if(isLeftChild)
             parent.leftChild = null;     // disconnect
          else                            // from parent
             parent.rightChild = null;
          }
    
       // if no right child, replace with left subtree
       else if(current.rightChild==null)
          if(current == root)
             root = current.leftChild;
          else if(isLeftChild)
             parent.leftChild = current.leftChild;
          else
             parent.rightChild = current.leftChild;
    
       // if no left child, replace with right subtree
       else if(current.leftChild==null)
          if(current == root)
             root = current.rightChild;
          else if(isLeftChild)
             parent.leftChild = current.rightChild;
          else
             parent.rightChild = current.rightChild;
    
       else  // two children, so replace with inorder successor
          {
          // get successor of node to delete (current)
          Node successor = getSuccessor(current);
    
          // connect parent of current to successor instead
          if(current == root)
             root = successor;
          else if(isLeftChild)
             parent.leftChild = successor;
          else
             parent.rightChild = successor;
    
          // connect successor to current's left child
          successor.leftChild = current.leftChild;
          }  // end else two children
       // (successor cannot have a left child)
       return true;                                // success
       }  // end delete()
    //-------------------------------------------------------------
    // returns node with next-highest value after delNode
    // goes to right child, then right child's left descendents
    private Node getSuccessor(Node delNode)
       {
       Node successorParent = delNode;
       Node successor = delNode;
       Node current = delNode.rightChild;   // go to right child
       while(current != null)               // until no more
          {                                 // left children,
          successorParent = successor;
          successor = current;
          current = current.leftChild;      // go to left child
          }
                                            // if successor not
       if(successor != delNode.rightChild)  // right child,
          {                                 // make connections
          successorParent.leftChild = successor.rightChild;
          successor.rightChild = delNode.rightChild;
          }
       return successor;
       }
    //-------------------------------------------------------------
    public void traverse(int traverseType)
       {
       switch(traverseType)
          {
          case 1: System.out.print("\nPreorder traversal: ");
                  preOrder(root);
                  break;
          case 2: System.out.print("\nInorder traversal:  ");
                  inOrder(root);
                  break;
          case 3: System.out.print("\nPostorder traversal: ");
                  postOrder(root);
                  break;
          }
       System.out.println();
       }
    //-------------------------------------------------------------
    private void preOrder(Node localRoot)
       {
       if(localRoot != null)
          {
          System.out.print(localRoot.iData + " ");
          preOrder(localRoot.leftChild);
          preOrder(localRoot.rightChild);
          }
       }
    //-------------------------------------------------------------
    private void inOrder(Node localRoot)
       {
       if(localRoot != null)
          {
          inOrder(localRoot.leftChild);
          System.out.print(localRoot.iData + " ");
          inOrder(localRoot.rightChild);
          }
       }
    //-------------------------------------------------------------
    private void postOrder(Node localRoot)
       {
       if(localRoot != null)
          {
          postOrder(localRoot.leftChild);
          postOrder(localRoot.rightChild);
          System.out.print(localRoot.iData + " ");
          }
       }
    //-------------------------------------------------------------
    public void displayTree()
       {
       Stack globalStack = new Stack();
       globalStack.push(root);
       int nBlanks = 32;
       boolean isRowEmpty = false;
       System.out.println(
       "......................................................");
       while(isRowEmpty==false)
          {
          Stack localStack = new Stack();
          isRowEmpty = true;
    
          for(int j=0; j<nBlanks; j++)
             System.out.print(' ');
    
          while(globalStack.isEmpty()==false)
             {
             Node temp = (Node)globalStack.pop();
             if(temp != null)
                {
                System.out.print(temp.iData);
                localStack.push(temp.leftChild);
                localStack.push(temp.rightChild);
    
                if(temp.leftChild != null ||
                                    temp.rightChild != null)
                   isRowEmpty = false;
                }
             else
                {
                System.out.print("--");
                localStack.push(null);
                localStack.push(null);
                }
             for(int j=0; j<nBlanks*2-2; j++)
                System.out.print(' ');
             }  // end while globalStack not empty
          System.out.println();
          nBlanks /= 2;
          while(localStack.isEmpty()==false)
             globalStack.push( localStack.pop() );
          }  // end while isRowEmpty is false
       System.out.println(
       "......................................................");
       }  // end displayTree()
    //-------------------------------------------------------------
    }  // end class Tree


    Java Code:
    package tree;
    
    import java.io.*;
    import java.util.*;               // for Stack class
    ////////////////////////////////////////////////////////////////
    public class Node
       {
       public int iData;              // data item (key)
       public double dData;           // data item
       public Node leftChild;         // this node's left child
       public Node rightChild;        // this node's right child
     
       public void displayNode()      // display ourself
          {
          System.out.print('{');
          System.out.print(iData);
          System.out.print(", ");
          System.out.print(dData);
          System.out.print("} ");
          }
       }  // end class Node

  5. #5
    Jodokus's Avatar
    Jodokus is offline Senior Member
    Join Date
    Jan 2011
    Location
    Amsterdam, the Netherlands
    Posts
    230
    Rep Power
    4

    Default

    Having done that, I don't see the problem: you use your double (dd) only to print it after the user choosing "f". I don't see it's any more difficult to print characters A,B then doubles.
    One remark: in the case-statement ( main() ) you need brackets {} around multiple statements in the else.

Similar Threads

  1. Please for the love of god help
    By Meta in forum New To Java
    Replies: 2
    Last Post: 03-11-2010, 08:54 AM
  2. In love with gui
    By fresh83 in forum New To Java
    Replies: 4
    Last Post: 12-27-2009, 10:35 AM
  3. For the people who love Calculus
    By tim in forum Forum Lobby
    Replies: 9
    Last Post: 12-01-2009, 01:53 PM
  4. I'm falling in love with java...
    By IndioDoido in forum Introductions
    Replies: 2
    Last Post: 08-30-2009, 04:38 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •