aspose file tools*
The moose likes Beginning Java and the fly likes replace a subTree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "replace a subTree" Watch "replace a subTree" New topic
Author

replace a subTree

Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
I have a tree

(+)
/\
(2)(5)

The method setupSubtreeList(n), adds each node object onto an array list. subNodes.get(1)=return the node object(+), subNodes.get(1)=return the node object(2) etc.
I would like to create a method that allows me to change the nodes (2nd node contains a (2) replacing it with a new node object).


Original tree
(+)
/\
(2)(5)

create a new node object with (3) and maybe some siblings, to replace the (2) node


Altered tree
(+)
/\
(3)(5)
/\
()()

I have tried to use subNodes.set(1, new Node("3")). But it does not seem to work, when i print out the tree it still return the tree containing the original node values


Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Terence hiu wrote:How can i edit the nodes using the list?

you have tree right? then why do you put your all the tree nodes to list and edit in first place?
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Seetharaman Venkatasamy wrote:
Terence hiu wrote:How can i edit the nodes using the list?

you have tree right? then why do you put your all the tree nodes to list and edit in first place?


I have to randomly generate a subtree and add it to an existing node. That is why i place the nodes onto a list, so it be easier for me to replace that node with then randomly generate subtree
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Terence hiu wrote:I have to randomly generate a subtree and add it to an existing node.

why? minimum spanning tree or (probably not this)shortest distance? . and i suggest you to read Introduction algorithm[in some(rarely) topic too high level] or i am planing to publish a book in algorithm at basic level,
*because I want to become an author* let see.. (no time as of now)
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Terence hiu wrote:
I have to randomly generate a subtree and add it to an existing node.

can you elaborate more... high level do you go for BFS(you want this right?) or DFS ?
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Seetharaman Venkatasamy wrote:
Terence hiu wrote:
I have to randomly generate a subtree and add it to an existing node.

can you elaborate more... high level do you go for BFS(you want this right?) or DFS ?

BFS
I have re edited the original post. Giving a more clear description. hopefully.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

not sure about your *code* tag. it just edit of data in a tree... do tree traversal and do the update on a node value you want. (not sure this is what you want)
note: tree may contains duplicates in terms of data
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Seetharaman Venkatasamy wrote:not sure about your *code* tag. it just edit of data in a tree... do tree traversal and do the update on a node value you want. (not sure this is what you want)
note: tree may contains duplicates in terms of data


This is my actual Node class, to make things clear.




i want to create another method say



the int param would be the nth node i want to replace the with the new node
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 1950
    
  28
I have re edited the original post. Giving a more clear description. hopefully.

Please don't edit your posts after someone has replied to them as it makes the reply look nonsensical and hence makes the thread very hard to read for other people.
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2066
    
  22

I am completely confused regarding how converting the nodes into an array is going to help you replace a node. To replace a node you have to edit the node's parent. How is getting into the list going to help you?

And you editing your original post is not helping either because the replies after that post don;t make any sense now. Anyone coming into the thread is going to give up after a few posts

Please help us by trying to TellTheDetails. What exactly did you try already?
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Constructor must have the same name as class name here. then what is the necessary of Node a, Node b and Node list in a class , it is enough to say list in terms of N-ary tree
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Jayesh A Lalwani wrote:I am completely confused regarding how converting the nodes into an array is going to help you replace a node. To replace a node you have to edit the node's parent. How is getting into the list going to help you?

And you editing your original post is not helping either because the replies after that post don;t make any sense now. Anyone coming into the thread is going to give up after a few posts

Please help us by trying to TellTheDetails. What exactly did you try already?


The reason why i converted the nodes into an array, is to make it easier for me to access that particular node and replace it. So if i wanted to replace the 3rd node i could just access the 3rd element in the array list and replace it as it is still the reference to the 3rd parent node(I think). But this does not work for some reason.

I am very sorry about editing the original post..


I have tried creating a method, to replace the nth node with the new node n. It access the element in my array and replaces it.
I have tried to print out the altered tree, but no changes are made



The output is still the same :


+ * 2 3 5
NEW
+ * 2 3 5
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2066
    
  22

Ok, so when you say Nth node, I am assuming that you mean the Nth node when you do a Depth First search.

There are many ways of doing this and converting the whole tree into an array is probably not the best one. Assuming you want to stick with converting into array, you can do it by having each child have a reference to it's parent. Then you can do this



However, this method has the performance of O(n) mainly because converting the tree to a list is an O(n) operation. Having performance of O(n) defeats the whole purpose of having a tree

Another way you can do is do a DF walk through the tree, and keep counting the nodes visited as you walk. Once you reach the parent of the nth node, replace it.
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Jayesh A Lalwani wrote:Ok, so when you say Nth node, I am assuming that you mean the Nth node when you do a Depth First search.

There are many ways of doing this and converting the whole tree into an array is probably not the best one. Assuming you want to stick with converting into array, you can do it by having each child have a reference to it's parent. Then you can do this



However, this method has the performance of O(n) mainly because converting the tree to a list is an O(n) operation. Having performance of O(n) defeats the whole purpose of having a tree

Another way you can do is do a DF walk through the tree, and keep counting the nodes visited as you walk. Once you reach the parent of the nth node, replace it.



How would i make each child have a reference to its parent?
int my node class i have added :

Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2066
    
  22

Yes, now when you add a node to the tree, set the parent attribute of the node to be the node's parent.
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Jayesh A Lalwani wrote:Yes, now when you add a node to the tree, set the parent attribute of the node to be the node's parent.


Could this be done in a constructor? I know i could use a setParent() method in the node class.

I am also curious on how the 2nd method DFS would be implemented. Can it be implemented recursively? since every recursive call, my counter would be set back to 0

Thankyou
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2066
    
  22

Well, you are doing a depth first walk in your returnAllSubNodes method. So, you already know how to do a DFS. Basically in your returnAllSubNodes method, instead of putting the nodes in the array just increment a counter. Once the counter hits n-1 or n-2, you have reached the parent of the node
Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Jayesh A Lalwani wrote:Well, you are doing a depth first walk in your returnAllSubNodes method. So, you already know how to do a DFS. Basically in your returnAllSubNodes method, instead of putting the nodes in the array just increment a counter. Once the counter hits n-1 or n-2, you have reached the parent of the node


My retrunAllSubNodes method is just creating a new array and return the initialise array. Do you mean then setupSubTreeArray?

Terence hiu
Ranch Hand

Joined: Oct 21, 2012
Posts: 36
Really appropriate the help. Finally worked out how to implement it both ways
Thanks to all that contributed.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: replace a subTree
 
Similar Threads
override the equals and hashcode
jtree to jtable (need help in coding)
How data is added in a ArrayList
print a HashSet of objects
Create a tree from a resultset