c++ - 修改二叉搜索树

Question

我正在尝试为二叉搜索树类编写一种方法来修改平衡的普通树，这使得树只有一侧有节点。

从元素在不平衡树中出现的顺序来看，在我看来，顺序遍历(左、中、右)之间似乎存在某种关系。

Answer 1

void unbalance(Node **pp) {
    Node *p;
    while ((p = *pp)) {
        if (!p->left) {
            pp = &p->right;
        } else {
            Node *tmp = p->left->right;
            *pp = p->left;
            p->left->right = p;
            p->left = tmp;
        }
    }
}

...
Node *tree = ...;
unbalance(&tree);

此代码基于@templatetypedef 的回答。它使用指向指针的指针来避免孤立节点(这也摆脱了 finalRoot，其唯一目的是避免孤立调用者传入的原始根)。

想法是沿着最右边的 Twig 走下树。如果永远没有左 child ，我们只进入 if 语句的第一部分，然后什么都不做就退出。

else 部分在有左子树时使用。在那种情况下，我们向右旋转树。

这具有从左子树向上拉一个节点的效果，即我们的左子树现在小了一个节点。我们重复这个直到左子树完全消失，此时我们再次进入 if 的第一部分。然后我们向下找到剩余的右子树并重复整个过程。

指针到指针在修改链表或树的结构时通常很有用。它们让我们直接在原始指针上工作，而不是复制它们。在这种情况下，赋值 *pp = ... 修改别处的指针(pp 指向的指针)。这要么是原始根(由调用者传入)，要么是树中的 right 指针之一(由 pp = &p->right 设置)。这种重新指向是必需的，因为 else 分支中的树旋转会打乱周围的节点，因此曾经是子树根的部分会进一步向下移动，而之前的左节点会被拉起成为新节点根。我们更新 *pp 以保留指针更高的不变性(调用者中的 tree 变量或父节点的 right 成员) 指向子树的(新)根。