Bốn kiểu duyệt cây

#include <stdio.h>

#include "tree.h"

/* TIỀN thứ tự: gốc, trái, phải */
void tien_thu_tu(const TNode *r)
{
    if (r == NULL) return;

    printf("%d ", r->data);      /* xử lý TRƯỚC hai cây con */
    tien_thu_tu(r->left);
    tien_thu_tu(r->right);
}

/* TRUNG thứ tự: trái, gốc, phải */
void trung_thu_tu(const TNode *r)
{
    if (r == NULL) return;

    trung_thu_tu(r->left);
    printf("%d ", r->data);      /* xử lý GIỮA hai cây con */
    trung_thu_tu(r->right);
}

/* HẬU thứ tự: trái, phải, gốc */
void hau_thu_tu(const TNode *r)
{
    if (r == NULL) return;

    hau_thu_tu(r->left);
    hau_thu_tu(r->right);
    printf("%d ", r->data);      /* xử lý SAU hai cây con */
}

/* Tạo nút mới TRƯỚC, rồi gắn hai cây con vào.
   Trả về NULL nếu hết bộ nhớ, và dọn sạch phần đã chép. */
TNode *tree_sao_chep(const TNode *r)
{
    if (r == NULL) return NULL;

    TNode *n = tn_tao(r->data);      /* xử lý gốc TRƯỚC */

    if (n == NULL) return NULL;

    n->left = tree_sao_chep(r->left);

    if (r->left != NULL && n->left == NULL) { tree_huy(n); return NULL; }

    n->right = tree_sao_chep(r->right);

    if (r->right != NULL && n->right == NULL) { tree_huy(n); return NULL; }

    return n;
}

/* Cây biểu thức: lá là số, nút trong là toán tử.
   Phải có giá trị của hai cây con TRƯỚC khi tính được nút này. */
typedef struct BTNode {
    char           op;        /* 0 nếu là số */
    double         so;
    struct BTNode *left, *right;
} BTNode;

typedef enum { BT_OK, BT_CHIA_KHONG, BT_LOI } MaBT;

MaBT bt_tinh(const BTNode *r, double *ra)
{
    if (r == NULL) return BT_LOI;

    if (r->op == 0) { *ra = r->so; return BT_OK; }      /* lá */

    double a, b;
    MaBT   m;

    m = bt_tinh(r->left,  &a);  if (m != BT_OK) return m;    /* trái trước */
    m = bt_tinh(r->right, &b);  if (m != BT_OK) return m;    /* phải sau */

    switch (r->op) {                                          /* rồi mới gốc */
        case '+': *ra = a + b; return BT_OK;
        case '-': *ra = a - b; return BT_OK;
        case '*': *ra = a * b; return BT_OK;
        case '/':
            if (b == 0.0) return BT_CHIA_KHONG;
            *ra = a / b;
            return BT_OK;
        default:  return BT_LOI;
    }
}

#include <stdio.h>

#include "queue-ptr.h"      /* hàng đợi chứa TNode *, xem Bài 23.1 */
#include "tree.h"

/* In mọi nút theo thứ tự tầng, trái sang phải. */
int theo_tang(const TNode *goc)
{
    if (goc == NULL) return 0;

    QueueP q;

    queue_khoi_tao(&q);

    if (queue_enqueue(&q, goc) != 0) return -1;

    while (!queue_rong(&q)) {
        const TNode *n;

        queue_dequeue(&q, &n);

        printf("%d ", n->data);

        if (n->left  != NULL && queue_enqueue(&q, n->left)  != 0) goto loi;
        if (n->right != NULL && queue_enqueue(&q, n->right) != 0) goto loi;
    }

    queue_huy(&q);

    return 0;

loi:
    queue_huy(&q);

    return -1;
}

/* Bản có xuống dòng giữa các tầng và trả về số tầng. */
int theo_tang_co_dong(const TNode *goc, size_t *so_tang)
{
    if (goc == NULL) { *so_tang = 0; return 0; }

    QueueP q;
    size_t tang = 0;

    queue_khoi_tao(&q);

    if (queue_enqueue(&q, goc) != 0) return -1;

    while (!queue_rong(&q)) {
        size_t n_tang = queue_so_phan_tu(&q);      /* CHỐT trước vòng trong */

        for (size_t i = 0; i < n_tang; ++i) {
            const TNode *n;

            queue_dequeue(&q, &n);
            printf("%d ", n->data);

            if (n->left  != NULL && queue_enqueue(&q, n->left)  != 0) goto loi;
            if (n->right != NULL && queue_enqueue(&q, n->right) != 0) goto loi;
        }

        printf("\n");
        ++tang;
    }

    queue_huy(&q);
    *so_tang = tang;

    return 0;

loi:
    queue_huy(&q);

    return -1;
}

/* Tiền thứ tự bằng ngăn xếp. Đẩy PHẢI trước để TRÁI ra trước. */
int tien_thu_tu_lap(const TNode *goc)
{
    if (goc == NULL) return 0;

    StackP st;

    stack_khoi_tao(&st);

    if (stack_push(&st, goc) != 0) return -1;

    while (!stack_rong(&st)) {
        const TNode *n;

        stack_pop(&st, &n);
        printf("%d ", n->data);

        if (n->right != NULL && stack_push(&st, n->right) != 0) goto loi;
        if (n->left  != NULL && stack_push(&st, n->left)  != 0) goto loi;
    }

    stack_huy(&st);

    return 0;

loi:
    stack_huy(&st);

    return -1;
}

/* Trung thứ tự bằng ngăn xếp. Khó hơn hẳn: phải đi hết nhánh trái
   rồi mới xử lý, nên cần một con trỏ chạy song song với ngăn xếp. */
int trung_thu_tu_lap(const TNode *goc)
{
    StackP       st;
    const TNode *cur = goc;

    stack_khoi_tao(&st);

    while (cur != NULL || !stack_rong(&st)) {
        while (cur != NULL) {              /* đi hết xuống nhánh trái */
            if (stack_push(&st, cur) != 0) { stack_huy(&st); return -1; }

            cur = cur->left;
        }

        stack_pop(&st, &cur);              /* lấy nút trái nhất chưa xử lý */
        printf("%d ", cur->data);

        cur = cur->right;                  /* rồi sang nhánh phải của nó */
    }

    stack_huy(&st);

    return 0;
}

#include <stdio.h>

#include "tree.h"

/* In cây xoay 90 độ: gốc ở bên trái, cây con phải ở phía trên.
   Duyệt phải, gốc, trái, tức TRUNG thứ tự đảo ngược. */
void in_cay(const TNode *r, int muc)
{
    if (r == NULL) return;

    in_cay(r->right, muc + 1);

    for (int i = 0; i < muc; ++i) printf("      ");

    printf("%d\n", r->data);

    in_cay(r->left, muc + 1);
}

/* tien_to là chuỗi thụt lề tích lũy.
   la_goc cho biết đây có phải nút gốc không, vì gốc không có cha
   nên không cần ký hiệu nối.
   la_phai cho biết nút này là con phải hay con trái của cha nó. */
void in_khung(const TNode *r, const char *tien_to, int la_goc, int la_phai)
{
    if (r == NULL) return;

    char moi[256];

    /* Cây con phải in TRƯỚC, nên nó nằm phía trên */
    snprintf(moi, sizeof moi, "%s%s", tien_to,
             la_goc ? "" : (la_phai ? "    " : "|   "));
    in_khung(r->right, moi, 0, 1);

    printf("%s%s%d\n", tien_to,
           la_goc ? "" : (la_phai ? ",-- " : "'-- "), r->data);

    snprintf(moi, sizeof moi, "%s%s", tien_to,
             la_goc ? "" : (la_phai ? "|   " : "    "));
    in_khung(r->left, moi, 0, 0);
}

/* Gọi: in_khung(goc, "", 1, 0); */