3

c＃を使用してn-ary種類のデータ構造を実装しようとしています。ツリーにはルートノードと子の配列があり、子配列の各子にも子ノードのセットがあります。私がやろうとしているのは、リーフノードに存在するすべての子に追加する必要がある子配列を追加するときです。私のコードは

      public void addChildren(Node root, Node[] children)
        {

             if (root.children == null)
            {
                root.children = children;

            }
            else
            {
                for (int i = 0; i < root.children.Length; i++)
                {

                    addChildren(root.children[i], children);
                }
            }

        }

メインプログラム

     Dictionary<String, String[]> measurelist = new Dictionary<string, string[]>();
        String[] values = { "y", "n" };
        measurelist.Add("m1", values);
        measurelist.Add("m2", values);
        measurelist.Add("m3", values);           
        foreach (KeyValuePair<String, String[]> entry in measurelist)
        {
            Node[] children = new Node[entry.Value.Length];
           for(int i = 0; i < entry.Value.Length ;i ++)
            {
                Node child = new Node(entry.Key+":"+entry.Value[i]);
                children[i] = child;
            }

            clustertree.addChildren(clustertree.root, children);               
        }

しかし、このコードは無限の再帰呼び出しをもたらします。私は試しましたが、何が悪いのか理解できませんでしたか？私が間違っていることを見つけるのを手伝ってください。 私は画像で問題を説明しました

解決策： あなたの助けを借りて、私はこの問題の解決策を見つけました。根本的な原因を説明すると、同じ問題に直面する可能性のある他の人にも役立つと思います。ノードの子配列を渡すときの問題の主な原因は、値ではなく参照として渡されます。同じ子配列参照が次の再帰呼び出しに渡されないようにするために、コードを少し変更しました。

これが私の修正されたコードです：

 public void addChildren(Node root, Node[] children)
        {

             if (root.children == null)
            {

                root.children = children;

            }
            else
            {
                for (int i = 0; i < root.children.Length; i++)
                {                       
                    Node[] children1 = new Node[children.Length];
          //I am creating a new array and nodes and passing the newly created array to                                       the next recursive call
                    for (int j = 0; j < children.Length; j++)
                    {
                        Node node = new Node(children[j].key);                           
                        node.children = children[j].children;
                        children1[j] = node;
                    }
                    addChildren(root.children[i], children1);
                }
            }

        }

再度、感謝します ：）

4

2 に答える 2

2

おそらく、内部node[]をlist<node>配列ではなく内部にする必要があります。

次に、このコードを使用します

      public void addChildren(Node root, Node[] children)
        {

            if (root.children == null)
            {
                root.children = new List<Node>();

            }

            root.children.AddRange(children);

        }
于 2013-02-23T08:13:01.523 に答える
1

図に示されているようにツリーを作成しているのではなく、次のようなことを行っています。

       R
      / \
     /   \
    a1   a2 (children of this are actually b1 and b2)
   / \   
  /   \
 b1   b2

b1, b2の子としてを追加すると、すでに追加されているものをa2参照していることになります。b1 and b2a1

を追加する次の反復c1 and c2では、アルゴリズムに従って、最初c1 and c2に両方を参照しますが、関数はここで停止しません。この時点では、を介して再び実行されますが、の子としてすでに追加されているため、アルゴリズムは混乱して入ります。永遠にループします。b1 and b2a1b1 and b2a2c1 and c2b1 and b2

この問題を解決するために：

ツリーの最後のレベルを検索しますが、最後のレベルまでは、1つの子のみを使用する再帰パスのみを使用します。

public boolean addChildren(Node root, Node[] children)
{

    if (root.children == null)
    {
        root.children = children;
        return true;
    }
    else
    {
        for (int i = 0; i < root.children.Length; i++)
        {
            /* if it returns true then it was last level 
                   else break */
            if(!addChildren(root.children[i], children)) 
            {
                /* this is non-last level break */
                break;
            }
        }
    }
    return false;
}
于 2013-02-23T08:43:40.593 に答える