BST删除节点功能 [英] BST Deletion node function

问题描述

我正在使用二进制搜索树遍历我插入的节点，我需要从中删除一个节点。 

i am using Binary Search Tree in traverse the nodes that i inserted and i need to delete a node from it. 

我不知道如何删除一个节点令人困惑，我找不到任何来源向我解释任何形式的帮助将不胜感激。 

i don't know how to delete a node it is confusing and i couldn't find any source to explain it to me any kind of help would be appreciated. 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DeletionBST
{
    class Program
    {
        static void Main(string[] args)
        { //insert nodes
            Tree BST = new Tree();
            BST.Insert(30);
            BST.Insert(35);
            BST.Insert(57);
            BST.Insert(15);
            BST.Insert(63);
            BST.Insert(49);
            BST.Insert(89);
            BST.Insert(77);
            BST.Insert(67);
            BST.Insert(98);
            BST.Insert(91);
            Console.WriteLine("Inorder Traversal : ");
            BST.Inorder(BST.ReturnRoot());
            Console.WriteLine(" ");
            Console.WriteLine();
            Console.WriteLine("Preorder Traversal : ");
            BST.Preorder(BST.ReturnRoot());
            Console.WriteLine(" ");
            Console.WriteLine();
            Console.WriteLine("Postorder Traversal : ");
            BST.Postorder(BST.ReturnRoot());
            Console.WriteLine(" ");
            Console.ReadLine();
        }
    }
    class Node
    {
        public int item;
        public Node left;
        public Node right;
        public void Display()
        {
            Console.Write("[");
            Console.Write(item);
            Console.Write("]");
        }
    }
    class Tree
    {
        public Node root;
        public Tree()
        {
            root = null;
        }
        public Node ReturnRoot()
        {
            return root;
        }
        public void Insert(int id)
        {
            Node newNode = new Node();
            newNode.item = id;
            if (root == null)
                root = newNode;  //see if the node is empty insert that value in the current node
            else
            {
                Node current = root;
                Node parent;
                while (true)
                {
                    parent = current;
                    if (id < current.item)
                    {
                        current = current.left;
                        if (current == null)
                        {
                            parent.left = newNode;
                            return;
                        }
                    }
                    else
                    {
                        current = current.right;
                        if (current == null)
                        {
                            parent.right = newNode;
                            return;
                        }
                    }
                }
            }
        }
        public void Preorder(Node Root)
        {
            if (Root != null)
            {
                Console.Write(Root.item + " ");
                Preorder(Root.left);
                Preorder(Root.right);
            }
        }
        public void Inorder(Node Root)
        {
            if (Root != null)
            {
                Inorder(Root.left);
                Console.Write(Root.item + " ");
                Inorder(Root.right);
            }
        }
        public void Postorder(Node Root)
        {
            if (Root != null)
            {
                Postorder(Root.left);
                Postorder(Root.right);
                Console.Write(Root.item + " ");
            }
        }
       // public void Delete(Node root)
        {

        }
    }
}

推荐答案

完全取决于你如何实施你的BST。在您的情况下，节点具有潜在的左右节点。因此，如果删除该节点，则必须更新树。更新BST记录在几个
地点中。

基本上你需要做的是找到节点的父节点，如果有的话。找到父节点后，您将使用要删除的节点的子节点替换其现有链接（左侧或右侧）。有几种情况需要处理。请注意，如果这是您的要求，那么
不会考虑重新平衡树的过程。假设R是要删除的节点，P是父节点。 R是存储在P的左侧还是右侧是不相关的，但我们将在此讨论中假设。

Basically what you need to do is find the node's parent, if any. Once you find the parent node you will be replacing it's existing link (left or right) with a child of the node being deleted. There are a couple of scenarios to deal with. Note that this does not take into account the process of rebalancing the tree, if that is a requirement for you. Assume R is the node to delete and P is the parent node. Whether R is stored in the left or right portion of P is not relevant but we'll assume left for this discussion.

1 - 节点没有左或右子节点。  R {left = null，right = null}

I 在这种情况下，可以删除节点，并将父节点的链接设置为null。 P {left = null}

1 - The node has no left or right children.  R { left = null, right = null }
In this case the node can be removed and the parent node's link set to null. P { left = null }

2 - 节点有一个左或右子，但不是两个。 R {left = A，right = null}


由于只有一个孩子，孩子成为父节点链接到的节点。  P {left = A}

2 - The node has either a left or right child but not both. R { left = A, right = null }
Since there is only 1 child that child becomes the node that the parent node links to.  P { left = A }

3 - 该节点同时具有左右子节点。 R {left = A，right = B}，B {left = C}，C {left = null}

3 - The node has both a left and right child. R { left = A, right = B }, B { left = C }, C { left = null }

在这种情况下，A或B必须升级到P.你选择哪一个并不重要，但我认为正确的节点是最常见的。 B成为父P {left = B}中的链接的节点。但是你不能丢失左节点（A），以便节点
现在成为新根节点（B）的最左边的子节点。所以你跟着左边的孩子，直到找到一个空C {left = A}。此时树不平衡，但排序仍然完好。

In this case either A or B has to be promoted up to P. It doesn't really matter which one you choose but I think the right node is the most common. B becomes the node the link in the parent P { left = B }. But you cannot lose the left node (A) so that node now becomes the left-most child of the new root node (B). So you follow the left children down until you find a null C { left = A }. At this point the tree is not balanced but the sorting is still intact.

这篇关于BST删除节点功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！