我正在尝试在C＃中编写BST的删除功能。我有一些需要通过的NUnit测试。除了两个，其他所有人都通过了。我有两种情况下测试失败。
我需要为这两个树删除10个。但是失败了：
100，10，5
100，10，20
所以我猜我的代码没有将10拼接出来。错误是在RemoveNonRootNode方法中。尤其是使用“ else if”语句查看1个孩子的情况。
这是我的代码。感谢您的帮助！
public class BST
{
private BSTNode m_top;
private class BSTNode
{
private int m_data;
private BSTNode m_left;
private BSTNode m_right;
public int Data
{
get { return m_data; }
set { m_data = value; }
}
public BSTNode Left
{
get { return m_left; }
set { m_left = value; }
}
public BSTNode Right
{
get { return m_right; }
set { m_right = value; }
}
public BSTNode(int data)
{
m_data = data;
}
}
public void AddValue(int v)
{
if (m_top == null)
{
m_top = new BSTNode(v);
}
else
{
BSTNode cur = m_top;
while (true)
{
if (v < cur.Data)
{
if (cur.Left == null)
{
cur.Left = new BSTNode(v);
return;
}
else
cur = cur.Left;
}
else if (v > cur.Data)
{
if (cur.Right == null)
{
cur.Right = new BSTNode(v);
return;
}
else
cur = cur.Right;
}
else
throw new DuplicateValueException("Value " + v + " is already in the tree!");
}
}
}
public void Print()
{
Console.WriteLine("=== Printing the tree ===");
if (m_top == null)
Console.WriteLine("Empty tree!");
else
PrintInternal(m_top);
}
private void PrintInternal(BSTNode cur)
{
if (cur.Left != null)
PrintInternal(cur.Left);
Console.WriteLine(cur.Data);
if (cur.Right != null)
PrintInternal(cur.Right);
}
public bool Find(int target)
{
return FindNode(target) != null;
}
private BSTNode FindNode(int target)
{
BSTNode cur = m_top;
while (cur != null)
{
if (cur.Data == target)
return cur;
else if (target < cur.Data)
cur = cur.Left;
else if (target > cur.Data)
cur = cur.Right;
}
return null;
}
public void Remove(int target)
{
// if the tree is empty:
if (m_top == null)
return;
if (m_top.Data == target)
{
RemoveRootNode(target);
}
else
{
RemoveNonrootNode(target);
}
}
private void RemoveNonrootNode(int target)
{
BSTNode cur = m_top;
BSTNode parent = null;
//First, find the target node that we need to remove
// we'll have the 'parent' reference trail the cur pointer down the tree
// so when we stop, cur is the node to remove, and parent is one above it.
while (cur!= null && cur.Data != target)
{
parent = cur;
if (target > cur.Data)
cur = cur.Right;
else
cur = cur.Left;
}
// Next, we figure out which of the cases we're in
// Case 1: The target node has no children
if (cur.Left == null && cur.Right == null)
{
if (parent.Left==cur)
parent.Left = null;
else
parent.Right = null;
}
// Case 2: The target node has 1 child
// (You may want to split out the left vs. right child thing)
else if (cur.Left == null)
{
BSTNode cur2 = cur;
cur = cur.Right;
cur2 = null;
return;
}
else if (cur.Right == null)
{
BSTNode cur2 = cur;
cur = cur.Right;
cur2 = null;
return;
}
// Case 3: The target node has 2 children
BSTNode removee = FindAndRemoveNextSmallerValue(target, cur);
cur.Data = removee.Data;
return;
}
private void RemoveRootNode(int target)
{
// If we're here, it's because we're removing the top-most node (the 'root' node)
// Case 1: Root has no children
if (m_top.Left == null && m_top.Right == null)
{
m_top = null; // Therefore, the tree is now empty
return;
}
// Case 2: Root has 1 child
else if (m_top.Left == null)
{
// 1 (right) child, OR zero children (right may also be null)
m_top = m_top.Right; // Right is null or another node - either way is correct
return;
}
else if (m_top.Right == null)
{
// If we're here, Left is not null, so there MUST be one (Left) Child
m_top = m_top.Left;
return;
}
// Case 3: Root has two children - this is where it gets interesting :)
else
{
// 2 children - find (and remove) next smaller value
// use that data to overwrite the current data.
BSTNode removee = FindAndRemoveNextSmallerValue(target, m_top);
m_top.Data = removee.Data;
return;
}
}
/// <summary>
/// This method takes 1 step to the left, then walks as far to the right
/// as possible. Once that right-most node is found, it's removed & returned.
/// Note that the node MAY be immediately to the left of the <B>startHere</B>
/// parameter, if startHere.Left.Right == null
/// </summary>
/// <param name="smallerThanThis"></param>
/// <param name="startHere"></param>
/// <returns></returns>
private BSTNode FindAndRemoveNextSmallerValue(int smallerThanThis, BSTNode startHere)
{
BSTNode parent = startHere;
BSTNode child = startHere.Left;
if (child.Data == smallerThanThis)
{
child = null;
}
while (child.Right != null)
{
parent = child;
child = child.Right;
}
parent = child;
child = null;
return parent;
}
// Given the value of a node, find (and remove) the predessor node in the tree
// returns the value of the predecessor node, or Int32.MinValue if no such value was found
public int TestFindAndRemoveNextSmallest(int sourceNode)
{
BSTNode startAt = this.FindNode(sourceNode);
// sourceNode should == startAt.Data, unless startAt is null)
BSTNode removed = FindAndRemoveNextSmallerValue(sourceNode, startAt);
if (removed != null)
return removed.Data;
else
return Int32.MinValue;
}
}
乍一看，似乎有这个错误：
else if (cur.Left == null)
{
BSTNode cur2 = cur;
cur = cur.Right;
cur2 = null;
return;
}
else if (cur.Right == null)
{
BSTNode cur2 = cur;
// cur = cur.Right; // THIS SHOULD BE .Left, because .Right is NULL
cur = cur.Left; // THIS IS THE FIX
cur2 = null;
return;
}
但是您的实际问题是；将cur引用更新为其他内容不会更改指向其父级持有的同一对象（cur）的指针。实际上，您在案例1中做对了，但是在案例2中却有所遗漏。完整的解决方法是：（仅修复失败的测试。不再承诺）。
// Case 2: The target node has 1 child
// (You may want to split out the left vs. right child thing)
else if (cur.Left == null)
{
if (parent.Left == cur)
{
parent.Left = cur.Right;
}
else
{
parent.Right = cur.Right;
}
return;
}
else if (cur.Right == null)
{
if(parent.Left == cur)
{
parent.Left = cur.Left;
}
else
{
parent.Right = cur.Left;
}
return;
}