在 C 中合并两个二叉树

Question

我正在尝试合并两个二叉树，这就是我想出的。我相信我的插入合并函数是正确的，我的和合并函数也有效......我的合并帮助程序有问题。我需要做的是后序，先左后右，但我不确定我所做的是否有意义。有什么想法吗？

  SparseNode * mergehelper(SparseNode* C_array_1, SparseNode * array_2)
        {
          if(array_2 ==NULL)
            {
              return(C_array_1);
            }
        C_array_1= SparseArray_InsertMerge(C_array_1, ((array_2->left)->index),((array_2->left)-
>value));
    C_array_1= SparseArray_InsertMerge(C_array_1, ((array_2->right)->index),((array_2->right)->value));
    }
    SparseNode* SparseArray_InsertMerge(SparseNode * array, int index, int value)
    {
     check(array);
      if(array ==NULL)
        { 
          return SparseNode_create(index, value);   
        } 
      if((array->index)==index)
      {
        if(array->value == -value)
          array= SparseArray_remove (array, array->index);
        else
          array->value += value;
        check(array);
        return array;
      }    
     if((array->index)>index)
        {   
          array->left = SparseArray_insert(array->left, index, value);  
        }      
      if((array->index)<index)
        {
          array->right = SparseArray_insert(array->right, index, value);
        }  
      check(array);
      return array;
    }
    /*
    post order traversal
    new insert for merge
    adapt for nonoverwriting
    do a tree traversal
    then add the node into the copied list in the work of the tree traversal
    in merge. copy array1. call mergehelper with copy. 
    in helper. if null return, then insert left and insert right. print function is similiar
     */
    SparseNode * SparseArray_merge(SparseNode * array_1, SparseNode * array_2)
    {
      SparseNode*Arr1_copy = copy(array_1);
      Arr1_copy =  mergehelper(Arr1_copy, array_2);
      return (Arr1_copy);
    }

Answer 1

合并两个二叉树的最简单方法是简单地使用树已经提供的功能：

• 遍历，提取值。
• 一种插入值的方法。

因此，解决方案就变成了（伪代码）：

def mergeTrees (tree1, tree2):
    valuePtr = tree2.getFirst();
    while valuePtr != NULL:
        tree1.addNode (valuePtr->value)
        valuePtr = tree2.getNextAfter (valuePtr)

之后，tree1将是两棵树的合并，您可以使用tree2做您想做的事。

现在这是基本思想 - 您可能想要处理重复删除或错误条件之类的事情，但这应该是一个足够好的开始，可以让您继续前进。当已发布的接口为您提供更简洁的方式时，使用数据结构的内部通常没有什么意义。