download code here
binary tree class:
using System;
using System.Collections.Generic;
using System.Text;
namespace BinaryTree
{
class TreeNode
{
private TreeNode leftNode; // link to left child
private int data; // data stored in node
private TreeNode rightNode; // link to right child
// initialize data and make this a leaf node
public TreeNode(int nodeData)
{
data = nodeData;
leftNode = rightNode = null; // node has no children
} // end constructor
// LeftNode property
public TreeNode LeftNode
{
get
{
return leftNode;
} // end get
set
{
leftNode = value;
} // end set
} // end property LeftNode
// Data property
public int Data
{
get
{
return data;
} // end get
set
{
data = value;
} // end set
} // end property Data
// RightNode property
public TreeNode RightNode
{
get
{
return rightNode;
} // end get
set
{
rightNode = value;
} // end set
} // end property RightNode
// insert TreeNode into Tree that contains nodes;
// ignore duplicate values
public void Insert(int insertValue)
{
if (insertValue < data) // insert in left subtree
{
// insert new TreeNode
if (leftNode == null)
leftNode = new TreeNode(insertValue);
else // continue traversing left subtree
leftNode.Insert(insertValue);
} // end if
else if (insertValue > data) // insert in right subtree
{
// insert new TreeNode
if (rightNode == null)
rightNode = new TreeNode(insertValue);
else // continue traversing right subtree
rightNode.Insert(insertValue);
} // end else if
} // end method Insert
} // end class TreeNode
// class Tree declaration
public class Tree
{
private TreeNode root;
// construct an empty Tree of integers
public Tree()
{
root = null;
} // end constructor
// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public void InsertNode(int insertValue)
{
if (root == null)
root = new TreeNode(insertValue);
else
root.Insert(insertValue);
} // end method InsertNode
// begin preorder traversal
public void PreorderTraversal()
{
PreorderHelper(root);
} // end method PreorderTraversal
// recursive method to perform preorder traversal
private void PreorderHelper(TreeNode node)
{
if (node == null)
return;
// output node data
Console.Write(node.Data + " ");
// traverse left subtree
PreorderHelper(node.LeftNode);
// traverse right subtree
PreorderHelper(node.RightNode);
} // end method PreorderHelper
// begin inorder traversal
public void InorderTraversal()
{
InorderHelper(root);
} // end method InorderTraversal
// recursive method to perform inorder traversal
private void InorderHelper(TreeNode node)
{
if (node == null)
return;
// traverse left subtree
InorderHelper(node.LeftNode);
// output node data
Console.Write(node.Data + " ");
// traverse right subtree
InorderHelper(node.RightNode);
} // end method InorderHelper
// begin postorder traversal
public void PostorderTraversal()
{
PostorderHelper(root);
} // end method PostorderTraversal
// recursive method to perform postorder traversal
private void PostorderHelper(TreeNode node)
{
if (node == null)
return;
// traverse left subtree
PostorderHelper(node.LeftNode);
// traverse right subtree
PostorderHelper(node.RightNode);
// output node data
Console.Write(node.Data + " ");
} // end method PostorderHelper
// delete node function
// this will check the root first.
// then try to search the delete value in the tree
// if the node is found, delete the node based on three consideration
// 1 Deleting a leaf
// 2 Deleting a node with one child
// 3 Deleting a node with two children
public void DeleteNode(int deleteValue)
{
if (root == null)
return;
// check the root data
// delete root node if its data equals to delete value
else if (root.Data == deleteValue)
{
if (root.LeftNode == null)
root = root.RightNode;
else if (root.RightNode == null)
root = root.LeftNode;
else if (root.LeftNode != null && root.RightNode != null)
{
int data = getPredecessor(root.LeftNode);
delRecNode(root.LeftNode, data);
root.Data = data;
}
}
else
{
delRecNode(root, deleteValue);
}
}
// recursive function to delete node based on value
private bool delRecNode(TreeNode node, int value)
{
if (node == null)
return false; // do nothing
if (value < node.Data)
{
if(delRecNode(node.LeftNode, value))
{
// There are several cases to be considered in deletion:
// case 1 no children
if (node.LeftNode.LeftNode == null && node.LeftNode.RightNode == null)
node.LeftNode = null;
// case 2 node has 1 child
else if (node.LeftNode.LeftNode == null)
node.LeftNode = node.LeftNode.RightNode;
else if (node.LeftNode.RightNode == null)
node.LeftNode = node.LeftNode.LeftNode;
// case 3 node has 2 children
else if (node.LeftNode.LeftNode != null && node.LeftNode.RightNode != null)
{
int data = getPredecessor(node.LeftNode.LeftNode);
// delete precessor
delRecNode(node.LeftNode.LeftNode, data);
node.LeftNode.Data = data;
}
}
return false;
}
else if (value > node.Data)
{
if(delRecNode(node.RightNode, value))
{
// There are several cases to be considered in deletion:
// case 1 no children
if (node.RightNode.LeftNode == null && node.RightNode.RightNode == null)
node.RightNode = null;
// case 2 node has 1 child
else if (node.RightNode.LeftNode == null)
node.RightNode = node.RightNode.RightNode;
else if (node.RightNode.RightNode == null)
node.RightNode = node.RightNode.LeftNode;
// case 3 node has 2 children
else if (node.RightNode.LeftNode != null && node.RightNode.RightNode != null)
{
int data = getPredecessor(node.RightNode.LeftNode);
// delete precessor
delRecNode(node.RightNode.LeftNode, data);
node.RightNode.Data = data;
}
}
return false;
}
else if (value == node.Data)
{
return true;
}
return false;
}
// get the value of predecessor
private int getPredecessor(TreeNode node)
{
if (node.RightNode != null)
{
return getPredecessor(node.RightNode);
}
else
{
return node.Data;
}
}
}
}
