二叉樹構建與遍歷演算法全集：遞歸、非遞歸、查找樹操作

資料結構定義

struct BTNode {
    int data;
    BTNode *lchild, *rchild;
};

struct ABTStack {  // 非遞歸遍歷用堆疊
    BTNode *ptree;
    ABTStack *link;
};

六種建樹方法

1. dCreateBranchTree1：完全二叉樹陣列表示法（遞歸）

BTNode* dCreateBranchTree1(char array[], int i, int n) {
    if (i >= n) return NULL;
    BTNode* p = (BTNode*)malloc(sizeof(BTNode));
    p->data = array[i];
    p->lchild = dCreateBranchTree1(array, 2*i+1, n);
    p->rchild = dCreateBranchTree1(array, 2*i+2, n);
    return p;
}

適用：順序儲存的完全二叉樹，索引 i 左子 2i+1、右子 2i+2。

2. dCreateBranchTree2：有序陣列建平衡 BST（遞歸）

BTNode* dCreateBranchTree2(char array[], int i, int j) {
    if (i > j) return NULL;
    BTNode* p = (BTNode*)malloc(sizeof(BTNode));
    p->data = array[(i+j)/2];  // 中點為根
    p->lchild = dCreateBranchTree2(array, i, (i+j)/2 - 1);
    p->rchild = dCreateBranchTree2(array, (i+j)/2 + 1, j);
    return p;
}

適用：已排序陣列建構高度平衡 BST。

3. dCreateBranchTree3：前序+中序序列重建（遞歸）

BTNode* dCreateBranchTree3(char* pre, char* mid, int n) {
    if (n <= 0) return NULL;
    BTNode* p = (BTNode*)malloc(sizeof(BTNode));
    p->data = *pre;                    // 前序首元素為根
    char* t = mid;
    while (t < mid + n && *t != *pre) t++;  // 在中序中定位根
    int left = t - mid;                // 左子樹節點數
    p->lchild = dCreateBranchTree3(pre+1, mid, left);
    p->rchild = dCreateBranchTree3(pre+1+left, t+1, n-1-left);
    return p;
}

經典重建算法：前序定根，中序分左右。

4. CreateBranchTree：層序陣列建樹（非遞歸）

輸入陣列 array[][2]：[data, order]，order=1 為根，order>1 父節點 order/2，偶序掛左、奇序掛右。使用 NodeAddr[MAXNODE] 緩衝區暫存節點指標，單趟掃描完成建樹。

遍歷算法：遞歸與非遞歸雙實現

遞歸版（簡潔教學用）

void dpre_Order_Access(BTNode* h) {
    if (h) { visit(h); dpre(h->lchild); dpre(h->rchild); }
}
void dmid_Order_Access(BTNode* h) {
    if (h) { dmid(h->lchild); visit(h); dmid(h->rchild); }
}
void dlast_Order_Access(BTNode* h) {
    if (h) { dlast(h->lchild); dlast(h->rchild); visit(h); }
}

非遞歸版（工程實用，顯式堆疊）

核心模式：while (pt || top) { while (pt) { push(pt); pt = pt->lchild; } pt = pop(); visit(pt); pt = pt->rchild; }

• 前序：push → visit → go left
• 中序：push → go left → pop → visit → go right
• 後序：需雙堆疊或標記法（原碼後序非遞歸邏輯有缺陷，實務建議用雙堆疊法）。

二叉搜尋樹（BST）操作：非遞歸實現

靜態查找

BTNode* static_Search_STree(BTNode* h, int key) {
    while (h) {
        if (h->data == key) return h;
        h = (key < h->data) ? h->lchild : h->rchild;
    }
    return NULL;
}

動態查找（回傳父節點，支援插入）

void dynamic_Search_STree(BTNode* h, BTNode** parent, BTNode** p, int key) {
    *parent = NULL; *p = h;
    while (*p) {
        if ((*p)->data == key) return;
        *parent = *p;
        *p = (key < (*p)->data) ? (*p)->lchild : (*p)->rchild;
    }
}

回傳語意：
*parent==NULL && *p==NULL → 空樹
*parent==NULL && *p!=NULL → 根節點命中
*parent!=NULL && *p==NULL → 未命中，可掛接於 *parent
*parent!=NULL && *p!=NULL → 非根節點命中

插入節點

int Insert_Node_STree(BTNode* h, int key) {
    BTNode *p, *q, *nnode;
    dynamic_Search_STree(h, &p, &q, key);
    if (q) return 0;  // 已存在
    nnode = (BTNode*)malloc(sizeof(BTNode));
    nnode->data = key; nnode->lchild = nnode->rchild = NULL;
    if (!p) h = nnode;  // 空樹
    else if (key < p->data) p->lchild = nnode;
    else p->rchild = nnode;
    return 1;
}

批次插入

void Insert_Batch_Node_STree(BTNode* h, int array[], int n) {
    for (int i=0; i

char TreeNodeS[] = {'A','B','C','D','E','F','G'};
char PreNode[] = {'A','B','D','E','C','F','G'};
char MidNode[] = {'D','B','E','A','C','G','F'};
// 以上對應同一棵樹，驗證三種建樹方法一致性