PZY

前文二叉查找树图解以图文相结合的方式，对二叉查找树添加、查找和删除数据结点底层原理进行解读，本文来聊聊二叉查找树添加、查找和删除数据结点算法实现，采用 C# 语言进行呈现。

首先，根据二叉树的定义，构建其结点模型，代码如下：

public class BinaryTreeNode
{
    /// <summary>
    /// node data
    /// </summary>
    public int Data { get; set; }

    /// <summary>
    /// left child
    /// </summary>
    public BinaryTreeNode LeftChild { get; set; }

    /// <summary>
    /// right child
    /// </summary>
    public BinaryTreeNode RightChild { get; set; }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="data">node data</param>
    public BinaryTreeNode(int data)
    {
        Data = data;
    }
}

接下来，根据二叉查找树的性质，定义其模型，分别实现二叉查找树添加、查找和删除数据结点算法。

添加数据结点

添加数据结点的逻辑：从二叉查找树的顶端结点开始寻找添加数字的位置，将要添加的数字与结点中的值（假设为 x）进行比较，小于 x 则往左移（左子树），大于 x 则往右移（右子树）。

关键实现算法如下：

public BinaryTreeNode Insert(BinaryTreeNode node, int data)
{
    if (node == null)
    {
        return new BinaryTreeNode(data);
    }

    if (data < node.Data)
    {
        //If 'data' is less than the value of the current node,
        //it indicates that 'data' should be inserted into the left subtree of the node
        node.LeftChild = Insert(node.LeftChild, data);
        return node;
    }

    if (data > node.Data)
    {
        //If 'data' is greater than the value of the current node,
        //it indicates that 'data' should be inserted into the left subtree of the node
        node.RightChild = Insert(node.RightChild, data);
        return node;
    }

    //the target node is found, insert data fails
    throw new ArgumentException("There is a node value equal to the parameter", nameof(data));
}

查找数据结点

查找数据结点的逻辑：在二叉查找树中查找目标结点，是从根结点出发，将二叉查找树结点中的值逐个与目标数据比较，小于该结点的值则往该结点左子树查找，大于则往该结点右子树查找。

关键实现算法如下：

public BinaryTreeNode Search(BinaryTreeNode binaryTreeNode, int data)
{
    if (binaryTreeNode == null || data == binaryTreeNode.Data)
    {
        return binaryTreeNode;
    }

    if (data < binaryTreeNode.Data)
    {
        return Search(binaryTreeNode.LeftChild, data);
    }

    return Search(binaryTreeNode.RightChild, data);
}

删除数据结点

在二叉查找树上搜索（删除）数据对应的结点，如找到则删除该结点，反之则删除失败。删除二叉查找树中已有的结点，必须确保整棵树还是二叉查找树，即删除的同时需要妥善处理它的左、右子树。相应地，实现删除二叉查找树数据结点算法实现也较为复杂，可分两步进行实现。

首先是二叉查找树上搜索（删除）数据对应的结点，如找到则删除该结点，反之则删除失败。实现算法如下：

public BinaryTreeNode Delete(BinaryTreeNode binaryTree, int data)
{
    if (binaryTree == null)
    {
        //The node to be deleted does not exist
        throw new ArgumentException("The node to be deleted does not exist.");
    }

    if (data == binaryTree.Data)
    {
        //Find the target node, delete it and return the tree after deleting the node.
        return Delete(ref binaryTree);
    }

    if (data < binaryTree.Data)
    {
        binaryTree.LeftChild = Delete(binaryTree.LeftChild, data);
        return binaryTree;
    }

    binaryTree.RightChild = Delete(binaryTree.RightChild, data);
    return binaryTree;
}

其次是删除找到的二叉查找树结点，并妥善处理结点删除后二叉查找树的左、右子树。其处理逻辑可以参考二叉查找树图解中，关于删除数据结点部分的解读。实现算法如下：

private static BinaryTreeNode Delete(ref BinaryTreeNode treeNode)
{
    //1. If the node to be deleted is a leaf node (that is to say, there is no child node),
    // just delete the node directly, the whole tree is still a binary search tree.
    if (treeNode.LeftChild == null && treeNode.RightChild == null)
    {
        treeNode = null;
        return treeNode;
    }

    //2. If the node to be deleted has two child nodes, first delete the target node,
    // then find the largest node in the left subtree of the deleted node,
    // and move the largest node to the position of the deleted node.
    if (treeNode.LeftChild != null && treeNode.RightChild != null)
    {
        BinaryTreeNode parentPreNode = treeNode;        //The parent node of the predecessor node
        BinaryTreeNode preNode = treeNode.LeftChild;    //predecessor node

        //find the predecessor node of the node to be deleted
        while (preNode.RightChild != null)
        {
            parentPreNode = preNode;
            preNode = preNode.RightChild;
        }

        // Change the value of the node to be deleted.
        treeNode.Data = preNode.Data;
        if (parentPreNode != treeNode)
        {
            //If the parentPreNode and deleteNode nodes are different,
            //the parentPreNode after deleting the preNode will have no right subtree,
            //so the left subtree of preNode is used as the right subtree of parentPreNode
            parentPreNode.RightChild = preNode.LeftChild;
        }
        else
        {
            //If the parentPreNode and deleteNode nodes are the same,
            //the parentPreNode (deleteNode) after deleting the preNode will have no left subtree,
            //so the left subtree of preNode is used as the left subtree of parentPreNode (deleteNode)
            parentPreNode.LeftChild = preNode.LeftChild;
        }

        return treeNode;
    }

    //3. If the node to be deleted has only one child node, then delete the target node first,
    // and then move the child node to the position of the deleted node.
    if (treeNode.LeftChild != null)
    {
        treeNode = treeNode.LeftChild;
        return treeNode;
    }

    if (treeNode.RightChild != null)
    {
        treeNode = treeNode.RightChild;
        return treeNode;
    }

    return treeNode;
}

二叉查找树删除结点算法的关键，是如何找到被删除结点的前驱结点，并将前驱结点转移到被删除结点的位置进行“补空”，上述代码中也提供了算法说明。

二叉查找树算法实现完整代码地址：前往 github。

（完）