C中沒有遞歸和堆棧的遍歷樹C

如何在C中無遞歸地遍歷樹的每個節點（無C++）？C中沒有遞歸和堆棧的遍歷樹C

假設我有樹的以下節點結構：

struct Node 
{ 
    struct Node* next; /* sibling node linked list */ 
    struct Node* parent; /* parent of current node */ 
    struct Node* child; /* first child node   */ 
}

這不是功課。
我更喜歡先深入。
我更喜歡不需要額外的數據結構（如堆棧）。
我更喜歡速度（而不是空間）方面最有效的方法。
您可以更改或添加Node結構的成員以存儲其他信息。

來源

2010-07-09 uray

一個字......堆棧。 – ChaosPandion 2010-07-09 15:54:10

按什麼順序？ – kennytm 2010-07-09 15:54:20

任何順序，最好是深度優先 – uray 2010-07-09 15:56:12

如果你不希望有任何存儲，並確定與深度優先搜索：

process = TRUE; 
while(pNode != null) { 
    if(process) { 
     //stuff 
    } 
    if(pNode->child != null && process) { 
     pNode = pNode->child; 
     process = true; 
    } else if(pNode->next != null) { 
     pNode = pNode->next; 
     process = true; 
    } else { 
     pNode = pNode->parent; 
     process = false; 
    } 
}

將遍歷樹; process是爲了防止它在返回時重新接觸父節點。

來源

2010-07-09 16:03:43 zebediah49

+1用於識別兄弟節點的鏈接列表的工作方式，而不是像高分的答案那樣引入大量無意義的開銷...... – 2010-07-09 16:33:17

......這仍然是很多得分較高的...... - 聲譽稱爲聲譽... – ShinTakezou 2010-07-09 16:40:31

+1。這看起來不錯。我刪除了我的答案，因爲:-)（我正在使用額外的節點信息）。對於一個解釋：這是不變的：當訪問一個節點時，如果過程是真實的，這意味着你還沒有遍歷該子樹。在完成所有這些操作後，您只能在訪問其子節點後才能回到節點，在這種情況下，過程是錯誤的，現在您轉移到兄弟節點。 – 2010-07-09 16:54:11

通常，您將使用自己的堆棧數據結構來存儲節點列表（或者如果您想要級別順序遍歷，則使用隊列）。

您首先將任何給定的起始節點推入堆棧。然後你進入你的主循環，直到堆棧爲空。從堆棧中彈出每個節點後，如果不是空的，則推入其下一個和子節點。

來源

2010-07-09 15:54:08

儘管如此，它也不會沿着樹遍歷。 – zebediah49 2010-07-09 15:55:02

@zeb，是的，它會 – corsiKa 2010-07-09 15:56:40

如果我使用鏈表實現自己的堆棧，它會比使用遞歸更有效嗎？ – uray 2010-07-09 15:57:53

您必須將其存儲在可迭代列表中。一個包含索引的基本列表將起作用。然後你只需從0結束查看數據。

如果你想避免遞歸，你需要保持樹中每個對象的引用。

來源

2010-07-09 15:59:22 Forge

您可以使用Pointer Reversal方法。缺點是您需要在節點內保存一些信息，因此它不能用於const數據結構。

來源

2010-07-09 16:22:20

這看起來像是我在25年前在工程學院所做的練習。我認爲這被稱爲樹包絡算法，因爲它繪製了樹的包絡。

我不敢相信它那麼簡單。我一定在某個地方犯了一個無知的錯誤。不管怎麼樣，我相信包封策略是正確的。如果代碼是錯誤的，只要將其視爲僞代碼即可。

while current node exists{ 
    go down all the way until a leaf is reached; 
    set current node = leaf node; 
    visit the node (do whatever needs to be done with the node); 

    get the next sibling to the current node; 
    if no node next to the current{ 
    ascend the parentage trail until a higher parent has a next sibling; 
    } 
    set current node = found sibling node; 
}

代碼：

void traverse(Node* node){ 

    while(node!=null){ 
    while (node->child!=null){ 
     node = node->child; 
    } 

    visit(node); 

    node = getNextParent(Node* node); 
    } 
} 

/* ascend until reaches a non-null uncle or 
* grand-uncle or ... grand-grand...uncle 
*/ 
Node* getNextParent(Node* node){ 

    /* See if a next node exists 
    * Otherwise, find a parentage node 
    * that has a next node 
    */ 
    while(node->next==null){ 
    node = node->parent; 
    /* parent node is null means 
    * tree traversal is completed 
    */ 
    if (node==null) 
     break; 
    } 

    node = node->next; 

    return node; 
}

來源

2010-07-09 21:50:20

C中沒有遞歸和堆棧的遍歷樹C

回答

相關問題