0

将新节点附加到任意树时，您会从根遍历树吗？或者你会构建子树并将它们组合成一棵完整的树吗？

我的节点和树结构看起来像：

节点.h

struct _Node;
typedef struct _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;
}

树.h

struct _Tree;
typedef struct _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;
}

主程序

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 回答