0

tree.hh: STL に似た C++ ツリー クラスを使用して、ツリーにデータを入力し、以下のツリーを取得するにはどうすればよいですか。いくつかの助けをいただければ幸いです。A と G はルート ノードです。

            A            G
      ______|____        |
     /      |    \       |
    B       C     D      H
    |       |     |      |
    |       E     |      |
     \_____/      |      |
        |         |      |
        F         |      |
        |_________|______|
           |
           I
           |
           J

上記のコードでは、深さ優先検索を使用してリスト内の項目を列挙しています。このようにフォーマットされたデータはほとんどありません

typedef tree<std::string> TreeNode;
typedef struct
{
    int   nBases;
    char * name;
} BASES;
BASES rgbases[] =
{
    {0xB, "J"},
    {0xA, "I"},
    {0x1, "H"},{0x0, "G"},
    {0x5, "F"},{0x2, "E"},{0x1, "C"},{0x0, "A"},
    {0x1, "D"},{0x0, "A"},
    {0x1, "B"},{0x0, "A"}
};

//here i'm trying to populate my tree
void populateTree(TreeNode &tr, BASES *pBaseArray, int numBase)
{
    int n = 0;
    while ( n < numBase )
    {
        BASES *pBase = &pBaseArray[n];
        if ( pBase->nBases > 0) // Check for children of the new node
            populateTree(tr, pBaseArray + (n + 1),pBase->nBases);
        // i suppose i need to insert tree code part here
        n += pBase->nBases + 1;
    }
}
void BuildTree(TreeNode &tr)
{
    populateTree(tr, rgBases, _countof(rgBases));
}
4

1 に答える 1

0

提示された元のグラフにまたがるツリーは、ノードAとBおよびDをリンクするエッジ（またはノードAとCおよびDをリンクするエッジ）を削除することで取得できます。その場合、ツリークラスが適用可能になります。

            A            G                                   A            G 
            |            |                             ______|            |
            |            |                            /                   |
    B       C     D      H                           B       C     D      H 
    |       |     |      |                           |       |     |      | 
    |       E     |      |                           |       E     |      | 
    \______/      |      |                           \______/      |      |
        |         |      |                              |          |      |
        F         |      |                              F          |      |
        |_________|______|                              |__________|______| 
           |                                                | 
           I                                                I
           |                                                |
           J                                                J

ループを発生させる上記のツリーのエッジは、別々に記録できます。つまり、ABとADは、ツリークラスとは別に構造に記録できます。このような構造でツリーをマージすると、元のグラフが復元されます。

于 2012-05-02T02:59:58.467 に答える