思路
二叉搜索树的插入
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) <
0)
{
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) <
0)
{
node.leftChild =
DeleteRec(node.leftChild, key);
}
else if (key.CompareTo(node.data) >
0)
{
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");
}
}
转载于:https://www.cnblogs.com/xuyanran/p/8468787.html
相关资源：JAVA上百实例源码以及开源项目
