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

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 所说，删除整个子树。

Answer 2

                      |
                 +----8----+
                 |         |
            +----3----+    10------+
            |         |            |
            1     +---6---+    +---14  
                  |       |    |
                  4       7    13

考虑这个 BST，如果你想删除大于 6 的元素，那么你必须删除

“6”的右边child/sub-tree，所以可以消去
但是你得从根开始遍历。所以检查根大于你的 'a' （在这种情况下 8>6），
将左边的 sub-tree 作为主树（根为 '3'）并将根与你的 'a' 进行比较，如果它仍然更大则重复步骤 2（或）
如果新的根小于'a'然后向右遍历child（这里3！> 6，所以从这里开始你不会碰到根）
然后检查右节点等于'a'在这种情况下，所以去它的右节点检查你是否有重复的元素等于a（如果存在则遍历该节点并将它的右边 child 设置为 'null'
如果向右移动时发现一个大于 6 的元素（在这种情况下，如果你在 6 的位置找到 7，在 4 的位置找到 6），那么你必须使子树的根及其左树
```
     |                                 |
+----7----+                            6
|         |          ---->     
6         7
```

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

Binary Search Tree - Removing all ints greater than certain value

java

binary-search-tree

data-structures