C++中的遍歷樹

我有一個足夠簡單的任務。我要創建一個使用該結構的樹：C++中的遍歷樹

struct gennode 
{ 
int item; 
gennode * firstChild; 
gennode * siblingList; 
gennode * prevSibling; 
gennode * parent; 
};

我的搜索算法是這樣的：

gennode* general::search(int element, gennode *t) 
{ 
    if(t == NULL) 
    { 
     return t; 
    } 
    if(t->item == element) 
    { 
     return t; 
    } 
    if(t->firstChild != NULL) 
    { 
     return search(element, t->firstChild); 
    } 
    return search(element, t->siblingList); 
}

我想不出什麼錯誤。它似乎不想找到所有的孩子。例如，如果我有1作爲根，2,3,4作爲孩子，5,6,7作爲2和8,9的孩子作爲4的孩子，我無法搜索找到2的孩子。

我找不出我的問題在哪裏。

編輯：下面是一個gennode結構如何在樹中查找的例子，其中1作爲根，2和3作爲子節點。

gennode * one; 
gennode * two; 
gennode * three; 

one->item = 1; 
one->firstChild = two; 
one->siblingList = NULL; 
one->prevSibling = NULL; 
one->parent = NULL; 

two->item = 2; 
two->firstChild = NULL; 
two->siblingList = three; 
two->prevSibling = NULL; 
two->parent = one; 

three->item = 3; 
three->firstChild = NULL; 
three->siblingList = NULL; 
three->prevSibling = two; 
three->parent = one;

來源

2013-04-29 marcinx27

siblingList引用了什麼？如同一個單一節點如何列表？如果你有一個孩子的列表，將它們存儲在一個矢量而不是單個節點中不是更好嗎？ siblingList是下一個兄弟姐妹，並prevSibling前一個？這個我不清楚。 – 2013-04-29 03:43:36

與你的例子請給予節點的gennode成員值爲值2 – 999k 2013-04-29 03:49:45

我編輯原始帖子，包括一個例子。 – marcinx27 2013-04-29 04:12:32

它看起來像你的問題是與搜索則firstChild OR siblingList的邏輯。也就是說，如果你有firstChild，你就永遠不會看兄弟姐妹。如果您的樹是從後到前構建的，它可能會解釋爲什麼要搜索節點4，而不是節點2.相反，您可能想要問一下search（element，t-> firstChild）是否成功，如果不成功，則轉到搜索（element，t-> siblingList）：

if(t->firstChild != NULL) 
{ 
    auto result = search(element, t->firstChild); 
    if(result != nullptr) 
    return result; 
} 
return search(element, t->siblingList);

來源

2013-04-29 03:51:18

我完全不理解這段代碼。如果通過兄弟姐妹找到一個NULL指針，它將會中斷。我只是困惑。 – marcinx27 2013-04-29 04:35:58

C++中的遍歷樹

回答

相關問題