二叉搜索树查找值是否存在

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.

到目前为止,我得到......

 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被标记为不可用,如果我做root.我得到选项tostring,value,left,right.

我可以不像列表那样遍历节点吗？如何检查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.然后,如果the的值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基于比较,或者true如果Value匹配则立即返回.如果我们将其设置为循环,则找不到该值.