試圖找出一個算法的目標

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從來沒有被這個算法穿過，所以似乎對所提供的兩棵樹有一些額外的要求。一種可能是他們預計不會有重疊的範圍。也就是說，一棵樹的最小值必須大於另一棵的最大值。或者需求可能是一些其他類似於涉及子樹內容的事情。或者，值的類型可能僅限於兩個值，如布爾值。