试图确定算法的目标

Question

我有这个算法，A和B是两个不同二叉树根的地址

每个节点都有一个值，指向左子树的指针和指向右子树的指针。

算法如下：

foo(A,B){

    if (A == NULL){
        return B;
    }
    if (B != NULL){
        if(A->value > B->value){
            return foo(B,A);
        }
        B->left = foo(A->right,B->left);
        A->right = B;
    }
    return A;
}

我确实理解了它是将树 B 合并到树 A 的右子树，但是我没有经理理解这些值的规律性。

希望你能帮我解决这个问题，谢谢！

Answer 1

我认为其目的是将两个排序的二叉树组合成一个排序的二叉树。

关键是比较if(A->value > B->value)。此分支确保 A 参数将始终包含子树合并点处的较小值，这会强制对结果进行排序。

由于 A->left 和 B->right 从未被此算法遍历，因此似乎对提供的两棵树有一些额外的要求。一种可能性是预计它们不会有重叠的范围。也就是说，一棵树的最小值必须大于另一棵树的最大值。或者需求可能是与此类似的其他事情，涉及子树的内容。或者值的类型可能仅限于两个值，例如布尔值。

试图确定算法的目标

Trying to identify the goal of an algorithm

c++

algorithm

tree

recursion

binary-tree