Data structure HW
mojahed44
p3-1_binarysearchtree.docxusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BinaryTree
{
class Node
{
public int item;
public Node leftChild, rightChild;
public Node(int _iData)
{
item = _iData;
}
public Node()
{
}
public override string ToString()
{
return string.Format("{0} ", item);
}
}
class Tree
{
public Node root;
public Tree()
{
root = null;
}
public Node Find(int key)
{
Node current = root;
while (current.item != key)
{
if (key < current.item)
current = current.leftChild;
else
current = current.rightChild;
if (current == null)
return null;
}
return current;
}
public void Insert(int id)
{
Node newNode = new Node(id);
if (root == null)
root = newNode;
else
{
Node current = root;
Node parent;
while (true)
{
parent = current;
if (id < current.item) //go left?
{
current = current.leftChild;
if (current == null) //if end of line, insert on left
{
parent.leftChild = newNode;
return;
}
} //end if go left
else
{
current = current.rightChild;
if (current == null) //if end of line, insert on right
{
parent.rightChild = newNode;
return;
}
} //end of else go right
} //end while
} //end else not root
}
public bool Delete(int KEY)
{
Node current = root;
Node parent = root;
bool isLeftChild = true;
/* Find the deleting node (current) */
while (current.item != KEY)
{
parent = current;
if (KEY < current.item)
{
isLeftChild = true;
current = current.leftChild;
}
else
{
isLeftChild = false;
current = current.rightChild;
}
if (current == null)
return false;
}
/* Case 1: the deleting node (current) has no child */
if ((current.leftChild == null) && (current.rightChild == null))
if (current == root)
root = null;
else if (isLeftChild)
parent.leftChild = null;
else
parent.rightChild = null;
/* Case 2: the deleting node (current) has one child */
else if (current.rightChild == null)
if (current == root)
root = current.leftChild;
else if (isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
else if (current.leftChild == null)
if (current == root)
root = current.rightChild;
else if (isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
/* Case 3: the deleting node (current) has two children */
else
{
Node successorParent = GetSuccessorParent(current);
Node successor = successorParent.leftChild;
if (!(successor == current.rightChild))
{
successorParent.leftChild = successor.rightChild;
}
current.item = successor.item;
}
return true;
}
public Node GetSuccessorParent(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while (!(current == null))
{
successorParent = successor;
successor = current;
current = current.leftChild;
}
return successorParent;
}
public void Traverse(int traverseType)
{
switch (traverseType)
{
case 1: Console.WriteLine("\nPreorder traversal: ");
Preorder(root);
break;
case 2: Console.WriteLine("\nInorder traversal: ");
Inorder(root);
break;
case 3: Console.WriteLine("\nPostorder traversal: ");
Postorder(root);
break;
}
Console.WriteLine();
}
private void Preorder(Node localRoot)
{
if (localRoot != null)
{
Console.WriteLine(localRoot + " ");
Preorder(localRoot.leftChild);
Preorder(localRoot.rightChild);
}
}
private void Inorder(Node localRoot)
{
if (localRoot != null)
{
Inorder(localRoot.leftChild);
Console.WriteLine(localRoot + " ");
Inorder(localRoot.rightChild);
}
}
private void Postorder(Node localRoot)
{
if (localRoot != null)
{
Postorder(localRoot.leftChild);
Postorder(localRoot.rightChild);
Console.WriteLine(localRoot + " ");
}
}
public void DisplayTree()
{
Inorder(root);
}
}
class Program
{
static void Main(string[] args)
{
int iValue;
Tree theTree = new Tree ();
Random rand = new Random();
Console.WriteLine("The following nodes are inserted to the tree: ");
for (int i = 0; i < 10; i++)
{
iValue = rand.Next(1, 100);
theTree.Insert(iValue);
Console.Write("{0} ", iValue);
}
while (true)
{
Console.Write("Enter first letter of show, insert, find, delete, or traverse, q to quit: ");
char choice = char.Parse(Console.ReadLine());
switch (choice)
{
case 's':
theTree.DisplayTree();
break;
case 'i':
Console.WriteLine("Enter values to insert: ");
Console.Write("Enter key: ");
iValue = int.Parse(Console.ReadLine());
theTree .Insert (iValue);
break;
case 'f':
Console.Write("Enter key to find: ");
iValue = int.Parse(Console.ReadLine());
Node found = theTree .Find (iValue );
if(found != null)
{
Console.WriteLine("Found!");
Console.WriteLine(found);
}
else
Console.WriteLine("Could not find the node with the key {0}", iValue );
break;
case 'd':
Console.Write("Enter the key to delete: ");
iValue = int.Parse (Console.ReadLine());
bool didDelete = theTree .Delete (iValue );
if(didDelete )
Console.WriteLine ("Deleted node with key {0}", iValue );
else
Console.WriteLine ("Could not deleted node with key {0}", iValue );
break;
case 't':
Console.Write("Type 1,2, or 3 to traverse the tree: ");
iValue = int.Parse (Console.ReadLine ());
theTree .Traverse (iValue );
break;
case 'q':
Console.WriteLine("Goodbye!");
return;
default:
Console.WriteLine("Invalid entry.");
break;
}
}
}
}
}
