c - ANSI C - 在任意树中查找节点

Question

我创建了一个简单的测试程序，如下(省略了错误检查)。

我的 Tree_Find() 和 Node_Find() 函数似乎工作正常，但我想知道是否有更有效的方法来实现相同的目标。

Node.h

typedef struct _Node Node;

Node* Node_Create(int nTag);
void Node_Destroy(Node **ppNode);
void Node_Append(Node **ppParent, Node *pChild);
Node* Node_Find(Node *pNode, int nTag);

树.h

#include "Node.h"

typedef struct _Tree Tree;

Tree* Tree_Create(void);
void Tree_Destroy(Tree **ppTree);
void Tree_Init(Tree *pTree);
Node* Tree_Find(Tree *pTree, int nTag);

Node.c

#include "Node.h"

struct _Node
{
    int nTag;
    struct _Node *pFirstChild;
    struct _Node *pNextSibling;
};

Node* Node_Create(int nTag)
{
    Node *pNode = malloc(sizeof(*pNode));
    pNode->nTag = nTag;
    pNode->pFirstChild = NULL;
    pNode->pNextSibling = NULL;

    return pNode;
}

void Node_Destroy(Node **ppNode)
{
    Node *pNode = NULL;

    if (!ppNode)
        return;

    if ((pNode = *ppNode) == NULL)
        return;

    Node_Destroy(&(pNode->pFirstChild));
    Node_Destroy(&(pNode->pNextSibling));

    free(pNode);
    *ppNode = NULL;
}

void Node_Append(Node **ppParent, Node *pChild)
{
    Node *pLastChild = NULL;

    if (!(*ppParent))
        return;

    if (!((*ppParent)->pFirstChild))
    {
        (*ppParent)->pFirstChild = pChild;

        return;
    }

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

    pLastChild->pNextSibling = pChild;
}

Node* Node_Find(Node *pNode, int nTag)
{
    Node *pNodeFound = NULL;

    if (!pNode)
        return NULL;

    if (pNode->nTag == nTag)
        return pNode;

    if ((pNodeFound = Node_Find(pNode->pFirstChild, nTag)) == NULL)
        pNodeFound = Node_Find(pNode->pNextSibling, nTag);

    return pNodeFound;
}

树.c

#include "Tree.h"

struct _Tree
{
    Node *pRoot;
};

Tree* Tree_Create(void)
{
    Tree *pTree = malloc(sizeof(*pTree));

    pTree->pRoot = NULL;

    return pTree;
}

void Tree_Destroy(Tree **ppTree)
{
    Tree *pTree = NULL;

    if (!ppTree)
        return;

    if ((pTree = *ppTree) == NULL)
        return;

    Node_Destroy(&(pTree->pRoot));

    free(pTree);
    *ppTree = NULL;
}

void Tree_Init(Tree *pTree)
{
    Node *p1 = Node_Create(1);
    Node *p2 = Node_Create(2);
    Node *p3 = Node_Create(3);
    Node *p4 = Node_Create(4);
    Node *p5 = Node_Create(5);

    Node_Append(&p1, p2);
    Node_Append(&p1, p3);
    Node_Append(&p3, p4);
    Node_Append(&p3, p5);

    pTree->pRoot = p1;
}

Node* Tree_Find(Tree *pTree, int nTag)
{
    if (!pTree)
        return NULL;

    return Node_Find(pTree->pRoot, nTag);
}

ma​​in.c

#include "Tree.h"

int main(void)
{
    Node *pNodeToFind = NULL;

    Tree *pTree = Tree_Create();

    Tree_Init(pTree);

    pNodeToFind = Tree_Find(pTree, 1);
    pNodeToFind = Tree_Find(pTree, 2);
    pNodeToFind = Tree_Find(pTree, 3);
    pNodeToFind = Tree_Find(pTree, 4);
    pNodeToFind = Tree_Find(pTree, 5);
    pNodeToFind = Tree_Find(pTree, 6); // Not found!

    Tree_Destroy(&pTree);

    return 0;
}

Answer 1

如果您的目标是构建和搜索键上没有顺序的任意树，那么您已经完成了几乎所有您能做的事情，除了一件事:您的追加方法将有 O(n^2) 运行时间，其中 n 是单个节点可能拥有的子节点数量。如果维护的是队列而不是列表，则可以在单位时间内追加。有一个很好的技巧可以实现队列中只有一个头指针而不是单独的头指针和尾指针。使子列表成为循环列表，并使父列表指向循环列表的尾部。那么parent->children是尾元素，parent->children->sibling是头元素。通过此设置，您可以插入子列表的尾部，也可以从子列表的头部插入和弹出。这些操作的代码可以非常优雅，并且您的追加时间将是恒定的。

或者，您可以将子项存储在自动调整大小的数组中。存在轻微的存储损失(您需要存储每个节点的指针和子节点计数)，但在某些情况下对子节点的随机访问可能很方便。