C 語言實現二叉排序樹（BST）構建與遍歷完整代碼

需求

輸入關鍵字序列，構造二叉排序樹（左小右大），支持遍歷輸出。

核心結構與操作

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    int key;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 插入節點（遞歸）
BiTree Insert(BiTree T, int key) {
    if (T == NULL) {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->key = key;
        T->lchild = T->rchild = NULL;
        return T;
    }
    if (key < T->key)
        T->lchild = Insert(T->lchild, key);
    else if (key > T->key)
        T->rchild = Insert(T->rchild, key);
    // 相等不插入或按策略處理
    return T;
}

// 中序遍歷（輸出有序序列）
void InOrder(BiTree T) {
    if (T) {
        InOrder(T->lchild);
        printf("%d ", T->key);
        InOrder(T->rchild);
    }
}

// 前序/後序遍歷
void PreOrder(BiTree T) { if (T) { printf("%d ", T->key); PreOrder(T->lchild); PreOrder(T->rchild); } }
void PostOrder(BiTree T) { if (T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%d ", T->key); } }

// 釋放樹
void FreeTree(BiTree T) {
    if (T) { FreeTree(T->lchild); FreeTree(T->rchild); free(T); }
}

int main() {
    BiTree root = NULL;
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(keys)/sizeof(keys[0]);
    
    for (int i = 0; i < n; i++)
        root = Insert(root, keys[i]);
    
    printf("中序 (有序): "); InOrder(root); printf("\n");
    printf("前序: "); PreOrder(root); printf("\n");
    printf("後序: "); PostOrder(root); printf("\n");
    
    FreeTree(root);
    return 0;
}

進階功能

• 查找：遞歸/迭代比較 key 走向左/右子樹。
• 刪除：三種情況（葉子、單子、雙子），雙子需找前驅/後繼替換。
• 非遞歸遍歷：棧模擬（前序/中序/後序）、隊列（層序）。
• 平衡化：AVL/紅黑樹防止退化為鏈表。

完整可運行代碼（含非遞歸遍歷、刪除）

見原帖最佳回答，包含完整的控制台交互程序，支持動態輸入關鍵字構建樹並多種遍歷輸出。