如何使用 C 中的中序遍历编写递归函数来搜索二叉树中的键？

Question

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

我遇到的问题是返回包含密钥的节点。每次我调用函数并且键在二叉树中时，函数returns 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搜索左子树。然后它忽略结果。

然后测试当前节点是否包含key。如果是，它 returns 给它的调用者。如果调用者本身（这是在递归调用中，而不是原始调用），调用者可能会忽略结果。

然后它使用inOrderKey搜索正确的树。那么它 return 就是结果。]

最终，只有在最右边的路径中，包含密钥的节点才会被 returned。如果在任意节点的左子树中，则忽略。

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

Answer 2

[已编辑 - 已更新以用于顺序遍历]

向左走。如果找不到key，则检查root，如果key不匹配，则向右递归。

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

Answer 3

您遇到的问题是您坚持浏览整棵树而不检查您是否已经找到密钥。在

TreeNodePtr inOrderKey(TreeNodePtr root, int key)
{
    /* don't declare a local you don't know 
     * yet if you are going to use */

    /* better to check the opposite */
    if (root == NULL) 
        return NULL;  /* no tree, nothing can be found */

    TreeNodePtr node = inOrderKey(root->left, key);

    if (node) return node; /* we found it in the left child */
    if(key == root->data) { /* check here */
        /* you found it in this node */
        return root;
    }

    /* last chance, right child :) */
    return inOrderKey(root->right, key);
}

验证已经完成，所以这应该可以工作（我没有测试它，因为你没有post一个完整和可验证的例子，我很抱歉）

如何使用 C 中的中序遍历编写递归函数来搜索二叉树中的键？

How to write a recursive function to search for a key in a binary tree using in-order traversal in C?

c

recursion

binary-tree

inorder