2

所以，我有一点问题。我知道如何遍历树，是否使用递归，是否使用堆栈。但是，我也想跟踪每片叶子的高度，如果高度（或深度）小于给定的参数来打印那片叶子。这是我使用堆栈的代码：

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

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

4

1 回答 1

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

  3. 您需要推送节点子节点而不是节点本身

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

  4. 正如@chux所说，如果堆栈为空，pop则应返回NULL

于 2015-04-18T18:59:55.420 回答