c# - 在二叉搜索树中查找任意数据类型的值

Question

我有一个用 C# 编写的二叉树，其中的节点用 IComparable 数据定义。从我可以用我喜欢的任何数据类型填充树(尽管我只尝试一次用一种数据类型填充它)并按顺序执行查找深度等功能的意义上说，这一切都很好搜索、数树叶等

我正在尝试编写一个函数，使用递归算法在树中查找数据值。该算法找到数据，但在找到数据时不会停止。有一个异常(exception)——当数据位于根节点时。我不知道哪里出了问题。该函数报告它找到了数据，此时它应该返回该节点并退出，但它继续在子节点中查找。

感谢接受的答案，这是我的工作代码:

    private TreeNode findValueStartingAtNode(TreeNode node, IComparable value)
    {
        if (node == null)
        {
            return null;
        }

        int test = value.CompareTo(node.data);

        if (test < 0)
        {
            return findValueStartingAtNode(node.left_child, value);
        }
        else if (test > 0)
        {
            return findValueStartingAtNode(node.right_child, value);
        }
        else
        {
            return node;
        }
    }

---

代码:

    public TreeNode findValue(IComparable value)
    {
        TreeNode node = findValueStartingAtNode(this.root, value);
        if (node == null)
        {
            Console.WriteLine("value not found");
            return null;
        }
        else
        {
            return findValueStartingAtNode(this.root, value);
        }
    }

    private TreeNode findValueStartingAtNode(TreeNode node, IComparable value)
    {
        Console.WriteLine("looking for value {0}", value);

        if (node == null)
        {
            Console.WriteLine("node is null -- returning null");
            return null;
        }
        else if (value.CompareTo(node.data) == 0)
        {
            Console.WriteLine("value found at current node");
            Console.WriteLine("current node data is {0}", node.data);
            Console.WriteLine("done and returning node");
            return node;
        }
        else
        {
            Console.WriteLine("checking children");
            TreeNode left = findValueStartingAtNode(node.left_child, value);
            TreeNode right = findValueStartingAtNode(node.right_child, value);

            Console.WriteLine("the values are left: {0}, right: {1}", left.data, right.data);

            if (value.CompareTo(left.data) == 0)
            {
                Console.WriteLine("value found in left child");
                return left;
            }
            else if (value.CompareTo(right.data) == 0)
            {
                Console.WriteLine("value found in right child");
                return right;
            }
            else
            {
                Console.WriteLine("value not found in either child");
                Console.WriteLine("current node data is {0}", node.data);
                return null;
            }
        }
    }

---

输出:

C:\Users\abalter\Documents\CS273\TreeNode\TreeNode\bin\Debug>TreeNode.exe
looking for value 50
value found at current node
current node data is 50
done and returning node
looking for value 50
value found at current node
current node data is 50
done and returning node
(in main) value 50 found


looking for value 45
checking children
looking for value 45
value found at current node
current node data is 45
done and returning node
looking for value 45
checking children
looking for value 45
checking children
looking for value 45
node is null -- returning null
looking for value 45
checking children
looking for value 45
node is null -- returning null
looking for value 45
node is null -- returning null

Unhandled Exception: System.NullReferenceException: Object reference not set to an instance of an object.
   at TreeNode.BinaryTree.findValueStartingAtNode(TreeNode node, IComparable value) in c:\Users\abalter\Documents\CS273\TreeNode\TreeNode\BinaryTree.cs:line 220
   at TreeNode.BinaryTree.findValueStartingAtNode(TreeNode node, IComparable value) in c:\Users\abalter\Documents\CS273\TreeNode\TreeNode\BinaryTree.cs:line 218
   at TreeNode.BinaryTree.findValueStartingAtNode(TreeNode node, IComparable value) in c:\Users\abalter\Documents\CS273\TreeNode\TreeNode\BinaryTree.cs:line 217
   at TreeNode.BinaryTree.findValueStartingAtNode(TreeNode node, IComparable value) in c:\Users\abalter\Documents\CS273\TreeNode\TreeNode\BinaryTree.cs:line 218
   at TreeNode.BinaryTree.findValue(IComparable value) in c:\Users\abalter\Documents\CS273\TreeNode\TreeNode\BinaryTree.cs:line 186
   at TreeNode.Program.Main(String[] args) in c:\Users\abalter\Documents\CS273\TreeNode\TreeNode\Program.cs:line 36

C:\Users\abalter\Documents\CS273\TreeNode\TreeNode\bin\Debug>

Answer 1

二叉搜索树具有某些属性。这里重要的属性是，对于每个节点，该节点左子树中的所有内容都小于该节点的值，而其右子树中的所有内容都大于该节点的值(根据比较器)。

你只需要查看一个子树。使用该属性查找您要查找的项目:

private TreeNode findValueStartingAtNode(TreeNode node, IComparable value)
{
    if (node == null) return null;

    int comp = value.CompareTo(node.data);

    if (comp == 0) return node; //Found it
    if (comp < 0) return findValueStartingAtNode(node.left_child, value);  //The item must be in the left subtree
    return findValueStartingAtNode(node.right_child, value); // The item must be in the right subtree
}

奖励:这里不是递归方法，而是我自己实现的迭代搜索函数:(它也是通用的)

private BinaryTreeNode<T> Search(BinaryTreeNode<T> node, T item)
{
    if (node == null) return null;
    int c;
    while (node != null && (c = comparer.Compare(item, node.Value)) != 0)
        node = c < 0 ? node.Left : node.Right;
    return node;
}