c - 大于 BST 中某个数字的节点之和

Question

对于C语言中不可更改的二叉搜索树结构:

struct bstnode {
  int item;
  struct bstnode* left;
  struct bstnode* right;
};

struct bst {
  struct bstnode* root;
};

我们怎样才能找到大于数字(num)的值的总和？
(我们无法遍历整个树或将此 bst 转换为数组)。
函数声明为:

int sum_greater(struct bst * t, int num)

基本上，我的方法是使用递归:
当 num 等于当前节点中的 item 时，我们对这棵树的右侧部分求和。
当num大于当前节点中的item并且node->right大于num时，我们对这棵树的右侧部分求和。
但我不知道如何处理当前节点小于num的情况。

Answer 1

你把事情搞得太复杂了。您的基本情况是命中叶节点(您已经知道如何处理)。您有三种递归情况:

current > num
    result = current +
             recur on right child +
             recur on left  child
current = num
    result = current +
             recur on right child
current < num
    result = recur on right child

return result

您所能做的就是剪掉发现的太小的左子树。不要浪费精力展望 future :递归会很好地处理这个问题。

请注意，您不能提前停止对右 child 值的依赖:该 child 很可能拥有具有任意大值的右后代。