C++中的DFS：返回節點（如果它包含搜索鍵）

我的程序目標是使用深度優先搜索搜索具有給定鍵的樹節點，並且如果找到具有該鍵的節點，它將返回給調用者函數。問題是，在DFS執行後訪問節點會終止帶有分段錯誤的程序，正好在搜索右側子樹中的節點時，而不是在左側子樹上搜索時終止。C++中的DFS：返回節點（如果它包含搜索鍵）

這是源代碼：

#include <iostream> 

using namespace std; 

struct node 
    char data; 
    struct node *left; 
    struct node *right; 
}; 

struct node *root = nullptr; 

struct node* addNewNode(char newData) { 
    struct node* newNode = new node; 
    newNode->data = newData; 
    newNode->left = nullptr; 
    newNode->right = nullptr; 

    return newNode; 
} 

struct node* preOrder(struct node *srcNode, char key) { 
    if (srcNode != nullptr) { 
     if (srcNode->data == key) 
      return srcNode; 
     return preOrder(srcNode->left, key); 
     return preOrder(srcNode->right, key); 
    } 
} 

int main() { 
    root = addNewNode('a'); 
    root->left = addNewNode('e'); 
    root->right = addNewNode('c'); 
    root->left->left = addNewNode('h'); 
    root->left->right = addNewNode('z'); 

    struct node* res = preOrder(root, 'c');  
    cout << res->data; 

    return 0; 
}

來源

2015-03-03 ner0x652

你preOrder函數並不總是返回一個值。如果srcNode是nullptr，則應返回nullptr。

你的編譯器應該警告你這個！如果不是，那麼改變你的編譯器設置，或者得到一個更好的編譯器。

編輯：另外 - 你應該檢查，res不是nullptr，然後再嘗試使用它。

EDIT2：沒有看到這一點

return preOrder(srcNode->left, key); 
    return preOrder(srcNode->right, key);

以預購的第二個電話會不會被調用（因爲你已經返回），所以你永遠不會在搜索右手節點。您需要更改邏輯，以便在左側搜索返回nullptr時在右側節點上進行搜索。

來源

2015-03-03 06:21:12

好的，它是有道理的，右子樹上的第二個preOrder永遠不會被調用，但在哪裏檢查左子樹是否返回nullptr？ – ner0x652 2015-03-03 06:55:07

不是立即返回左子樹的結果，而是將其存儲在局部變量中。然後，如果變量不是'nullptr'，則返回它，否則請按照您現在正在執行的操作檢查正確的子樹。 – 2015-03-03 07:17:58

我認爲一個簡單的方法來找到節點是有一個節點類型的全局變量*（例如res）和preOrder if（srcNode-> data == key）then res = srcNode。然後preOrder調用不需要被返回。 – ner0x652 2015-03-03 07:19:07

C++中的DFS：返回節點（如果它包含搜索鍵）

回答

相關問題