need a delete method for binarytree

[Neorussell]

can somebody pl.s help me out. I'm doing a binarytree project and I have all the methods I was asked of me but he wants me to create a delete method. I have two class and a main tester class.

here's my code:
this is the binarytree class


using System;

namespace binary_tree
{
public class BinaryTree
{
private BinaryTreeNode root;

public BinaryTree()
{
root = null;
}

public bool IsEmpty()
{
return (root == null);
}

private void InorderHelper(BinaryTreeNode p)
{
if (p != null)
{
InorderHelper(p.Left);
System.Console.WriteLine(p.Data + "");
InorderHelper(p.Right);
}
}
public void Inorder()
{
InorderHelper(root);
}

private void PostOrderHelper(BinaryTreeNode p)
{
if (p != null)
{
PostOrderHelper(p.Left);
PostOrderHelper(p.Right);
System.Console.WriteLine(p.Data + "");
}
}
public void Postorder()
{
PostOrderHelper(root);
}
public void Preorder()
{
PreOrderHelper(root);
}
public void PreOrderHelper(BinaryTreeNode p)
{
if (p != null)
{
System.Console.WriteLine(p.Data + "");
PreOrderHelper(p.Left);
PreOrderHelper(p.Right);
}
}
public int CountNodes()
{
return CountNodesHelper(root);
}
private int CountNodesHelper(BinaryTreeNode rootNode)
{
if(rootNode == null)
return 0;
else
return 1 + (CountNodesHelper(rootNode.Left) + CountNodesHelper(rootNode.Right));
}

public void Insert(int InsertItem)
{
BinaryTreeNode current;
BinaryTreeNode parent = null;
BinaryTreeNode newNode;

newNode = new BinaryTreeNode(InsertItem);

if(IsEmpty())
{
root = newNode;
}
else
{
current = root;
while(current != null)
{
parent = current;
if(current.Data == InsertItem)
{
System.Console.WriteLine("Duplicates are not allowed");
return;
}
else
{
if(InsertItem < current.Data)
{
current = current.Left;
}
else
current = current.Right;
}
}
if(InsertItem < parent.Data)
{
parent.Left = newNode;
}
else
{
parent.Right = newNode;
}


}
}
public bool Search(int item)
{
BinaryTreeNode current;
bool match = false;

if(IsEmpty())
{
System.Console.WriteLine("Tree is empty");
}
else
{

current = root;

while(current != null && !match)
{

if(current.Data == item)
{
match = true;
}
else
{

if(current.Data > item)
{
current = current.Left;
}
else
{

current = current.Right;
}

}
}
}

return match;
}
public void Delete(int deleteItem)
///have no idea what to do for this method. I searched the net but only gave me delete for other programming language. Pls. help if you can.


Here's the binarytreenode class

using System;

namespace binary_tree
{

public class BinaryTreeNode
{
private int info;
private BinaryTreeNode llink;
private BinaryTreeNode rlink;

public BinaryTreeNode()
{
info = 0;
llink = rlink = null;
}
public BinaryTreeNode(int data)
{
info = data;
llink = rlink = null;
}

public BinaryTreeNode Left
{
set {llink = value;}
get {return llink;}

}
public BinaryTreeNode Right
{
set {rlink = value;}
get {return rlink;}
}
public int Data
{
set {info = value;}
get {return info;
}
}
}
}


here's the tester:

using System;
using s = System.Console;
namespace binary_tree
{

public class BinaryTester
{

public void print(BinaryTreeNode p)
{
SidePrint(p,0,"R-");
}

public void SidePrint(BinaryTreeNode p,int Level,string d)
{
int k = 0;
if(p != null)
{

SidePrint(p.Right,Level + 1,"/");

for(;k < 3 * Level;k++)
{
System.Console.Write(" ");
}
System.Console.WriteLine(d + p.Data);
SidePrint(p.Left,Level + 1,"\\");

}
}
public void Msg(string msg)
{
s.Write( msg);
}
[STAThread]
static void Main(string[] args)
{
int []nodeValue = {60,65,45,46,40,35,50,61,70,66,80,42};
BinaryTester tester = new BinaryTester();
BinaryTree bt = new BinaryTree();
tester.Msg("1.1-Loading Binary Tree");
for(int i = 0; i < nodeValue.Length;i++)
{
bt.Insert(nodeValue[i]);
}
tester.Msg("\n1.2-Add Duplicate data: ");
bt.Insert(60);
tester.Msg("1.3-Is empty : " + bt.IsEmpty());
tester.Msg("\n1.4-Count Node: " + bt.CountNodes());
tester.Msg("\n1.5-Search for 80: " + bt.Search(0x50));
tester.Msg("\n1.6-Search for 255: " + bt.Search(0xff) );
BinaryTree bt2 = new BinaryTree();
tester.Msg("\n1.7-Search Empty Tree for 80: " );
bt2.Search(0xff);
tester.Msg("1.8-Access Root: ");
BinaryTreeNode root = bt.Root;
tester.Msg(""+(root != null));
tester.Msg("\n1.9-Print tree: \n" );
tester.print(root);
tester.Msg("\n");
tester.Msg("\n1.10-InOrder: ");
bt.Inorder();
tester.Msg("\n1.11-PostOrder: ");
bt.Postorder();
tester.Msg("\n1.12-PreOrder: ");
bt.Preorder();
tester.Msg("\n1.13-Delete from tree value = 60: ");
bt.Delete(60);
tester.Msg("\n1.14-Delete from tree value = 66: \n");
bt.Delete(66);
tester.Msg("1.15-Delete from tree value = 66:");
bt.Delete(66);
tester.Msg("1.16-Delete from tree value = 42: \n");
bt.Delete(42);
tester.print(root);
tester.Msg("\n1.17-Count Node: " + bt.CountNodes());
tester.Msg("\n1.18-Is Empty: " + bt.IsEmpty());
tester.Msg("\nCongratulations Your assignment is ready to submit\nPlease don't forget to remove the BinaryTester.cs\n");
s.ReadLine();
}
}
}




I did most of the stuff but I need a delete for binarytree class.

public void Delete(int deleteItem)
///have no idea what to do for this method. I searched the net but only gave me delete for other programming language. Pls. help if you can.

thanks to anybody who helps

[Norfy]

I remember having to do this problem as part of my course work 10+ years ago...

One observation: It may have been simpler to stick with recursion or iteration. ie. Your Helper methods use recursion and Insert, and Search use iteration. For this sort of "project" recursion tends to give more elegant solutions...which is always nice.eg. bool Search(BinaryTreeNode p, int item)
{
return p != null ?
(p.Data == item) || Search(p.Left, item) || (Search(p.Right, item) : false;
}Anyway, to your problem... :)

The easy bit, if a leaf node is deleted then "parent.Left/Right = null".

If a middle node is deleted then either one of its child nodes needs to replace it. It doesn't matter which one since both (if not null) will still be in the correct place in the tree. eg. parent.Left = current.Left . The problem is now what to with current.Right. Basically you have to insert the current.Right node into current.Left.

If you refactor your current Insert method to take a destination node and a node to insert as parameters then you already have this part done.eg. void Insert (int item) { Insert(new BinaryTreeNode(item), root); }

void Insert(BinaryTreeNode newNode, BinaryTreeNode node) { // refactor your existing method}

[JetDeveloper]

Delete is a pain. Here is the basic algorithm.

Call Search() on the thing you wish to delete. If Search() fails, then there's nothing to delete.

If it does find it, then there are three cases.

(1) Node is a leaf node

Set the child of the parent that is your node to be null

(2) Node has one child, but not two.

Strip out the node from the tree, like in linked list delete. Set the parent's child (which used to be your node) to the node's child

e.g. If your node is parent's right child

set [parent].rlink to [node].[child]

(3) Node has 2 children

This one is the worst case. You need to find the node's sucessor, or next node in InOrder traversal. That is the leftmost node in the right subtree and it can have at most one child. Good proof exercise!

Find the successor and replace [node]'s value with the successor's value. Then delete the successor (yes, the successor and not your node) like you would delete a node with zero or one children.

Yes, it's a pain. It helps to keep track of the parent node as you blow through the tree.

[Norfy]

Maybe I should have done a search on the web for Delete Node From Binary Tree. (http://www.google.ch/search?hl=de&q=delete+node+binary+tree) . :)

Just shows you that there is always more than one way to solve a problem.

Call me stubborn/old fashioned/purist, but getting "the leftmost node in the right subtree" in the middle of an inorder binary tree traversal...doesn't seem right. :ehh:

But going by the web it looks like I'm outvoted... :)

[JetDeveloper]

You shouldn't use the InOrder to find the successor. It just happens that the successor is the same node as the next node in the InOrder.

Here's Why

(1) Every node in the right subtree has a greater value than the node you are trying to delete.
(2) The leftmost node of a tree/subtree has the smallest value in the tree/subtree

Therefore, the leftmost node in the right subtree has the least value that is greater than the one you wish to delete.

In other words, it is the next largest node, which is the definition of successor. This also happens to be the next node in the in-order traversal.

[Norfy]

You shouldn't use the InOrder to find the successor.I didn't/wouldn't.

You'll also find that the right-most node of the left tree is also a valid candidate.

The main reason for the "successor" algorithm is to maintain as much as possible the original structure of the tree.

In "my" algorithm I do not make any such restrictions; (as stated) the reinserted node will appear as the right-most node in the left tree.