0

我正在尝试合并两个二叉树，这就是我想出的。我相信我的 Insertmerge 函数是正确的，并且我的和 merge 函数也可以工作......我的合并助手有问题。我需要做的是发布订单，从左到右，但我不确定我所做的是否有意义。有什么想法吗？ 

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

1 回答 1

1

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

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

所以解决方案就变成了（伪代码）：

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

之后，tree1将合并两棵树，您可以使用tree2.

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

于 2014-03-25T09:04:09.277 回答