aspose file tools*
The moose likes Beginning Java and the fly likes Question about Tree Node Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Question about Tree Node" Watch "Question about Tree Node" New topic
Author

Question about Tree Node

Taylor Woods
Greenhorn

Joined: Mar 19, 2005
Posts: 10
Hello. I have posted once to ask a qustion about Tree Node. Now, I learned a little more about Tree, and I think I figured out most things I had problem with. However, I am still having trouble with creating a constructor in order to delete a node from the tree. I tried to look it up in the "Java Guide Book" in the book store. But...I couldn't find anything about it...although I went through every book in two book stores. So I am asking for help here. If anyone has experience with creating a constructor for deleting a node from the tree, please give me some help. I will truly appreciate it. Thank you for regarding my words.
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
You should only need a remove() method to remove a node from a tree. A constructor would be used when adding a node to the tree, but not when removing.

The first step is to locate the node to remove. Then you'll need to adjust the references to and from that node such that the node is no longer referenced by the other nodes in the tree and any nodes the node to be removed referenced are now referenced by other nodes in the tree.

For example, removing a leaf node (no children) is simple: just remove the refernece to the node from its parent. You're done. Removing a node with children is more difficult: you must make sure other nodes are referencing the children of the removed node.

The specifics of the algorithm depend on the type of tree you have. Is it a binary search tree? A red-black tree? Can you describe exactly which type of tree you are creating and post some code for the tree? With that you'll be much more likely to get the guidance you need.
Taylor Woods
Greenhorn

Joined: Mar 19, 2005
Posts: 10
Thank you for your kind consideration, David.
I think I need to see some examples in order to adapt it to my own program. I will post my code I have been working on so far.
Oh...in addition, it's binary search tree.




Do you think my codes are all right? I'm not sure about the part "insert"
I kept getting an error that says I need to "return" something at the end of the "insert" method. So..I just put "return left" and "return right" even though I don't really know what they do in the code. So...could you check if it's right?

And...

From this tree, I want to delete the node containing 2, the node containing 23, and the node containing 1. Could you show me the actual code to do those if it's not too much truble?. because seeing an actual code always helps me greatly.

Thank you so much.
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Originally posted by Taylor Woods:
I'm not sure about the part "insert" I kept getting an error that says I need to "return" something at the end of the "insert" method. So..I just put "return left" and "return right" even though I don't really know what they do in the code.
What is insert's contract? Which TreeNode is it supposed to return? One likely possibility is that it should return the TreeNode that gets created to hold the value. This code will not do that, but it's very close.

Also, what happens if insertValue is already in the tree?
This method can be rewritten without the root parameter. As it stands, the root node is iterating the whole tree. Compare it to how the insert() method recurses on each node down the tree.
From this tree, I want to delete the node containing 2, the node containing 23, and the node containing 1.
The remove algorithm is tricky since you have to adjust the tree; you can't simply delete the node in place. Instead, you must adjust the two subtrees. Have you read descriptions of how to do this in your book or online? There's a fairly simple trick to it with a binary tree.

In fact, java.util.TreeMap uses a binary tree for the keys. Check it out and see if you can give it a go. Draw out what needs to happen and then write it in code.
 
Consider Paul's rocket mass heater.
 
subject: Question about Tree Node