修改二进制搜索树

Question

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

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

Answer 1

迭代执行此操作的一种方法是使用树旋转。想法大致是这样的：

1. 如果根节点具有左子节点，请向右旋转根节点
2. 否则，根节点没有左子节点。向右下降并重复此过程

在伪代码中：

Node finalRoot = null;
while (currNode != null) {
    if (currNode.left != null) {
        currNode = rotateRight(currNode);
    } else {
        if (finalRoot == null) finalRoot = currNode;
        currNode = currNode.right;
    }
}
return finalRoot;

这种方法改编自第一步的Day Stout-Warren算法，它在时间O（n）中运行。

Answer 2

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);

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

这个想法是沿着最右边的树枝沿着树走下来。如果从来没有剩下任何孩子，我们只输入if语句的第一部分并退出而不做任何事情。

这具有从左侧子树上拉一个节点的效果，即我们的左侧子树现在小了一个节点。我们重复此操作，直到左侧子树完全消失，此时我们再次输入 if 的第一部分。然后我们转到剩余的右侧子树并重复整个事情。

指针到指针在修改链表或树的结构时通常很有用。它们让我们直接处理原始指针，而不是复制它们。在这种情况下，赋值 *pp = ... 在其他地方修改指针（pp 指向的指针）。这是原始根（由调用方传入），或者树中的正确指针之一（由 pp = 设置）