问题描述
我正在使用二进制搜索树遍历我插入的节点，我需要从中删除一个节点。
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)
{
}
}
}
推荐答案
基本上你需要做的是找到节点的父节点，如果有的话。找到父节点后，您将使用要删除的节点的子节点替换其现有链接（左侧或右侧）。有几种情况需要处理。请注意，如果这是您的要求，那么
不会考虑重新平衡树的过程。假设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删除节点功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！