c++ - 如何在不知道其父节点的情况下旋转子树

Question

我想向左旋转以节点 N 为根的子树(见左图)，而不操作其父节点 P。

P             P              P   
 \            |               \
  N           | R              R
 / \          |/              /
L   R         N              N
             /              /
            L              L

如果我想在一个函数中使用它，它将 N 作为参数:

void rotate_left(Node *node);

我最终会在中间的图上显示一棵树。问题是尽管旋转 P 仍然指向 N，而不是 R(左图)。如果函数 rotate_left() 没有指向 P< 的指针，如何在旋转结束时使 P 指向 R/?

我想到了三种方法:

1. 让 rotate_left() 获取指向节点 N 的指针的引用

   void rotate_left(Node * &node);
   

   然后调用rotate left()，将P的右子节点传递给它(即 N):

   rotate_left(P->right_child);
   

2. 将对象R放在末尾N的内存地址下 旋转

3. 将父 P 传递给 rotate_left():

   void rotate_left(Node *parent, Node *child);
   

解决方案(2)和(3)听起来不太好，在解决方案(1)中，您需要知道调用 rotate_left() 的函数中的父 P >.

Answer 1

解决方案 1 是您建议的三个解决方案中最好的一个。它或多或少等同于解决方案 3。我会使用它。在我看来，无论你在哪里调用 rotate_left，你都已经知道存储此指针的变量(父节点或 root)，所以它不会是一个传递其引用时出现问题。

解决方案 2(交换内容)将使任何已存在于树外部的指针无效。你必须非常小心；如果有这样的指针，请不要使用它。然而，这是对您的问题“如何在不知道 parent 的情况下旋转？”的唯一正确答案。

我想您不想在树中保留指向父节点的指针。如果您准备好这样做，一切都会容易得多。