Results 1 to 20 of 25
Thread: Trees Insert Method
- 08-05-2013, 08:31 AM #1
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
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 08:38 AM.
- 08-05-2013, 11:18 AM #2
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
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,
JosBuild a wall around Donald Trump; I'll pay for it.
- 08-05-2013, 05:26 PM #3
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
Re: Trees Insert Method
Anymore comment on this ?
- 08-05-2013, 05:49 PM #4
Just a guy
- Join Date
- Jun 2013
- Location
- Netherlands
- Posts
- 5,114
- Rep Power
- 13
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
- 08-05-2013, 05:52 PM #5
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
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.
- 08-05-2013, 06:00 PM #6
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
- 08-05-2013, 06:04 PM #7
Just a guy
- Join Date
- Jun 2013
- Location
- Netherlands
- Posts
- 5,114
- Rep Power
- 13
- 08-05-2013, 06:12 PM #8
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
Re: Trees Insert Method
Did you even read through the codes? How incorrect it is? Which part?
- 08-05-2013, 06:17 PM #9
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
Re: Trees Insert Method
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.
JosBuild a wall around Donald Trump; I'll pay for it.
- 08-05-2013, 06:23 PM #10
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
Re: Trees Insert Method
My question is right above the code. and no the tree does not allow duplicates of parentchild.
- 08-05-2013, 06:29 PM #11
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
Re: Trees Insert Method
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;
JosBuild a wall around Donald Trump; I'll pay for it.
- 08-05-2013, 06:38 PM #12
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
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(); } }
- 08-05-2013, 07:01 PM #13
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
Re: Trees Insert Method
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.
JosBuild a wall around Donald Trump; I'll pay for it.
- 08-06-2013, 12:02 PM #14
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
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 12:50 PM.
- 08-06-2013, 01:18 PM #15
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
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.
JosBuild a wall around Donald Trump; I'll pay for it.
- 08-06-2013, 01:31 PM #16
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
Re: Trees Insert Method
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 01:39 PM.
- 08-06-2013, 03:34 PM #17
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
Re: Trees Insert Method
Build a wall around Donald Trump; I'll pay for it.
- 08-06-2013, 04:26 PM #18
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
Re: Trees Insert Method
Last edited by Malv; 08-06-2013 at 04:29 PM.
- 08-06-2013, 05:20 PM #19
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
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.
JosBuild a wall around Donald Trump; I'll pay for it.
- 08-06-2013, 05:37 PM #20
Member
- Join Date
- Jun 2013
- Posts
- 62
- Rep Power
- 0
Similar Threads
-
Help with binary trees please
By sim18 in forum New To JavaReplies: 3Last Post: 11-27-2012, 08:34 PM -
Abstract table model help adding the insert row method too it
By kevinn205 in forum AWT / SwingReplies: 7Last Post: 12-03-2011, 05:25 AM -
Need help with Trees...(8-puzzle)
By ventrue in forum New To JavaReplies: 2Last Post: 03-24-2009, 12:04 AM -
How to insert large data into database using one insert query
By sandeepsai39 in forum New To JavaReplies: 3Last Post: 02-28-2009, 10:17 AM -
Insert() Method Help
By VinceGuad in forum New To JavaReplies: 7Last Post: 02-26-2009, 06:19 AM
Bookmarks