二叉搜索树

public class BinarSearchTree
{private Node _tree;public BinarSearchTree(List<int> datas){if (datas != null){foreach (var item in datas){Insert(item);}}}/// <summary>/// 插入/// </summary>/// <param name="data"></param>public void Insert(int data){if (_tree == null){_tree = new Node(data);}else{var current = _tree;while (current != null){if (data > current.Data){if (current.Right == null){current.Right = new Node(data, current);break;}current = current.Right;}else if (data < current.Data){if (current.Left == null){current.Left = new Node(data, current);break;}current = current.Left;}}}}/// <summary>/// 删除/// </summary>/// <param name="data"></param>public void Delete(int data){var node = Find(data);if (node == null) return;if (node.Left == null && node.Right == null){if (node.Parent == null){_tree = null;}else{// 直接删除即可DeleteFromParent(node);}}else if (node.Left != null && node.Right != null){if (node.Parent == null){_tree = null;}else{// 查找右子树最大节点var minNode = node.Right;var currentNode = node.Right;while (currentNode != null){minNode = currentNode;currentNode = minNode.Left;}DeleteFromParent(minNode);ReplaceChildNode(node, minNode);}}else{// 有一个子节点，则直接将子节点挂到父节点下var child = node.Left ?? node.Right;if (node.Parent == null){_tree = child;}else{ReplaceChildNode(node, child);}}}private void ReplaceChildNode(Node node, Node newNode){newNode.Parent = node.Parent;if (node.Parent.Left == node){node.Parent.Left = newNode;}if (node.Parent.Right == node){node.Parent.Right = newNode;}}private void DeleteFromParent(Node node){if (node.Parent.Left == node){node.Parent.Left = null;}if (node.Parent.Right == node){node.Parent.Right = null;}}/// <summary>/// 查找/// </summary>/// <param name="data"></param>/// <returns></returns>public Node Find(int data){var current = _tree;while (current != null){if (data > current.Data){current = current.Right;}else if (data < current.Data){current = current.Left;}else{return current;}}return null;}
}public class Node
{public Node(int data, Node parent = null){this.Data = data;Parent = parent;}public int Data { get; set; }public Node Left { get; set; }public Node Right { get; set; }public Node Parent { get; set; }
}