c - ANSI C - 将节点附加到任意树

Question

当向任意树添加新节点时，您会从根开始遍历这棵树吗？或者您会构建子树并将它们组合起来构建整个树？

我的节点和树结构如下所示:

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;
}    

树.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;
}

ma​​in.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;
}

Answer 1

嗯，这取决于你的树是如何组织的。 “任意树”，使用任意数量的子节点通常不用于节点具有确定顺序的情况；在大多数情况下，当父/子关系很重要时，这种树就会出现。

在这种情况下，您的附加通常更像是“将此节点添加为该父节点的子节点”，允许快速插入，因为父节点已知，并且如果子节点的顺序不已知，则允许恒定时间插入没关系。

否则，您可能必须遵循应用程序必须遵循的任何规则来遍历树，才能找到放置节点的正确位置。