时间戳

首页 > 解决方案 > 如何使用 C 中的中序遍历编写递归函数来搜索二叉树中的键？

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

问题描述

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

我遇到的问题是返回包含密钥的节点。每次我调用该函数并且密钥在二叉树中时，该函数都会返回 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 测试该功能。

标签： crecursionbinary-treeinorder

解决方案

这段代码：

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

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

然后它测试当前节点是否包含密钥。如果是，它返回给它的调用者。如果调用者是它自己（这是递归调用，而不是原始调用），调用者可能会忽略结果。

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

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

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

推荐阅读