Cây nhị phân

#ifndef TREE_H
#define TREE_H

#include <stddef.h>

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

TNode *tn_tao(int data);
void   tree_huy(TNode *r);
size_t tree_dem_nut(const TNode *r);
size_t tree_dem_la(const TNode *r);
int    tree_chieu_cao(const TNode *r);
size_t tree_dem_nut_trong(const TNode *r);

#endif

#include <stdlib.h>

#include "tree.h"

TNode *tn_tao(int data)
{
    TNode *n = malloc(sizeof *n);

    if (n == NULL) return NULL;

    n->data  = data;
    n->left  = NULL;
    n->right = NULL;

    return n;
}

#include <stdio.h>

#include "tree.h"

/* Dựng bằng tay cây mẫu của chương.
   Trả về NULL nếu hết bộ nhớ giữa chừng, và dọn sạch phần đã dựng. */
static TNode *dung_cay_mau(void)
{
    TNode *r = tn_tao(50);

    if (r == NULL) return NULL;

    r->left  = tn_tao(30);
    r->right = tn_tao(70);

    if (r->left == NULL || r->right == NULL) { tree_huy(r); return NULL; }

    r->left->left   = tn_tao(20);
    r->left->right  = tn_tao(40);
    r->right->left  = tn_tao(60);
    r->right->right = tn_tao(80);

    if (r->left->left  == NULL || r->left->right  == NULL ||
        r->right->left == NULL || r->right->right == NULL) {
        tree_huy(r);

        return NULL;
    }

    return r;
}

int main(void)
{
    TNode *goc = dung_cay_mau();

    if (goc == NULL) { fprintf(stderr, "Het bo nho\n"); return 1; }

    printf("so nut       : %zu\n", tree_dem_nut(goc));
    printf("so la        : %zu\n", tree_dem_la(goc));
    printf("so nut trong : %zu\n", tree_dem_nut_trong(goc));
    printf("chieu cao    : %d\n",  tree_chieu_cao(goc));

    tree_huy(goc);

    return 0;
}

#include <stdio.h>
#include <math.h>

int main(void)
{
    printf("%12s %12s %12s\n", "so nut", "cao toi thieu", "cao toi da");

    for (long n = 10; n <= 10000000; n *= 10)
        printf("%12ld %12.0f %12ld\n",
               n, ceil(log2((double)n + 1.0)) - 1.0, n - 1);

    return 0;
}

/* Đếm số nút. Cây rỗng có 0 nút. */
size_t tree_dem_nut(const TNode *r)
{
    if (r == NULL) return 0;

    return 1 + tree_dem_nut(r->left) + tree_dem_nut(r->right);
}

/* Đếm số lá. Lá là nút không có con nào. */
size_t tree_dem_la(const TNode *r)
{
    if (r == NULL) return 0;

    if (r->left == NULL && r->right == NULL) return 1;

    return tree_dem_la(r->left) + tree_dem_la(r->right);
}

/* Đếm số nút trong, tức nút có ít nhất một con. */
size_t tree_dem_nut_trong(const TNode *r)
{
    if (r == NULL) return 0;

    if (r->left == NULL && r->right == NULL) return 0;

    return 1 + tree_dem_nut_trong(r->left) + tree_dem_nut_trong(r->right);
}

/* Chiều cao tính theo cạnh. Cây rỗng có chiều cao -1. */
int tree_chieu_cao(const TNode *r)
{
    if (r == NULL) return -1;

    int t = tree_chieu_cao(r->left);
    int p = tree_chieu_cao(r->right);

    return 1 + (t > p ? t : p);
}

/* Hủy cây. Con TRƯỚC, gốc SAU. Bài 24.2 nói kỹ vì sao. */
void tree_huy(TNode *r)
{
    if (r == NULL) return;

    tree_huy(r->left);
    tree_huy(r->right);
    free(r);
}

#include <limits.h>

/* Giá trị lớn nhất trong cây. Trả về INT_MIN nếu cây rỗng. */
int tree_lon_nhat(const TNode *r)
{
    if (r == NULL) return INT_MIN;

    int t  = tree_lon_nhat(r->left);
    int p  = tree_lon_nhat(r->right);
    int kq = r->data;

    if (t > kq) kq = t;
    if (p > kq) kq = p;

    return kq;
}

/* Tổng mọi giá trị. */
long long tree_tong(const TNode *r)
{
    if (r == NULL) return 0;

    return r->data + tree_tong(r->left) + tree_tong(r->right);
}

/* Hai cây có giống hệt nhau không, cả cấu trúc lẫn giá trị. */
int tree_bang(const TNode *a, const TNode *b)
{
    if (a == NULL && b == NULL) return 1;
    if (a == NULL || b == NULL) return 0;

    return a->data == b->data
        && tree_bang(a->left,  b->left)
        && tree_bang(a->right, b->right);
}

/* Cây gương: đảo trái phải ở mọi nút. Sửa tại chỗ. */
void tree_lat(TNode *r)
{
    if (r == NULL) return;

    TNode *t = r->left;

    r->left  = r->right;
    r->right = t;

    tree_lat(r->left);
    tree_lat(r->right);
}

/* Cây đầy: mọi nút có 0 hoặc 2 con. */
int tree_day(const TNode *r)
{
    if (r == NULL) return 1;

    if ((r->left == NULL) != (r->right == NULL)) return 0;   /* đúng một con */

    return tree_day(r->left) && tree_day(r->right);
}

/* Cây cân bằng chiều cao. Bản ngây thơ tốn O(n bình phương). */
int tree_can_bang_cham(const TNode *r)
{
    if (r == NULL) return 1;

    int t = tree_chieu_cao(r->left);       /* mỗi lần lại duyệt cả cây con */
    int p = tree_chieu_cao(r->right);
    int d = t - p;

    if (d < -1 || d > 1) return 0;

    return tree_can_bang_cham(r->left) && tree_can_bang_cham(r->right);
}

/* Bản O(n): trả về chiều cao, hoặc -2 làm tín hiệu "không cân bằng". */
static int cao_hoac_bao_loi(const TNode *r)
{
    if (r == NULL) return -1;

    int t = cao_hoac_bao_loi(r->left);

    if (t == -2) return -2;

    int p = cao_hoac_bao_loi(r->right);

    if (p == -2) return -2;

    int d = t - p;

    if (d < -1 || d > 1) return -2;

    return 1 + (t > p ? t : p);
}

int tree_can_bang(const TNode *r)
{
    return cao_hoac_bao_loi(r) != -2;
}