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：返回节点（如果它包含搜索键）

回答

相关问题