0

私は2つの二分木をマージしようとしていますが、これが私が思いついたものです。私のInsertmerge関数は正しいだけでなく、私の関数とマージ関数も機能すると信じています...マージヘルパーに問題があります。私がする必要があるのは、ポストオーダー、左から右ですが、私がやっていることは意味があるかどうかわかりません。何かご意見は？ 

  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

2 つのバイナリ ツリーをマージする最も簡単な方法は、ツリーが既に提供している機能を使用することです。

  • トラバーサル、値を抽出します。
  • 値を挿入する手段。

したがって、ソリューションは次のようになります (疑似コード):

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

それに続いて、tree12 つのツリーがマージされ、必要なことを行うことができますtree2。

これが基本的な考え方です。重複の削除やエラー状態などを処理したい場合がありますが、始めるにはそれで十分です。公開されたインターフェイスがよりクリーンな方法を提供する場合、データ構造の内部を使用してもほとんど意味がありません。

于 2014-03-25T09:04:09.277 に答える