在BST中打印后续和前置

Question

我的问题如下：

我有一个带关键字的二元搜索树：a1

因此，您不能在树中按顺序遍历，并为每个节点找到后续节点/前置节点。因为这需要O（nh）时间，如果树是平衡的，那么整个树的时间将是O（nlgn）。




Answer 1

奥利说的顺序遍历是O（n）是对的，但你说的对，使用一般的后继/前置例程会增加算法的复杂性。因此：

一个简单的解决方案是使用按顺序遍历来遍历树，跟踪您最后一次获得右指向边的时间（例如，使用名为last_right_ancestor_seen的变量指向其父节点）和您看到的最后一个叶节点（例如，在last_leaf_seen（实际上，任何没有右子节点的节点）。每次您处理一个叶节点时，它的前身是last_right_ancestor，每次您遇到一个非叶节点时，它的前身是last_leaf_seen，您只需打印这两个。O（n）时间，O（1）空间。

希望足够清楚，如果不清楚，我可以给你画个图。

编辑：这是未经测试的，但可能是正确的：

walk(node* current, node* last_right_ancestor_seen, node* last_leaf_seen) {

    if(current->left != null) {
        walk(current->left, last_right_ancestor_seen, last_leaf_seen);
    }

    if(current->is_leaf()) {
            if(last_right_ancestor_seen != null)
                print(last_right_ancestor_seen->value, current->value);
    }
    else {
        print(last_leaf_seen->value, current->value);
    }

    if(current->right != null) {
        *last_right_ancestor_seen = *current;
        walk(current->right, last_right_ancestor_seen, last_leaf_seen);
    }
    else {
        *last_leaf_seen = *current;
    }

}

Answer 2

虽然您认为查找有序的后续或前置可能需要O（h）时间，但事实证明，如果您从BST中的最小值开始，并反复查找其后续，则无论树的形状如何，所完成的总工作量最终都会达到O（n）。

根据直觉，在迭代执行后续查找时，要考虑遍历树中的每条边的次数。具体来说，您将访问树中的每条边恰好两次：一次是在您下降到子树时，一次是在您访问了该子树中的每个节点后走出子树时。由于n节点树具有O（n）边，因此需要时间O（n）才能完成。

如果您对此持怀疑态度，请尝试编写一个简单的程序来验证它。我记得当我第一次听到这个结果时，我并不相信，直到我编写了一个程序来确认它为止。：-）

在伪代码中，逻辑如下所示：

1. 通过从根开始并重复跟随左子指针，直到不存在这样的指针，来查找树中的最小值

希望这有帮助！