Функция удаления бинарного дерева поиска - PullRequest
Новая
       27

Функция удаления бинарного дерева поиска

1 голос
/ 10 марта 2019

Я создаю функцию удаления для бинарного дерева поиска и столкнулся с вопросом.

private BinaryTreeNode<T> BinaryDelete(BinaryTreeNode<T> root, T value)
    {
        if (root == null)
        {
            return root;
        }

        int compareResult = value.CompareTo(root.Value);

        if (compareResult < 0)
        {
            root.Left = this.BinaryDelete(root.Left, value);
        }
        else if (compareResult > 0)
        {
            root.Right = this.BinaryDelete(root.Right, value);
        }
        else
        {
            if (root.Left == null)
            {
                return root.Right;
            }
            else if (root.Right == null)
            {
                return root.Left;
            }

            root.Value = this.FindMinLeftLeaf(root.Left);

            root.Left = this.BinaryDelete(root.Left, root.Value);
        }

        return root;
    }

    private T FindMinLeftLeaf(BinaryTreeNode<T> root)
    {
        while (root.Left != null)
        {
            root = root.Left;
        }

        return root.Value;
    }

Итак, в основном root.Value = this.FindMinLeftLeaf (root.Left);ищет в левом потомке корня.Пока я учился, я видел несколько примеров, когда поиск проводится в правильном ребенке, так что это немного сбивает с толку.Короче говоря: эти две строки должны быть похожи на 

root.Value = this.FindMinLeftLeaf(root.Right);
root.Right= this.BinaryDelete(root.Right, root.Value)

или как у меня в первом примере?

...