c - 无递归的后订单打印

Question

这就是我到目前为止所拥有的。我真的不明白我哪里错了。访问最左边的节点后需要打印，然后再向右打印。

void printPostOrderIterative(BSTNode *root)
{
    BSTNode *cur;
    Stack s;
    s.top = NULL;
    Stack output;
    output.top = NULL;

    if (!root) {
        return;
    }


    push(&s, root);

    while (isEmpty(&s) != 1 ) {
        cur = s.top;
        push(&output,cur);
        pop(&s);
        if (cur->left){
            push(&s, cur->left);
        }
        if (cur->right){
            push(&s, cur->right);
        }
    }
    while (isEmpty(&output) != 1) {
        printf("%d", output.top);
        pop(&output);
    }
}

目前，代码只是在第一个 while 循环中保持循环。

Answer 1

这是一些工作代码。我必须实现您的堆栈代码和 BST 代码的近似值，但我只对您的函数做了非常简单的更改。有人认为我不应该进行创建:Stack Overflow 鼓励您创建 MCVE ( How to create a Minimal, Complete, and Verifiable Example? )SSCCE ( Short, Self-Contained, Correct Example ) — 同一基本思想的两个名称和链接。

无需任何重大算法调整，您的代码 (a) 即可完成，并且 (b) 会生成与递归后序打印函数(在一个示例数据集上)相同的答案。

static void printPostOrderIterative(BSTNode *root)
{
    if (!root)         // Moved to avoid stack initialization before returning
        return;        // …ditto…

    Stack s;
    Stack output;
    init(&s);         // Different initialization
    init(&output);    // Different initialization
    push(&s, root);

    while (isEmpty(&s) != 1)
    {
        BSTNode *cur = top(&s);    // Different code
        push(&output, cur);
        pop(&s);
        if (cur->left)
            push(&s, cur->left);
        if (cur->right)
            push(&s, cur->right);
    }

    while (isEmpty(&output) != 1)
    {
        BSTNode *c = top(&output);  // Different code
        printf(" %d", c->data);     // Added space
        pop(&output);
    }
    putchar('\n');       // Extra code

    clean(&s);           // Extra code
    clean(&output);      // Extra code
}

因此问题可能不在您显示的代码中 - 更有可能在您未显示的代码中。我最好的猜测是堆栈实现有点错误，但由于您没有显示它，所以很难确定。

完整代码

#include <assert.h>
#include <errno.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BSTNode BSTNode;
struct BSTNode
{
    int      data;
    BSTNode *left;
    BSTNode *right;
};

typedef struct Stack
{
    size_t    size;
    size_t    top;
    BSTNode **stack;
} Stack;

static void err_syserr(const char *fmt, ...)
{
    int errnum = errno;
    va_list args;
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    if (errnum != 0)
        fprintf(stderr, "(%d: %s)\n", errnum, strerror(errnum));
    exit(1);
}

static void push(Stack *sp, BSTNode *np)
{
    assert(sp != 0 && np != 0);
    if (sp->top == sp->size)
    {
        size_t n_size = (sp->size + 2) * 2;
        void  *n_data = realloc(sp->stack, n_size * sizeof(*sp->stack));
        if (n_data == 0)
            err_syserr("Out of memory (%zu bytes requested)\n",
                       n_size * sizeof(*sp->stack));
        sp->stack = n_data;
        sp->size = n_size;
    }
    sp->stack[sp->top++] = np;
}

static bool isEmpty(Stack *sp)
{
    return sp->top == 0;
}

static void pop(Stack *sp)
{
    if (!isEmpty(sp))
        sp->top--;
}

static void init(Stack *sp)
{
    sp->top = 0;
    sp->size = 0;
    sp->stack = 0;
}

static BSTNode *top(Stack *sp)
{
    if (sp->top == 0)
        return 0;
    return sp->stack[sp->top - 1];
}

static void clean(Stack *sp)
{
    while (sp->top > 0)
        free(sp->stack[--sp->top]);
    free(sp->stack);
    init(sp);
}

static BSTNode *new_node(int data)
{
    BSTNode *np = malloc(sizeof(*np));
    if (np == 0)
        err_syserr("Out of memory (%zu bytes requested)\n", sizeof(*np));
    np->data = data;
    np->left = 0;
    np->right = 0;
    return np;
}

static void printPostOrderIterative(BSTNode *root)
{
    if (!root)
        return;

    Stack s;
    Stack output;
    init(&s);         // Different initialization
    init(&output);    // Different initialization
    push(&s, root);

    while (isEmpty(&s) != 1)
    {
        BSTNode *cur = top(&s);    // Different code
        push(&output, cur);
        pop(&s);
        if (cur->left)
            push(&s, cur->left);
        if (cur->right)
            push(&s, cur->right);
    }

    while (isEmpty(&output) != 1)
    {
        BSTNode *c = top(&output);
        printf(" %d", c->data);
        pop(&output);
    }
    putchar('\n');       // Extra code

    clean(&s);           // Extra code
    clean(&output);      // Extra code
}

static void printPostOrderRecursive(BSTNode *root)
{
    if (root != 0)
    {
        printPostOrderRecursive(root->left);
        printPostOrderRecursive(root->right);
        printf(" %d", root->data);
    }
}

static void printInOrderRecursive(BSTNode *root)
{
    if (root != 0)
    {
        printInOrderRecursive(root->left);
        printf(" %d", root->data);
        printInOrderRecursive(root->right);
    }
}

static BSTNode *bst_add(BSTNode *root, int data)
{
    if (root == 0)
        root = new_node(data);
    else if (root->data > data)
        root->left = bst_add(root->left, data);
    else
        root->right = bst_add(root->right, data);
    return root;
}

static void bst_destroy(BSTNode *root)
{
    if (root != 0)
    {
        bst_destroy(root->left);
        bst_destroy(root->right);
        free(root);
    }
}

int main(void)
{
    int data[] =
    {
        71, 57,  4, 31, 47, 65, 69, 65, 98, 81,
        54, 58, 17, 37, 48, 64, 64, 93, 40, 22,
        45, 62, 99, 47, 18, 86, 67, 99, 68, 27,
    };
    enum { NUM_DATA = sizeof(data) / sizeof(data[0]) };

    BSTNode *root = 0;
    for (int i = 0; i < NUM_DATA; i++)
    {
        root = bst_add(root, data[i]);
        printInOrderRecursive(root);
        putchar('\n');
    }

    printPostOrderRecursive(root);
    putchar('\n');
    printPostOrderIterative(root);

    bst_destroy(root);
    return 0;
}

示例输出

 71
 57 71
 4 57 71
 4 31 57 71
 4 31 47 57 71
 4 31 47 57 65 71
 4 31 47 57 65 69 71
 4 31 47 57 65 65 69 71
 4 31 47 57 65 65 69 71 98
 4 31 47 57 65 65 69 71 81 98
 4 31 47 54 57 65 65 69 71 81 98
 4 31 47 54 57 58 65 65 69 71 81 98
 4 17 31 47 54 57 58 65 65 69 71 81 98
 4 17 31 37 47 54 57 58 65 65 69 71 81 98
 4 17 31 37 47 48 54 57 58 65 65 69 71 81 98
 4 17 31 37 47 48 54 57 58 64 65 65 69 71 81 98
 4 17 31 37 47 48 54 57 58 64 64 65 65 69 71 81 98
 4 17 31 37 47 48 54 57 58 64 64 65 65 69 71 81 93 98
 4 17 31 37 40 47 48 54 57 58 64 64 65 65 69 71 81 93 98
 4 17 22 31 37 40 47 48 54 57 58 64 64 65 65 69 71 81 93 98
 4 17 22 31 37 40 45 47 48 54 57 58 64 64 65 65 69 71 81 93 98
 4 17 22 31 37 40 45 47 48 54 57 58 62 64 64 65 65 69 71 81 93 98
 4 17 22 31 37 40 45 47 48 54 57 58 62 64 64 65 65 69 71 81 93 98 99
 4 17 22 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 69 71 81 93 98 99
 4 17 18 22 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 69 71 81 93 98 99
 4 17 18 22 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 69 71 81 86 93 98 99
 4 17 18 22 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 67 69 71 81 86 93 98 99
 4 17 18 22 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 67 69 71 81 86 93 98 99 99
 4 17 18 22 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 67 68 69 71 81 86 93 98 99 99
 4 17 18 22 27 31 37 40 45 47 47 48 54 57 58 62 64 64 65 65 67 68 69 71 81 86 93 98 99 99
 18 27 22 17 45 40 37 47 48 54 47 31 4 62 64 64 58 68 67 65 69 65 57 86 93 81 99 99 98 71
 18 27 22 17 45 40 37 47 48 54 47 31 4 62 64 64 58 68 67 65 69 65 57 86 93 81 99 99 98 71

讨论

由于您使用了交错声明和语句，因此您至少使用的是 C99，因此我使用了 <stdbool.h>和bool类型。该代码编译干净，至少在使用选项编译时(Mac OS X 10.11.4，GCC 5.3.0):

$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
>     -Wold-style-definition -Werror nr-post.c -o nr-post
$

代码在 valgrind 下运行干净(3.12.0-SVN)。

输出的第一行在树构建时按顺序打印(从 0..99 范围内随机生成的 30 个整数)。这让我可以看到这棵树是从头开始正确构建的。最后两行输出首先来自 printPostOrderRecursive() ，后序打印的简单递归实现，然后来自(我对你的轻微改编)printPostOrderIterative() .

如果你的堆栈实现不可用，我不得不猜测你在那里的某个地方有问题。通过如图所示的堆栈的直接实现(其中 top 是节点指针数组的索引)，您的代码就可以了。我们无法判断您是否忽略了编译警告。

嗯，检查我的代码，我发现它没有检查 top()返回一个非空指针。添加断言和运行时错误而不是返回 null 是很诱人的。还可以添加许多其他断言 - 特别是传递给堆栈函数的非空堆栈指针。