Question about Tree Node

[Taylor Woods]

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]

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]

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.

public class TreeNode
{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode (int num)
{
data = num;
left = right = null;
}
public int getData()
{
return data;
}
public TreeNode getLeft()
{
return left;
}
public TreeNode getRight()
{
return right;
}
public void setData(int newData)
{
data = newData;
}
public void setLeft(TreeNode newLeft)
{
left = newLeft;
}
public void setRight(TreeNode newRight)
{
right = newRight;
}
public TreeNode insert(int insertValue)
{
if (insertValue < data)
{
if (left == null)
left = new TreeNode (insertValue);
else
left.insert(insertValue);
return left;
}
else if (insertValue > data)
{
if (right == null)
right= new TreeNode(insertValue);
else
right.insert(insertValue);
}
return right;
}
private void preOrder(TreeNode root)
{
if (root!=null)
{
System.out.println(root.getData());
preOrder(root.getLeft());
preOrder(root.getRight());
}
}
public static void main (String [] args)
{
TreeNode root = new TreeNode(15);
root.insert(23);
root.insert(8);
root.insert(1);
root.insert(20);
root.insert(16);
root.insert(3);
root.insert(11);
root.insert(2);
root.insert(21);
root.insert(17);
root.insert(9);
root.insert(14);
root.insert(18);
root.insert(6);
root.insert(4);
root.insert(10);
root.insert(22);
root.insert(12);
root.insert(5);
root.insert(24);
root.insert(7);
root.insert(13);
root.insert(19);
root.insert(25);
root.insert(26);
System.out.println("Pre-order: ");
root.preOrder(root);
}
}

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]

 

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?

private void preOrder(TreeNode root)
{
if (root!=null)
{
System.out.println(root.getData());
preOrder(root.getLeft());
preOrder(root.getRight());
}
}

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.