二叉搜索树 - 迭代检查高度

Question

那么，我遇到了一些问题。我知道如何遍历树，是否使用递归，是否使用堆栈。但是，我还想跟踪每片叶子的高度，如果高度（或深度）小于打印该叶子的给定参数。这是我使用堆栈的代码：

void PrintLevelIter(struct tNode* tree, int h1){
    if(h1==0){
        printf("%d ",tree->info);
        return;
    }
    struct sNode *stek = NULL;
    push(&stek,tree);

    struct tNode* current = tree;


    while(!isEmptyStack(stek)){
        pop(&stek);
        printf("%d ",current->info);
        if(current->left != NULL && current->right != NULL){
            if(Depth(current) < h1){
                push(&stek, current);
            }
            else return;
        }
    }
}

我做错了什么？可能是因为我的堆栈实现？这是代码：

struct sNode{
    struct tNode* t;
    struct sNode* next;
};

/*Funkcije za stek*/
void push(struct sNode** top, struct tNode* t){
    struct sNode* newNode = (struct sNode*)malloc(sizeof(struct sNode));
    if(newNode==NULL)
    {
        return;
    }
    newNode->t = t;
    newNode->next = (*top);
    (*top) = newNode;
}

int isEmptyStack(struct sNode* top){
    return top==NULL;
}

struct tNode* pop(struct sNode** top){
    struct tNode* res;
    struct sNode* sTop;

    if(isEmptyStack(*top))
        printf("Stack is empty!");
    else{
        sTop = *top;
        res = sTop->t;
        *top = sTop->next;
        free(top);

    }
    return res;
}

问题是，我的输出只给我根值，没有别的。有谁知道我在哪里犯了错误？还是错误:)？

Answer 1

你不要在循环内改变current的值，pop(&stek)应该是current = pop(&stek)
return应该是continue，不是递归，return会在遍历所有树之前退出函数

你需要推送节点子节点而不是节点本身

while (!isEmptyStack(stek))
{
    current = pop(&stek);

    if (current->left != NULL)
        push(&stek, current->left);
    if (current->right != NULL)
        push(&stek, current->right);

    if (Depth(current) < h1)
        printf("%d ",current->info);
}

如@chux 所说，pop 应该 return NULL 如果堆栈为空

二叉搜索树 - 迭代检查高度

Binary search tree - Iterative check for height

c

stack

height

binary-search-tree

non-recursive