2

N分木に変換する必要がある配列があります。N の値とノードの総数を知っています。

下の写真で例を挙げます。N 分木は図のように並べる必要があります。

画像へのリンクはこちら

私はそれを理解することはできません。そのためのアルゴリズムが必要です。私が書いているプログラムはjavascriptですが、疑似コードでの回答も問題ありません。

あなたの助けに感謝！

【編集済】

ここからアルゴリズムを使用して解決策を見つけました: Construct a complete K-ary tree from preorder traversal

4

2 に答える 2

2

ここからアルゴリズムを使用して解決策を見つけました：

preorder トラバーサルから完全な K-ary ツリーを構築する

于 2014-06-04T09:42:28.403 に答える
0

これは疑似コード/ C# バージョンです。コメントで C# 関連の質問をしてください。ここで重要なことは、先入れ先出しのデータ構造 (parents以下のスニペットのキュー) を使用することです。このメソッドconvertToN_aryTreeは、結果の n 分ツリーのルート ノードを返します。

public class Node
{
    public int data;
    public int nCount; // 'n' in n-ary
    public Node[] children; // this needs to be initialised to length n

    public Node(int d, int n)
    {
        data = d;
        nCount = n;
        children = new Node[n];
    }
}

// data is teh array and n is branch factor of the tree
Node convertToN_aryTree(int[] data, int n)
{
    if(data.Length == 0)
    {
        return null;
    }
    Node root = new Node(data[0], n);
    Node currParent = root;
    Node curr;
    int currChildCount = 0;
    Queue<Node> parents = new Queue();
    for(int i = 1; i<data.Length; i++)
    {
        curr = new Node(data[i], n);
        currParent.children[currChildCount] = curr;
        parents.Enqueue(curr);

        currChildCount++;
        if(currChildCount >= n) // finished with children of this node, so start adding to children of the next.
        {                       // next node is either a sibling or a child but that is taken care of by Queue.
            currParent = parents.Dequeue();
            currChildCount = 0;
        }
    }

    return root;
}
于 2014-05-01T14:21:56.593 に答える