二叉搜索树实现.似乎无法添加新值和搜索现有值

Question

C# 中的泛型实现。一个非常快速的例子，所以显然代码可以改进很多，但是目前我想让它以当前的形式工作。

添加新节点或删除现有节点不起作用。在驱动程序中调用print()方法时：

BinarySearchTree<int> testTree = new BinarySearchTree<int>(1);
Console.WriteLine("Binary search tree contains 0: " + testTree.exists(0));
Console.WriteLine("Binary search tree contains 1: " + testTree.exists(1));
Console.WriteLine("Binary search tree contains 2: " + testTree.exists(2));
testTree.add(2);
Console.WriteLine("Binary search tree contains 2: " + testTree.exists(2));
testTree.remove(1);
Console.WriteLine("Binary search tree contains 1: " + testTree.exists(1));
testTree.print();

上述控制台输出：

Binary search tree contains 0: False
Binary search tree contains 1: True
Binary search tree contains 2: False
Binary search tree contains 2: False
Binary search tree contains 1: True
1

在适当的方法上设置断点进行检查，没有更接近找到问题。

此类的代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace BinaryTree
{
public class BinarySearchTree<T> where T : IComparable
{
#region private members
private class Node
{
public T value;
public Node left;
public Node right;
}
private Node rootNode;
private void insert(Node root, Node node)
{
if (root==null)
{
root = node;
}
else if (isLessThan(node.value,root.value))
{
insert(node.left, node);
}
else if (isGreaterThan(node.value,root.value) || (isEqual(root.value,node.value)))
{
insert(node.right, node);
}
}
private void displayInOrder(Node node)
{
if (node != null)
{
displayInOrder(node.left);
Console.WriteLine(node.value);
displayInOrder(node.right);
}
}
#region comparison helper functions
private bool isGreaterThan(T a, T b)
{
return a.CompareTo(b) > 0;
}
private bool isLessThan(T a, T b)
{
return a.CompareTo(b) < 0;
}
private bool isEqual(T a, T b)
{
return a.CompareTo(b) == 0;
}
#endregion
#endregion
// ctor
public BinarySearchTree(T rootValue)
{
rootNode = new Node();
rootNode.value = rootValue;
rootNode.left = null;
rootNode.right = null;
}
public void add(T value)
{
// first create a new node. Eventually, it will be added to the tree.
Node newNode = new Node();
newNode.value = value;
newNode.left = null;
newNode.right = null;
// give this node to the insert method, which will traverse the tree until it finds the correct place to insert it.
insert(rootNode, newNode);
}
public bool exists(T value)
{
Node node = rootNode;
while (node!=null)
{
if (isEqual(node.value,value))
{
return true;
}
else if (isLessThan(value,node.value))
{
node = node.left;
}
else if (isGreaterThan(value,node.value))
{
node = node.right;
}
}
return false;
}
public void remove(T value)
{
Node node = rootNode;
while (node!=null)
{
if (isEqual(node.value,value))
{
node = null;
}
else if (isLessThan(node.value, value))
{
node = node.left;
}
else if (isGreaterThan(node.value, value) || (isEqual(value, node.value)))
{
node = node.right;
}
}
}
public void print()
{
displayInOrder(rootNode);
}   
}
}

Answer 1

您的问题是您正在为null赋值，而该值根本不是引用。

null 关键字是表示 null 引用的文本，该引用不引用任何对象。 null 是引用类型变量的默认值。普通值类型不能为 null，但可为 null 的值类型除外。

在这一行代码中，node.right的值为 null。

insert(node.right, node);

因此，您将节点分配给一个根本没有引用的空值。

我的建议是像这样更改插入代码：

声明方向枚举

public enum Direction {
Left,
Right
}

使用枚举更新正确的引用

private void insert(Node root, Node node)
{
if (root==null)
{
root = node;
}
else if (isLessThan(node.value,root.value))
{
insert(root, node, Direction.Left);
}
else if (isGreaterThan(node.value,root.value) || (isEqual(root.value,node.value)))
{
insert(root, node, Direction.Right);
}
}
private void insert(Node root, Node node, Direction direction)
{
if (direction == Direction.Left)
{
// You are actually updating the reference left of root node
root.left = node;
}
else if (direction == Direction.Right)
{
// You are actually updating the reference right of root node
root.right = node;
}
}

删除逻辑几乎相同。检查评论

// I am declaring a local reference to a Node
Node node = rootNode;
while (node!=null)
{
if (isEqual(node.value,value))
{
// I am updating the local reference to null
// I am not setting the left or right value reference to null
// So that I won't be able to find it again
node = null;
}

请注意，当您分离一个引用时，您必须重建整个树。如果通过在左侧设置 null 来分离链接，则所有左侧值也将分离。