二进制搜索树查找是否存在值

Question

尝试学习树节点...

    Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.
Write a function that checks if a given binary search tree contains a given value.
For example, for the following tree:
n1 (Value: 1, Left: null, Right: null)
n2 (Value: 2, Left: n1, Right: n3)
n3 (Value: 3, Left: null, Right: null)
Call to Contains(n2, 3) should return true since a tree with root at n2 contains number 3.

到目前为止iv ...

 public class BinarySearchTree
    {
        public static bool Contains(Node root, int value)
        {
            foreach (var v in root)
            {
                if (root.Value == value)
                {
                    //value found return true
                }
            }
        }
        public static void Main(string[] args)
        {
            Node n1 = new Node(1, null, null);
            Node n3 = new Node(3, null, null);
            Node n2 = new Node(2, n1, n3);
            Console.WriteLine(Contains(n2, 3));
        }
    }

，但root将其标记为不可用，如果我扎根。我得到了tostring，value，左，右的选项。

我不能像列表那样通过节点迭代吗？如何检查是否在root中找到值？谢谢你

---

更新啊，好的...谢谢你的回复juharr，所以我将代码更新到...

public static bool Contains(Node root, int value)
            {
                    if (root.Value == value)
                    {
                        return true;
                    }
                    else if (root.Value > value)
                    {
                        if (root.Right == null)
                        {
                            Contains(root.Left, value);
                        }
                        Contains(root.Right, value);
                    }
                    else //(root.Value < value)
                    {
                        if (root.Left == null)
                        {
                            Contains(root.Right, value);
                        }
                        Contains(root.Left, value);
                    }
                return false;
            }

但是，在第二个环上，圆形根是无效的，并导致崩溃吗？

Answer 1

你很接近，但这是您实际想要的

public static bool Contains(Node root, int value)
{
    if (root == null) return false;
    if (root.Value == value) return true;
    if (root.Value > value) return Contains(root.Left, value);
    return Contains(root.Right, value);
}

因此，如果root是null，则没有数字，因此您返回false。然后，您检查值是否匹配并返回true（如果确实如此）。然后，如果root的值较大，则返回左子树的递归调用结果。最后，您只需返回右子树的递归调用结果，因为此时您知道根值较小。

这是进行搜索的一种非收回方法

public static bool Contains(Node root, int value)
{
    while(root != null)
    {
        if(root.Value == value) return true;
        if(root.Value > value) root = root.Left;
        else root = root.Right;
    }
    return false;
}

在这里，我们循环直到击中null节点，然后根据比较将root设置为Left或Right，或者如果Value是匹配的，则立即返回true。如果我们将其取出循环，则找不到该值。

Answer 2

我不能像列表那样通过节点迭代吗？

you 可以通过BST迭代 - 使用堆栈通过子节点会有所帮助（如此处所示）。因此，您可以将root的孩子扔进堆栈，然后将其值与您的目标value进行比较。

话虽如此，可以说更直观的方法将是递归的 - 从理论上讲，您将检查当前节点的值，然后递归地调用Contains-将当前节点的right或left孩子传递，直到找到目标Value5，或不。

在这两种方法中，您都需要利用您在问题中指出的BST的优势：

二进制搜索树（BST）是一个二进制树，其中每个节点的值更大或等于该节点的左子树中所有节点的值。

考虑到这一点，您可以通过"切断"您知道您不需要检查的值来在O(log n)时间内实现它（由于当前节点的值与目标value相关）。