2013-04-29 86 views
0

我有一個足夠簡單的任務。我要創建一個使用該結構的樹: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; 
+0

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

+0

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

+0

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

回答

4

它看起來像你的問題是與搜索則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); 
+0

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