Chèn vào BST

#include <stdlib.h>

#include "bst.h"

/* Chèn v vào cây gốc r. Trả về gốc MỚI của cây con đó.
   Khóa trùng bị bỏ qua. Trả về r cũ nếu hết bộ nhớ, tức cây không đổi. */
TNode *bst_chen(TNode *r, int v)
{
    if (r == NULL) return tn_tao(v);      /* tìm được chỗ trống, tạo nút */

    if      (v < r->data) r->left  = bst_chen(r->left,  v);
    else if (v > r->data) r->right = bst_chen(r->right, v);
    /* v == r->data: bỏ qua, không cho trùng */

    return r;                             /* gốc không đổi ở mọi tầng khác */
}

/* Dùng: */
TNode *goc = NULL;

goc = bst_chen(goc, 50);
goc = bst_chen(goc, 30);
goc = bst_chen(goc, 70);

/* Trả về  0 nếu chèn được
            1 nếu khóa đã có, cây không đổi
           -1 nếu hết bộ nhớ, cây không đổi                    */
int bst_chen2(TNode **pgoc, int v)
{
    if (pgoc == NULL) return -1;

    if (*pgoc == NULL) {
        TNode *n = tn_tao(v);

        if (n == NULL) return -1;

        *pgoc = n;

        return 0;
    }

    if (v < (*pgoc)->data) return bst_chen2(&(*pgoc)->left,  v);
    if (v > (*pgoc)->data) return bst_chen2(&(*pgoc)->right, v);

    return 1;      /* đã có */
}

/* Dùng: */
TNode *goc = NULL;

if (bst_chen2(&goc, 50) < 0) { /* xử lý hết bộ nhớ */ }

typedef struct {
    TNode *goc;
    size_t size;      /* số nút, để hỏi trong O(1) */
} BST;

void bst_khoi_tao(BST *t);
void bst_huy(BST *t);
int  bst_chen3(BST *t, int v);      /* 0 ổn, 1 đã có, -1 hết bộ nhớ */
int  bst_co(const BST *t, int v);

int bst_chen3(BST *t, int v)
{
    int kq = bst_chen2(&t->goc, v);

    if (kq == 0) ++t->size;      /* chỉ tăng khi thật sự thêm nút */

    return kq;
}

/* Bản lặp: không đệ quy, O(1) bộ nhớ, không sợ tràn ngăn xếp. */
int bst_chen_lap(TNode **pgoc, int v)
{
    if (pgoc == NULL) return -1;

    TNode *cha = NULL;
    TNode *cur = *pgoc;

    /* Đi xuống tìm chỗ trống, nhớ nút cha */
    while (cur != NULL) {
        if      (v < cur->data) { cha = cur; cur = cur->left;  }
        else if (v > cur->data) { cha = cur; cur = cur->right; }
        else                    return 1;      /* đã có */
    }

    TNode *n = tn_tao(v);

    if (n == NULL) return -1;

    if      (cha == NULL)     *pgoc      = n;   /* cây trước đó rỗng */
    else if (v < cha->data)   cha->left  = n;
    else                      cha->right = n;

    return 0;
}

/* Ngắn nhất: pp luôn là địa chỉ của ô đang trỏ tới cây con hiện tại. */
int bst_chen_pp(TNode **pgoc, int v)
{
    TNode **pp = pgoc;

    while (*pp != NULL) {
        if      (v < (*pp)->data) pp = &(*pp)->left;
        else if (v > (*pp)->data) pp = &(*pp)->right;
        else                      return 1;
    }

    TNode *n = tn_tao(v);

    if (n == NULL) return -1;

    *pp = n;      /* ghi thẳng vào ô trống vừa tìm được */

    return 0;
}

#include <stdio.h>

#include "bst.h"

int main(void)
{
    BST t;

    bst_khoi_tao(&t);

    int nguon[] = { 50, 30, 70, 20, 40, 60, 80, 30, 50 };

    for (size_t i = 0; i < sizeof nguon / sizeof nguon[0]; ++i) {
        int kq = bst_chen3(&t, nguon[i]);

        printf("chen %2d -> %s\n", nguon[i],
               kq == 0 ? "ok" : kq == 1 ? "da co" : "het bo nho");

        if (kq < 0) { bst_huy(&t); return 1; }
    }

    printf("so nut     : %zu\n", t.size);
    printf("chieu cao  : %d\n",  tree_chieu_cao(t.goc));
    printf("la BST     : %d\n",  la_bst(t.goc));

    printf("trung thu tu: ");
    trung_thu_tu(t.goc);
    printf("\n");

    printf("cay:\n");
    in_khung(t.goc, "", 1, 0);

    bst_huy(&t);

    return 0;
}

if (v == r->data) return r;      /* không làm gì, giữ nút cũ */

typedef struct TNodeD {
    int             data;
    size_t          dem;         /* số lần khóa này được chèn */
    struct TNodeD  *left, *right;
} TNodeD;

int bstd_chen(TNodeD **pp, int v)
{
    while (*pp != NULL) {
        if      (v < (*pp)->data) pp = &(*pp)->left;
        else if (v > (*pp)->data) pp = &(*pp)->right;
        else { ++(*pp)->dem; return 0; }      /* đã có, chỉ tăng đếm */
    }

    TNodeD *n = malloc(sizeof *n);

    if (n == NULL) return -1;

    n->data = v;
    n->dem  = 1;
    n->left = n->right = NULL;
    *pp     = n;

    return 0;
}