C++ 中的 DFS：return 节点，如果它包含搜索到的键

Question

我的程序目标是使用深度优先搜索来搜索具有给定键的树节点，如果找到具有该键的节点，它将返回给调用函数。问题是在 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;
}

Answer 1

您的 preOrder 函数并不总是 return 一个值。如果 srcNode 是 nullptr 你应该 return nullptr.

您的编译器应该就此警告您！如果不是，则更改您的编译器设置，或获得更好的编译器。

编辑：另外 - 在您尝试使用它之前，您应该检查 res 不是 nullptr。

编辑 2：没看到这一点

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

将永远不会调用对 preOrder 的第二次调用（因为您已经 returned），因此您永远不会搜索右侧节点。您需要更改逻辑，以便在左侧搜索时在右侧节点上搜索 returned nullptr.

C++ 中的 DFS：return 节点，如果它包含搜索到的键

DFS in C++: return node if it contains searched key

c++

algorithm

tree

depth-first-search