二叉樹是每個節點最多擁有兩個子節點的樹形結構。除根節點外，每個節點有且僅有一個父節點；無子節點者稱葉子節點；其餘為分支節點。若每層節點數達上限則為滿二叉樹；若除最後一層外達上限且最後一層靠左集中則為完全二叉樹。
typedef struct Node {
int data; // 數據域
struct Node *left; // 左子樹指針
struct Node *right; // 右子樹指針
} Node;
| 遍歷方式 | 順序 | 典型應用 |
|---|---|---|
| 先序 | 根 → 左 → 右 | 樹的複製、前綴表達式 |
| 中序 | 左 → 根 → 右 | BST 輸出有序序列 |
| 後序 | 左 → 右 → 根 | 釋放內存、後綴表達式 |
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
typedef struct {
Node *root;
int cnt;
} Tree;
/* ---------- 工具函數 ---------- */
Node *create_node(int data) {
Node *pn = (Node *)malloc(sizeof(Node));
pn->data = data; pn->left = pn->right = NULL;
return pn;
}
/* ---------- 插入 ---------- */
void insert(Node **pRoot, Node *pn) {
if (*pRoot == NULL) { *pRoot = pn; return; }
if ((*pRoot)->data > pn->data) insert(&(*pRoot)->left, pn);
else insert(&(*pRoot)->right, pn);
}
void insert_data(Tree *pt, int data) {
insert(&pt->root, create_node(data));
pt->cnt++;
}
/* ---------- 中序遍歷（輸出有序序列） ---------- */
void travel(Node *pRoot) {
if (pRoot) {
travel(pRoot->left);
printf("%d ", pRoot->data);
travel(pRoot->right);
}
}
void travel_data(Tree *pt) { travel(pt->root); printf("\n"); }
/* ---------- 查找：返回指向目標節點指針的指針 ---------- */
Node **find(Node **pRoot, int data) {
if (*pRoot == NULL) return pRoot;
if (data == (*pRoot)->data) return pRoot;
if (data < (*pRoot)->data) return find(&(*pRoot)->left, data);
return find(&(*pRoot)->right, data);
}
Node **find_data(Tree *pt, int data) { return find(&pt->root, data); }
/* ---------- 刪除：合併左右子樹 ---------- */
void del_data(Tree *pt, int data) {
Node **pp = find_data(pt, data);
if (*pp == NULL) { printf("目標不存在，刪除失敗\n"); return; }
Node *q = *pp; // 待刪節點
if (q->left) insert(&q->right, q->left); // 左子樹併入右子樹
*pp = q->right; // 父節點指向合併後的右子樹
free(q); q = NULL;
pt->cnt--;
}
/* ---------- 修改 = 刪舊 + 插新 ---------- */
void modify(Tree *pt, int old_v, int new_v) {
del_data(pt, old_v);
insert_data(pt, new_v);
}
/* ---------- 輔助查詢 ---------- */
int empty(Tree *pt) { return pt->root == NULL; }
int full(Tree *pt) { return 0; } // 鏈式結構理論不滿
int size(Tree *pt) { return pt->cnt; }
int get_root(Tree *pt) { return empty(pt) ? -1 : pt->root->data; }
/* ---------- 清空整棵樹 ---------- */
void clear(Node **pRoot) {
if (*pRoot) {
clear(&(*pRoot)->left);
clear(&(*pRoot)->right);
free(*pRoot); *pRoot = NULL;
}
}
void clear_data(Tree *pt) { clear(&pt->root); pt->cnt = 0; }
/* ---------- 主程序演示 ---------- */
int main() {
Tree tree = {NULL, 0};
insert_data(&tree, 50); travel_data(&tree); // 50
insert_data(&tree, 70); travel_data(&tree); // 50 70
insert_data(&tree, 20); travel_data(&tree); // 20 50 70
insert_data(&tree, 60); travel_data(&tree); // 20 50 60 70
del_data(&tree, 50); travel_data(&tree); // 20 60 70
del_data(&tree, 30); travel_data(&tree); // 刪除失敗
del_data(&tree, 20); travel_data(&tree); // 60 70
modify(&tree, 10, 20); travel_data(&tree); // 20 60 70
printf("根節點: %d\n", get_root(&tree)); // 70
printf("節點數: %d\n", size(&tree)); // 3
printf("%s\n", empty(&tree)?"空":"非空"); // 非空
clear_data(&tree);
return 0;
}
Node ** 實現「修改父節點指針」find 返回 &parent->left 或 &parent->right，刪除時直接 *pp = new_child 即可修改父節點指向，無需額外記錄父節點。
利用 BST 性質：左子樹所有值 < 根 < 右子樹所有值。將左子樹整體插入右子樹，再用右子樹根替代被刪節點，保持有序性。
極端退化樹（如遞增插入）深度 = n，遞歸可能棧溢出。生產環境建議改用非遞歸 + 顯式棧或紅黑樹/AVL平衡結構。
50 50 70 20 50 70 20 50 60 70 ------------------ 20 50 60 70 20 60 70 20 60 70 60 70 -------------------- 20 60 70 二叉樹中根節點的元素是：70 二叉樹中節點的個數是：3 二叉樹不為空 二叉樹沒有滿
lower_bound/upper_bound 區間查詢完整代碼已上傳 GitHub，歡迎學習交流！
