思路
二叉搜索树的插入
TreeNode InsertRec(rootNode, key) =
if rootNode == NULL, return new Node(key)
if key >= rootNode.data, rootNode.rightChild = InsertRec(rootNode.rightChild, key)
if Key < rootNode.data, rootNode.leftChild = InsertRec(rootNode.leftChild, key)
Context is: currentNode的reference 和要插入的key.
把key插入一个以rootNode为根的子树中去
二叉搜索树的删除
TreeNode DeleteRec(rootNode, key) =
if rootNode == NULL, return rootNode
if key >= rootNode.data, rootNode.rightChild = DeleteRec(rootNode.rightChild, key)
if Key < rootNode.data, rootNode.leftChild = DeleteRec(rootNode.leftChild, key)
Context is: currentNode的reference 和要删除的key.
把key从一个以rootNode为根的子树中删去
在base case里，
- 如果是叶子节点返回空即可，
- 如果是单子节点，如果左子为空就返回右子。如果右子为空，就返回左子。
- 如果被删节点有两个孩子，则组要借助util找到中序遍历的后继节点， take 其值，然后再递归删除successor节点。
实现
/// <summary>
/// insert record to BST recursively
/// </summary>
/// <param name="root">current root node</param>
/// <param name="key">the value of the element to be inserted</param>
public TreeNode<T> InsertRec(TreeNode<T> rootNode, T key)
{
if (rootNode == null)
{
rootNode = new TreeNode<T>();
rootNode.data = key;
return rootNode;
} if (key.CompareTo(rootNode.data) < )
{
rootNode.leftChild = InsertRec(rootNode.leftChild, key);
}
else
{
rootNode.rightChild = InsertRec(rootNode.rightChild, key);
} return rootNode;
} public void DeleteKey(T key)
{
this.root = DeleteRec(root, key);
} public void InsertKey(T key)
{
this.root = InsertRec(root, key);
} /// <summary>
/// Delete record from BST recursively
/// </summary>
/// <param name="rootNode">root node</param>
/// <param name="Key">value of the element</param>
/// <returns></returns>
public TreeNode<T> DeleteRec(TreeNode<T> node, T key)
{
if (node == null)
{
return null;
} if (key.CompareTo(node.data) < )
{
node.leftChild = DeleteRec(node.leftChild, key);
}
else if (key.CompareTo(node.data) > )
{
node.rightChild = DeleteRec(node.rightChild, key);
}
else // find the node, node is the one to be deleted
{
if (node.leftChild == null)
{
return node.rightChild;
}
else if (node.rightChild == null)
{
return node.leftChild;
}
else
{
// need to handle the root?
T value = GetMinValue(node);
node.data = value;
node.rightChild = DeleteRec(node.rightChild, value);
}
} return node;
} private T GetMinValue(TreeNode<T> node)
{
if (node == null)
{
throw new Exception("node is null.");
} if (node.rightChild != null)
{
TreeNode<T> temp = node.rightChild;
while (temp.leftChild != null)
{
temp = temp.leftChild;
} return temp.data;
}
else
{
throw new Exception("successor node is not found");
}
}