c - 二叉树中的迭代加深深度优先搜索

Question

我有一个正常的二叉树，我试图在使用 c 时应用迭代加深深度优先搜索：

struct node {
    int data;
    struct node * right;
    struct node * left;
};

typedef struct node node;

我正在使用一个函数将节点插入树中，现在我需要将搜索函数实现为如下所示： function search(root,goal,maxLevel) 所以它使用深度优先搜索但搜索到特定的最大级别然后停止这是我的第一次尝试，它没有工作：

currentLevel = 0;
void search(node ** tree, int val, int depth)
{
    if(currentLevel <= depth) {
        currentLevel++;
        if((*tree)->data == val)
        {
            printf("found , current level = %i , depth = %i", currentLevel,depth);

        } else if((*tree)->left!= NULL && (*tree)->right!= NULL)
        {
            search(&(*tree)->left, val, depth);
            search(&(*tree)->right, val, depth);
        }
    }
}

请帮忙，谢谢...

Answer 1

你永远不会停止...

node *search(node ** tree, int val, int depth)
{
    if (depth <= 0)
    {
        return NULL; // not found
    }

    if((*tree)->data == val)
    {
        return *tree;
    }

    if((*tree)->left)
    {
        node * left = search(&(*tree)->left, val, depth - 1);
        if (left) return left; // found
    }
    if((*tree)->right)
    {
        node * right = search(&(*tree)->left, val, depth - 1);
        return right; // whatever is result of right
    }
    return NULL; // not found
}

Answer 2

全局变量不适用于此。你想拥有类似的东西

void search(node ** tree, int val, int remainingDepth) {
    if (remainingDepth == 0) return;

然后

        search(&(*tree)->left, val, remainingDepth - 1);
        search(&(*tree)->right, val, remainingDepth - 1);

您可能还想分别检查左右是否为空，因为每个都可以独立为空。