ANSI C - 在任意樹中查找節點

我已經創建了一個簡單的測試程序，如下所示（省略了錯誤檢查）。ANSI C - 在任意樹中查找節點

我的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);

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

Tree.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); 
}

的main.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; 
}

來源

2012-09-08 jpen

您可以避免遞歸。除此之外，它看起來並不需要優化。 –

ANSI C是一個相對模糊的術語。雖然它通常指的是C89，但ANSI也採用了C99 *和* C11。 – oldrinb

以下劃線和大寫字母開頭的名稱保留供實施用於任何目的;避免使用這些名字。在你的代碼中，不要使用前導下劃線; 'typedef struct Node Node;'在C中完全可以（並且在C++中沒有必要）。 –

如果您的目標是在按鍵上無順序地構建並查找任意樹，那麼除了一件事外，您已經完成了所有可以執行的操作：您的append方法將具有O（n^2）運行時間，其中n是單個節點可能擁有的孩子的數量。如果你維護一個隊列而不是一個列表，你可以追加單位時間。實現一個隊列中只有一個指針而不是單獨的頭部和尾部指針是很好的技巧。使子列表循環並使父指向通知列表的尾部。然後父母 - >孩子是尾巴元素，父母 - >孩子 - >兄弟姐妹是頭部。通過這種設置，您可以推到尾巴上，並從兒童列表的頭部推入和彈出。這些操作符的代碼可以非常優雅，並且你的追加將是恆定的。

或者，您可以將孩子存儲在自動調整大小的數組中。存在輕微的存儲損失（您需要爲每個節點存儲指針和子數），但在某些情況下，可以隨意訪問子項。

來源

2012-09-08 20:24:57 Gene

正如Linus Torvalds的說，它是所有關於數據結構。你的算法本身不能優化，但你的數據結構可以。重複訪問指針並不便宜，您可以在一個節點中存儲256個對象，以獲得更高的性能。

來源

2012-09-08 20:06:37 orlp

ANSI C - 在任意樹中查找節點

回答

相關問題