binary tree traversal

Normal binary tree inorder traversal

Node definition:

struct bintree_node {
    char *data;  
    struct bintree_node *left, *right;
};

Recursively

void bintree_show(struct bintree_node *n) {
    if (n == NULL) return;
    bintree_show(n->left);
    printf ("%s\n", n->data);
    bintree_show(n->right);
}

Iteratively

Paraphrased from TAoCP:

void bintree_show_taocp(struct bintree_node *T) {
    struct bintree_node *A[10];
    struct bintree_node *P;
    int depth;

T1: depth = 0;                  /* "Set stack A empty" */
    P = T;
T2: if (P == NULL) goto T4;
T3: A[depth++] = P;
    P = P->left;
    goto T2;
T4: if (depth == 0) return;
    P = A[--depth];
T5: printf("%s\n", P->data);   /* "Visit P" */
    P = P->right;
    goto T2;
}

Re-written:

void bintree_show_taocp2 (struct bintree_node *n) {
    struct bintree_node *stack[10];
    int depth = 0;

    while (n || depth != 0) {
        if (n != NULL) {
            stack[depth++] = n;
            n = n->left;
        } else {
            n = stack[--depth];
            printf("%s\n", n->data);
            n = n->right;
        }
    }
}