Как написать рекурсивную функцию для поиска ключа в двоичном дереве, используя обход по порядку в C?

Question

Я пытаюсь написать рекурсивную функцию, которая, учитывая root двоичного дерева и ключа, ищет ключ, используя обратный порядок. Функция возвращает 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.

Answer 1

Этот код:

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

впервые использует inOrderKey для поиска в левом поддереве. Затем он игнорирует результат.

Затем он проверяет, содержит ли текущий узел ключ. Если это так, он возвращается к своему абоненту. Если вызывающий был сам (это рекурсивный вызов, а не исходный), вызывающий, скорее всего, игнорирует результат.

Затем он использует inOrderKey для поиска нужного дерева. Затем он возвращает результат.]

В конечном счете, узел, содержащий ключ, будет возвращен, только если он находился в крайнем правом пути. Если он находится в левом поддереве любого узла, он будет игнорироваться.

Чтобы исправить это, после каждого вызова inOrderKey проверяйте, является ли возвращаемое значение нулевым указателем. Если это не так, верните его немедленно, вместо того чтобы продолжать.

Answer 2

Проблема в том, что вы настаиваете на навигации по всему дереву , не проверяя, нашли ли вы ключ уже. В

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);
}

проверки сделаны, так что это должно работать (я не проверял это, поскольку вы не опубликовали полный и проверяемый пример, мои извинения за это)

Answer 3

[отредактировано - обновлено для использования при обходе ордера]

Перемещение влево. Если ключ не найден, тогда отметьте root, если ключ не совпадает, тогда вернитесь вправо.

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;
}