c# - BST算法中的StackOverFlowException

我一直在尝试将contains方法实现到我的bstree类中，该类将接受一个值，然后检查所有节点，看看它是否包含在树中。我认为算法是正确的，但是我不知道为什么我在第一个if语句中总是得到stackoverflowexception。有什么想法吗？

public Boolean Contains(T item)
    {
      Node<T> node = root;
      return contains(root, item);
    }



    private Boolean contains(Node<T> node, T item)
    {
      if (item.CompareTo(root.Data) == 0)
      {
        return true;//return 0 if found
      }
      else
      {
        if (item.CompareTo(root.Data) > 0)
        {
          //root = node.Left;
          Node<T> left = root.Left;
          return(contains(root, item));
        }
        else
        {
          if (item.CompareTo(root.Data) < 0)
          {
            //root = node.Right;
            Node<T> right = root.Right;
            return(contains(root, item));
          }
          else
          {
            return false;//return 1 if not found
          }
        }
      }
    }

最佳答案

代码的问题是将错误的节点传递到递归调用中。例如，假设您的元素比树中的所有元素都小然后，在第一个递归调用中，您将看到以下语句：

Node<T> left = root.Left;
return(contains(root, item));

这意味着递归在根节点上，而不是在左子节点上。因此，在下一次迭代中，您将发现元素小于根的右子元素，因此您将再次执行完全相同的语句，递归地重复调用相同的函数，直到堆栈空间用完为止。
要解决这个问题，您应该将上面的代码改为

Node<T> left = node.Left;
return(contains(left, item));

这表示查看当前节点的左子树，而不是根节点本身。类似地，您将需要为右分支更新相应的大小写。
最后，要完成这项工作，您需要向递归函数添加一个基本情况，该函数处理树null的情况，这可能是因为您已经离开了树，也可能是树开始是空的我把这个留作练习:-)

关于c# - BST算法中的StackOverFlowException，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7005632/