c# - BST算法中的StackOverFlowException

Question

我一直在尝试在我的 BSTree 类中实现一个 Contains 方法，该方法将接受一个值，然后检查所有节点以查看它是否包含在树中。我认为该算法是正确的，但我不知道为什么我在第一个 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
          }
        }        
      }
    }

Answer 1

您的代码存在的问题是您将错误的节点传递给递归调用。例如，假设您的元素小于树中的所有元素。然后在第一个递归调用中，你会遇到这个语句:

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

这意味着您递归根，而不是左 child 。因此在下一次迭代中，你会发现该元素小于根的右 child ，因此你将再次执行完全相同的语句，重复递归调用相同的函数，直到用完堆栈空间。

要解决这个问题，您应该将上面的代码更改为

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

这表示要查看当前节点的左子树，而不是根节点本身。同样，您需要更新正确分支的相应案例。

最后，要完成此操作，您需要向递归函数添加一个基本情况，以处理树为 null 的情况，无论是因为您离开了树还是这棵树一开始是空的。我会把它留作练习。 :-)