Page 1 of 2 12 LastLast
Results 1 to 20 of 25
  1. #1
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Trees Insert Method

    Question :

    The insert method takes two parameters, parentVal and childVal and inserts a new node containing childVal as the last child of any node containing parentVal. If there is no node containg parentVal then insert has no effect. insert will not insert a new node below a parent that has a pre-existing child node containing childVal. To illustrate, the call insert(3,3) on the tree:

    Root: 1
    Child of 1: 3,4

    will result in the tree:

    Root: 1
    Child of 1: 3,4
    Child of 3: 3

    which, when when given the call insert(3,5) will result in the tree:

    Root: 1
    Child of 1: 3,4
    Child of 3: 3,5
    Child of 3: 5

    Futher calls with duplicate elements such as insert(3,5) or insert(1,4) will have no effect.


    Below is my code and my code does not have the case which after I insert 1,4 and 1,3 , I want to insert 3,3 but it just simply ignores the code. Anyone can tell me which part affects?

    Java Code:
    public void insert(T parentVal, T childVal){
            insert(root, parentVal, childVal);
        }
    
        // put any auxiliary methods you may define here.
    
        private void insert(Node<T> n, T parentVal, T childVal){
            boolean notInserted = true;
            for(int i=0; i<n.children.size(); i++){
                if(n.children.get(i).val.equals(childVal)){
                    notInserted = false;
                }
            }
            if(notInserted){
                if(n.val.equals(parentVal)){ // i think its this part.
                    Node<T> tmp = new Node<T>();
                    tmp.val = childVal;
                    n.children.add(tmp);
                }
                for(int i=0; i<n.children.size(); i++){
                    insert(n.children.get(i), parentVal, childVal);
                }
            }
    }
    Last edited by Malv; 08-05-2013 at 07:38 AM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    I don't understand your algorithm, imho it should be:

    - find the parent node; if not found then stop;
    - if the new node already a child of parent then stop;
    - add new node as child of parent.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    Anymore comment on this ?

  4. #4
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,900
    Rep Power
    5

    Default Re: Trees Insert Method

    If you don't understand what JosAH is telling you then say so and ask for clarification, don't just ignore him and ask for other comments.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  5. #5
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    I understand. Just that he doesn't understand. So i asked for other comments. Don't just assume. Didn't ask for unrelated comment, thanks.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    Quote Originally Posted by Malv View Post
    I understand. Just that he doesn't understand. So i asked for other comments. Don't just assume. Didn't ask for unrelated comment, thanks.
    Who doesn't understand what, except for your incorrect algorithm?

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,900
    Rep Power
    5

    Default Re: Trees Insert Method

    Quote Originally Posted by Malv View Post
    I understand. Just that he doesn't understand. So i asked for other comments. Don't just assume. Didn't ask for unrelated comment, thanks.
    Then tell Jos you think he's mistaken! Its just rude to flat out ignore someone that is trying to help; I certainly wouldn't want to help anyone that acts like that.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  8. #8
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    Did you even read through the codes? How incorrect it is? Which part?

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    Quote Originally Posted by Malv View Post
    Did you even read through the codes? How incorrect it is? Which part?
    You have to give more information w.r.t. the requirements; does the tree contain duplicates? If so, do you want to add the new node to all those duplicates? Is it a search tree? You can't be just vague, hand over an incorrect implementation of an algorithm (otherwise you wouldn't have started this thread) and expect others to do your work and just spoonfeed you. You want a correct implementation, we couldn't care less.

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    My question is right above the code. and no the tree does not allow duplicates of parentchild.

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    Quote Originally Posted by Malv View Post
    My question is right above the code. and no the tree does not allow duplicates of parentchild.
    Then my first suggestion still applies 100%:

    - find the parent node; if not found then stop;
    - if the new node already a child of parent then stop;
    - add new node as child of parent.

    You can add one more constraint:

    - if the new node is already in the tree (somewhere) then stop;

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    - find the parent node; if not found then stop; // if(n.val.equals(parentVal)){
    - if the new node already a child of parent then stop; // if(n.children.get(i).val.equals(childVal)){ <- but this only see if n.children contains childVal
    - add new node as child of parent.
    // Node<T> tmp = new Node<T>();
    tmp.val = childVal;
    n.children.add(tmp);

    You can add one more constraint:

    - if the new node is already in the tree (somewhere) then stop; //done

    anyway the tree doesnt work in a way where parent and child node can be found.
    Here is the full code:

    Java Code:
    import java.util.*;
    
    
    /**
       Definition of a tree container that supports insertion 
       by adding the child not correspoinding to a parent node.
    */
    
    public class InsertByParentTree<T>{
    
     
        private Node<T> root;   // reference to the root of the tree.
    
    
        /**
          private class defining a tree node.
        */
    
        private class Node<T1>{
           
            // data members, value and children.
    
            public T1 val;
            public ArrayList<Node<T1>> children = new ArrayList<Node<T1>>();
    
            // zero-argument toString method
    
            public String toString(){
                return toString("");
            }
    
            // auxiliary toString method to print the tree in 
            // a nice indented fashion.
    
            public String toString(String prefix){
    
                String res = prefix + val + "\n";
                for (Node<T1> x: children){
                    res += prefix + x.toString(prefix+" ");
                }
                return res;
            }
    
        }
    
    
       
        /**
           Constructor for InsertByParentTree's. 
           Builds the root node.
           @param val the value to insert at the root node.
        */
        public InsertByParentTree(T val){
            root = new Node<T>();
            root.val = val;
        }
    
    
        /**
         Inserts a node containing childVal  at the end of the list
         of childnodes of each node containing parentVal. 
         Does nothing if, parentVal cannot be 
         found in the tree. Will not insert a node under a parent
         containing parentVal if a node containing childVal is already
         an immediate child of childval.
         @param parentVal the data in the parent node to match.
         @param childVal the data to be inserted in a new node
                under the parentVal.
        */
        
        public void insert(T parentVal, T childVal){
            if(root!=null){
                insert(root, parentVal, childVal);
            }
        }
    
        // put any auxiliary methods you may define here.
    
        private void insert(Node<T> n, T parentVal, T childVal){
            boolean notInserted = true;
            for(int i=0; i<n.children.size(); i++){
                if(n.children.get(i).val.equals(childVal)){
                    notInserted = false;
                }
            }
            if(notInserted){
                if(n.val.equals(parentVal)){
                    Node<T> tmp = new Node<T>();
                    tmp.val = childVal;
                    n.children.add(tmp);
                }
                for(int i=0; i<n.children.size(); i++){
                    insert(n.children.get(i), parentVal, childVal);
                }
            }
        }
        
        public static void main(String args[]){
            InsertByParentTree<Integer> myTree = new InsertByParentTree<Integer>(1);
                myTree.insert(1,4);
                myTree.insert(1,3);
                myTree.insert(3,3);
            System.out.println(myTree.toString());
        }
    
        public String toString(){
            return root.toString();
        }
    }

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    Quote Originally Posted by Malv View Post
    anyway the tree doesnt work in a way where parent and child node can be found.
    Trees don't work; only certain animals do.

    Start with a simple (recursive) method Node<T> find(T t) that finds a Node for you (if present). If find(child) returns non-null, there is no need to insert anything because it's already in the tree; otherwise if find(parent) returns non-null, insert your child to the parent.

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    Hi Jos,

    Has gone through your answer and understood your logic.

    However I still have doubts on what to do on the else case. Line 80 to 87

    Below is the code:

    Java Code:
    import java.util.*;
    
    
    /**
       Definition of a tree container that supports insertion 
       by adding the child not correspoinding to a parent node.
    */
    
    public class InsertByParentTree<T>{
    
     
        private Node<T> root;   // reference to the root of the tree.
    
    
        /**
          private class defining a tree node.
        */
    
        private class Node<T1>{
           
            // data members, value and children.
    
            public T1 val;
            public ArrayList<Node<T1>> children = new ArrayList<Node<T1>>();
    
            // zero-argument toString method
    
            public String toString(){
                return toString("");
            }
    
            // auxiliary toString method to print the tree in 
            // a nice indented fashion.
    
            public String toString(String prefix){
    
                String res = prefix + val + "\n";
                for (Node<T1> x: children){
                    res += prefix + x.toString(prefix+" ");
                }
                return res;
            }
    
        }
    
    
       
        /**
           Constructor for InsertByParentTree's. 
           Builds the root node.
           @param val the value to insert at the root node.
        */
        public InsertByParentTree(T val){
            root = new Node<T>();
            root.val = val;
        }
    
    
        /**
         Inserts a node containing childVal  at the end of the list
         of childnodes of each node containing parentVal. 
         Does nothing if, parentVal cannot be 
         found in the tree. Will not insert a node under a parent
         containing parentVal if a node containing childVal is already
         an immediate child of childval.
         @param parentVal the data in the parent node to match.
         @param childVal the data to be inserted in a new node
                under the parentVal.
        */
        
        public void insertChild(Node<T> n, T parentVal, T childVal){
            Node<T> findParent = find(n, parentVal);
            Node<T> findChild = find(n, childVal);
            Node<T> ch = new Node<T>();
    
            if(n.val.equals(parentVal)){ //finds the correct parentVal and add the childVal to the parentVal
                ch.val = childVal; 
                n.children.add(ch); //adds the childVal into n.children
            }
            /*else{
                // when parentVal == childVal, for example when I insert(3,3), it comes in here
                }
            }*/
            
            for(int i=0; i<n.children.size(); i++){
                if(findChild == null && findParent != null){
                    insertChild(n.children.get(i), parentVal, childVal);
                }
                
            }
        }
        
        public void insert(T parentVal, T childVal){
            if(root!=null){
                insertChild(root, parentVal, childVal);
            }
        }
        
            
        private Node<T> find(Node<T>n, T t){
            boolean contains = false;
            Node<T> tmp = new Node<T>();
            for(int i=0; i<n.children.size(); i++){
                if(n.children.get(i).val.equals(t)){
                    contains = true;
                }
            }
            if(contains==true){
                tmp.val = t;
            }else{
                tmp.val = null;
            }
            return tmp;
        }
        
        public static void main(String args[]){
            InsertByParentTree<Integer> myTree = new InsertByParentTree<Integer>(1);
                myTree.insert(1,4);
                myTree.insert(1,3);
                myTree.insert(3,3);
            System.out.println(myTree.toString());
        }
    
        public String toString(){
            return root.toString();
        }
    }
    Last edited by Malv; 08-06-2013 at 11:50 AM.

  15. #15
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    First try to find the child node; if you found it there is no need to continue because the child is already in the tree (no duplicates allowed according to your own requirements); next try to find the parent node; if not found there is also no need to continue (again, according to your own requirements); else add a new child node to the found parent node.

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    Quote Originally Posted by JosAH View Post
    First try to find the child node; if you found it there is no need to continue because the child is already in the tree (no duplicates allowed according to your own requirements); next try to find the parent node; if not found there is also no need to continue (again, according to your own requirements); else add a new child node to the found parent node.

    Jos
    sorry jos. sorry for the misunderstanding. you ask me to find the child node. den if i found it, no need to continue but now, i just realise that child can be duplicated. what changes are there to the logic now? when i have already inserted(1,4) in, i cannot insert another (1,4) again, only this cannot be duplicated
    Last edited by Malv; 08-06-2013 at 12:39 PM.

  17. #17
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    Quote Originally Posted by Malv View Post
    sorry jos. sorry for the misunderstanding. you ask me to find the child node. den if i found it, no need to continue but now, i just realise that child can be duplicated. what changes are there to the logic now? when i have already inserted(1,4) in, i cannot insert another (1,4) again, only this cannot be duplicated
    That is never going to work: suppose I insert (1, 2) (1 is the parent of 2), next I insert (2, 1) which is allowed by your requirements and finally I want to insert (1, 3); which one? Better sort out your requirements first before you start asking questions here.

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  18. #18
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    Quote Originally Posted by JosAH View Post
    That is never going to work: suppose I insert (1, 2) (1 is the parent of 2), next I insert (2, 1) which is allowed by your requirements and finally I want to insert (1, 3); which one? Better sort out your requirements first before you start asking questions here.

    Jos
    Sorry jos for the messy requirements. from your case, insert(1,2), insert(2,1), insert(1,3) . it should work and appear as

    1
    ^2
    ^^1
    ^^^3
    ^3

    but if i were to add in 2,2 ?'

    it should be

    1
    ^2
    ^^1
    ^^2^3
    ^3

    but my output is
    1
    ^2
    ^^1
    ^^^3
    ^3
    ^2
    Last edited by Malv; 08-06-2013 at 03:29 PM.

  19. #19
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,447
    Blog Entries
    7
    Rep Power
    20

    Default Re: Trees Insert Method

    Is the requirement: for every potential parent, add the new node as a child; a potential parent is a node that doesn't have the new node as a child yet.

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  20. #20
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Re: Trees Insert Method

    Quote Originally Posted by JosAH View Post
    Is the requirement: for every potential parent, add the new node as a child; a potential parent is a node that doesn't have the new node as a child yet.

    Jos
    i think so jos? dont really understand what it means thou

Page 1 of 2 12 LastLast

Similar Threads

  1. Help with binary trees please
    By sim18 in forum New To Java
    Replies: 3
    Last Post: 11-27-2012, 07:34 PM
  2. Replies: 7
    Last Post: 12-03-2011, 04:25 AM
  3. Need help with Trees...(8-puzzle)
    By ventrue in forum New To Java
    Replies: 2
    Last Post: 03-23-2009, 11:04 PM
  4. Replies: 3
    Last Post: 02-28-2009, 09:17 AM
  5. Insert() Method Help
    By VinceGuad in forum New To Java
    Replies: 7
    Last Post: 02-26-2009, 05:19 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
  •