Monday, October 20, 2008

How to delete node from binary search tree(C#)

namespace BinarySearchTreeDelete
{
//define a Node class for tree
public class Node
{
public int Data;
public Node Left;
public Node Right;

public void DisplayNode()
{
Console.Write(Data+" ");
}
}

public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}

public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node Current = root;
Node parent;
while (true)
{
parent = Current;
if (i < Current.Data)
{
Current = Current.Left;
if (Current == null)
{
parent.Left = newNode;
break;
}
}
else
{
Current = Current.Right;
if (Current == null)
{
parent.Right = newNode;
break;
}
}
}
}
}

public void InOrder(Node theRoot)
{
if (theRoot != null)
{
InOrder(theRoot.Left);
theRoot.DisplayNode();
InOrder(theRoot.Right);
}
}

public Node GetSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.Right;

while (current != null)
{
successorParent = current;
successor = current;
current = current.Left;
}
if (successor != delNode.Right)
{
successorParent.Left = successor.Right;
successor.Right = delNode.Right;
}
return successor;
}

public bool Delete(int key)
{
Node current = root;
Node parent = root;
bool isLeftChild = true;
while (current.Data != key)
{
parent = current;
if (key < current.Data)
{
isLeftChild = true;
current = current.Left;//
}
else
{
isLeftChild = false;
current = current.Right;
}
if (current == null)
{
return false;
}
}

if (current.Left == null && current.Right == null)
{
if (current == root)
{
root = null;
}
else if (isLeftChild)
{
parent.Left = null;
}
else
{
parent.Right = null;
}
}
else if (current.Right == null)
{
if (current == root)
{
root = current.Left;
}
else if (isLeftChild)
{
parent.Left = current.Left;
}
else
{
parent.Right = current.Right;
}
}
else if (current.Left == null)
{
if (current == root)
{
root = current.Right;
}
else if (isLeftChild)
{
parent.Left = parent.Right;
}
else
{
parent.Right = current.Right;
}
}
else
{
Node successor = GetSuccessor(current);
if (current == root)
{
root = successor;
}
else if (isLeftChild)
{
parent.Left = successor;
}
else
{
parent.Right = successor;
}
successor.Left = current.Left;
}
return true;
}
}

class Program
{
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree();
BST.Insert(23);
BST.Insert(45);
BST.Insert(16);
BST.Insert(37);
BST.Insert(3);
BST.Insert(99);
BST.Insert(22);
BST.Insert(5);
Console.WriteLine("InOrder traversing...");
BST.InOrder(BST.root);
Console.WriteLine();
if (BST.Delete(45))
{
BST.InOrder(BST.root);
}
else
{
Console.WriteLine("there is no this number...");
}
Console.WriteLine();
}
}
}

No comments: