在不使用父指针的情况下找到后继者[重复]

5 回答

• 0

  这应该工作：

  TREE-SUCCESSOR(T, x)
    if right[x] != NIL
      return TREE-MINIMUM(right[x])
    else
      return FIND-TREE-SUCCESSOR(root[T], x, NIL)
  
  FIND-TREE-SUCCESSOR(y, x, c)
    if y = x
      return c
    if key[x] < key[y]
      return FIND-TREE-SUCCESSOR(left[y], x, y)
    else
      return FIND-TREE-SUCCESSOR(right[y], x, c)
  

  FIND-TREE-SUCCESSOR 在 c （候选者）中保留我们向左转的最后一个节点 .

  回复于 2024-05-05T22:01:19+08:00
• 3

  受Sheldon解决方案的启发，这是该解决方案的非递归版本 .

  if (right[x]  != NIL)
      return min(right[x]);
  else
  {
      candidate = NIL;
      y = root; 
      while  (y!= x) // y is used as a probe 
          if (key[x] < key[y])
              {
              candidate = y;
              y = y ->left; 
               }
          else
              y = y->right;
  }
  return candidate;
  

  如果候选人== NIL，则x是树中的最大值，并且没有后继者 .

  回复于 2024-05-05T22:01:19+08:00
• 0

  我找到了一个优雅的解决方案，用于顺序后继，没有父指针 - > http://www.geeksforgeeks.org/archives/9999

  想法是

  1.如果节点具有右子树，则其后继子是右子树中的最小元素

  • 如果节点的右子树为空，则其后继是其祖先之一，可以在没有父指针的情况下自上而下找到，具有以下算法：

  最初，current_node是root，succ_node = null;

  case1：如果搜索元素小于current_node，则当前元素是潜在的后继者 - 在current_node处放置succ_node并将current_node移动到其左边节点（因为搜索元素在左子树中）

  case2：如果搜索元素大于current_node，则它不是潜在的后继者（较小的元素怎么可能是后继者？） . 所以不需要在这里放置succ_node，而是将current_node移到右边 .

  继续重复该过程，直到您达到null或元素本身并返回succ_node .

  回复于 2024-05-05T22:01:19+08:00
• 6

  如果您无法访问指向父节点的指针，那么您需要知道父亲是谁 . 如果你不知道，你怎么能在树上？

  回复于 2024-05-05T22:01:19+08:00
• 1

  递归Java解决方案可以采用以下方式：

  public Integer successor(Integer value) {
      Node n = succ(root, value, null);
      if (null != n) {
         return n.value;
      }
      return null;
  }
  
  private Node succ(Node n, Integer x, Node p) {
      if (null == n) {
          return null;
      }
  
      if (x < n.value) {
          return succ(n.left, x, n);
      } else if (x > n.value) {
          return succ(n.right, x, p);
      }
      if (null != n.right) {
          return min(n.right);
      }
      return p;
  }
  

  作为客户端，我们只需传递我们想要了解后继节点的节点的值 . 然后我们开始从根搜索，直到找到我们正在寻找的值 . 现在有两种情况：

  • 如果当前节点具有正确的子节点，则后继节点是当前节点的右子树中的最小元素

  • 否则，它是节点p（父指针），它只在我们离开树内时才更新

  回复于 2024-05-05T22:01:19+08:00