0

新しいノードを任意のツリーに追加するとき、ルートからツリーをトラバースしますか？または、サブツリーを構築し、それらを組み合わせてツリー全体を構築しますか？

私のノードとツリーの構造は次のようになります。

Node.h

struct _Node;
typedef struct _Node Node;

Node.c

struct _Node
{
    char *pName;
    unsigned char *pValue;
    struct _Node *pFirstChild;
    struct _Node *pNextSibling;
};

Node* NodeCreate(char *pName, uint32_t uLength, unsigned char *pValue)
{
    if (!pValue)
        return NULL;

    Node *pNode = (Node*)malloc(sizeof(Node));
    if (!pNode)
        return NULL;

    pNode->pName = pName;
    pNode->pValue = (unsigned char*)malloc(uLength * sizeof(pValue[0]));
    pNode->pFirstChild = NULL;
    pNode->pNextSibling = NULL;

    return pNode;
}

Tree.h

struct _Tree;
typedef struct _Tree Tree;

Tree.c

struct _Tree
{
    Node *pRoot;
};

Node* TreeNodeCreate(char *pName, uint32_t uLength, unsigned char *pValue)
{
    return NodeCreate(pName, uLength, pValue);
}

Node* TreeNodeAppend(Node **ppParent, Node *pNode)
{
    if (!((*ppParent)->pFirstChild))
    {
        (*ppParent)->pFirstChild = pNode;

        return (*ppParent)->pFirstChild;
    }

    Node *pLastChild = (*ppParent)->pFirstChild;
    while (pLastChild->pNextSibling)
        pLastChild = pLastChild->pNextSibling;

    pLastChild->pNextSibling = pNode;

    return pLastChild;
}

Node* TreeGetRoot(Tree *pTree)
{
    if (!pTree)
        return NULL;

    return pTree->pRoot;
}

void TreeSetRoot(Tree **ppTree, Node *pNode)
{
    (*ppTree)->pRoot = pNode;
}

main.c

int main()
{
    unsigned char value[] = { 0x01, 0x02, 0x03 };
    uint32_t uLength = sizeof(value) / sizeof(value[0]);

    Tree *pTree = TreeCreate();

    Node *pRoot = TreeNodeCreate("Root", uLength, value);
    TreeSetRoot(&pTree, pRoot); 

    Node *pA = TreeNodeCreate("A", uLength, value);
    Node *pB = TreeNodeCreate("B", uLength, value);
    Node *pC = TreeNodeCreate("C", uLength, value);
    Node *pD = TreeNodeCreate("D", uLength, value);
    Node *pE = TreeNodeCreate("E", uLength, value);
    Node *pF = TreeNodeCreate("F", uLength, value);

    TreeNodeAppend(&pRoot, pA);
    TreeNodeAppend(&pRoot, pB);

    TreeNodeAppend(&pA, pC);
    TreeNodeAppend(&pA, pD);

    TreeNodeAppend(&pB, pE);
    TreeNodeAppend(&pE, pF);

    return 0;
}
4

1 に答える 1

2

まあ、それはあなたのツリーがどのように編成されているかに依存します。「任意のツリー」であり、任意の数の子ノードを使用することは、通常、ノードの順序が決まっているものには使用されません。ほとんどの場合、このようなツリーは、親子関係が重要な場合に表示されます。

このような場合、追加は通常、「このノードをその親の子として追加する」のようになり、親がすでにわかっているためすばやく挿入でき、子の順序が重要でない場合は一定時間挿入できます。

そうしないと、アプリケーションがノードを配置するための正しい場所を見つけるために必要なルールに従って、ツリーを通過する必要がある場合があります。

于 2012-08-19T14:06:25.493 に答える