java - 二叉搜索树 - 删除所有大于特定值的整数

Question

我试图找出如何删除所有整数 a，使得 a > b 其中 a 是二叉搜索树中的任何元素，b 是阈值数BST 中的所有元素都会进行比较。到目前为止我已经:

public treeRemoveGreater(int x, BinaryNode node) {
       if (node.element > x) {
          //node.element accesses element of given node i.e. integer value
          remove(node.element);
       }
       else {
          //Traverse tree 
       }

我的问题是弄清楚如何相应地遍历树。我知道有一种有效的方法可以解决这个问题，因为不一定需要完全遍历树，我只是不确定如何继续。

Answer 1

考虑一下 BST 的属性。父节点等于或大于左侧的子节点，并且等于或小于右侧的子节点。因此，您需要找到 B 并删除其右侧的所有节点(只要确保右侧没有节点等于 B，因为您的条件都是 a > b)。就像 Makoto 所说的删除整个子树。