c - 二叉树的中序后继

Question

我正在学习如何在二叉搜索树中查找中序后继者我了解到:

1. 如果节点的右子树不为NULL，则后继位于右子树中。执行以下操作。

   转到右子树，返回右子树中键值最小的节点。

2. 如果节点的右子树为 NULL，则后继者是祖先之一。执行以下操作。

   使用父指针向上移动，直到看到一个节点，该节点是其父节点的左子节点。该节点的父节点是后继节点。

我不明白为什么如果右子树不为空我们必须返回最小值的节点，如果右子树为空我们必须找到一个作为其父节点的左子节点的节点。并且该节点的父节点是后继节点。

请帮忙..这是该算法的关键点。

struct node * inOrderSuccessor(struct node *root, struct node *n) 
{ 
  // step 1 of the above algorithm  
  if( n->right != NULL ) 
    return minValue(n->right); 

  // step 2 of the above algorithm 
  struct node *p = n->parent; 
  while(p != NULL && n == p->right) 
  { 
     n = p; 
     p = p->parent; 
  } 
  return p; 
}

Answer 1

考虑以下树: 4 2 61 3 5

首先考虑获取“3”的后继者，因为右子节点为空，所以您必须沿着树向上查找第一个祖先的父节点，即其父节点的左子节点。请记住，在二叉搜索树中，每个左子节点都将小于当前节点，而每个右子节点将大于当前节点。按照这种逻辑，任何左子节点的父节点都将大于该子节点。

现在考虑获取“4”的后继者，首先您将转到“6”，但由于它有一个左子节点，因此该左下降树中的任何节点都将在 4 和 6 之间，即该左子节点的最左子节点直接右子节点将是该节点的直接后继节点。