c - 如何在 C 中编写递归函数以使用中序遍历在二叉树中搜索键？

Question

我正在尝试编写一个递归函数，给定二叉树的根和一个键，使用中序遍历来搜索键。如果没有找到带有该键的节点，该函数返回 NULL；否则返回包含该键的节点。

我遇到的问题是返回包含 key 的节点。每次我调用该函数并且键位于二叉树中时，该函数都会返回 NULL。感觉结果不断被函数第一行的初始化覆盖。

这是有序搜索功能:

typedef struct treeNode
{
    int data;
    struct treeNode *left, *right;
} TreeNode, *TreeNodePtr;

typedef struct
{
    TreeNodePtr root;
} BinaryTree;

TreeNodePtr inOrderKey(TreeNodePtr root, int key)
{
    TreeNodePtr node = NULL;

    if (root != NULL)
    {
        node = inOrderKey(root->left, key);
        if(key == root->data)
        {
           node = root;
           return node;
        }
        node = inOrderKey(root->right, key);
    }

    return node;
}

主要功能如下:

int main()
{
    FILE * in = fopen("numbst.txt", "r");

    BinaryTree bst;
    bst.root = NULL;

    int num;

    fscanf(in, "%d", &num);
    while (num != 0)
    {
        if (bst.root == NULL)
            bst.root = newTreeNode(num);
        else
        {
            TreeNodePtr node = findOrInsert(bst, num);
        }
        fscanf(in, "%d", &num);
    }

    printf("\nThe in-order traversal is: ");
    inOrder(bst.root);
    printf("\nThe pre-order traversal is: ");
    preOrder(bst.root);

    TreeNodePtr keyNode;
    int count = 0;
    keyNode = inOrderKey(bst.root, 9);
    if (keyNode != NULL)
        count = 1;
    else
        count = 0;

    if (count == 1)
        printf("\n\n%d exists in the binary tree. In order traversal was used.\n", 9);
    else
        printf("\n\n%d doesn't exist in the binary tree. In order traversal was used.\n", 9);
        return 0;
}

我正在使用的二叉树的中序遍历是:1 2 3 4 5 7 9 21

二叉树的前序遍历为:4 1 2 3 7 5 21 9

我正在使用 9 和 31 测试该函数。

Answer 1

这段代码:

    node = inOrderKey(root->left, key);
    if(key == root->data)
    {
       node = root;
       return node;
    }
    node = inOrderKey(root->right, key);

首先使用inOrderKey来搜索左子树。然后它会忽略结果。

然后测试当前节点是否包含该键。如果是，则返回给调用者。如果调用者是其本身(这是递归调用，而不是原始调用)，则调用者可能会忽略结果。

然后它使用inOrderKey来搜索正确的树。然后返回结果。]

最终，仅当包含该键的节点位于最右边的路径时才会返回该节点。如果它在任意节点的左子树中，则会被忽略。

要解决此问题，请在每次调用 inOrderKey 后测试返回值是否为空指针。如果不是，请立即返回，而不是继续。