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

Question

我想向左旋转以 node 为根的子树N（见左图）而不操纵其 parent P。

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

如果我愿意在一个函数中使用它，那将N作为一个参数：

void rotate_left(Node *node);

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

我想到了三种方法：

1. Letrotate_left()引用指向节点的指针N

   void rotate_left(Node * &node);
   

   然后调用，将其传递给（即 ）rotate left()的右孩子：PN

   rotate_left(P->right_child);
   

2. 将对象放在旋转结束时R的内存地址下N

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

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

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

Answer 1

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

解决方案 2（交换内容）将使树外已经存在的任何指针无效。你必须非常小心；如果有这样的指针，不要使用它。但是，这是您问题“如何在不知道父母的情况下旋转？”的唯一真正答案。

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