??一、前言
? ? ? 二叉樹是一種特殊的樹形結構，每個節點最多有兩個子節點，分別稱為左子樹和右子樹。其特點是子樹有嚴格的左右之分，順序不可顛倒。從歷年真題來看，二叉樹的鏈式存儲實現、遍歷算法、屬性統計是高頻考點，常以選擇題（概念辨析）、填空題（代碼補全）、編程題（算法實現）形式出現。
????????二叉樹的常見類型包括：
- 滿二叉樹：所有非葉子節點均有兩個子節點，且所有葉子節點在同一層。
- 完全二叉樹：除最后一層外，其他層節點數達到最大值，且最后一層節點向左對齊。
- 二叉搜索樹（BST）：左子樹所有節點的值小于根節點，右子樹所有節點的值大于根節點。
二、二叉樹
???????二叉樹通常用鏈式存儲或順序存儲（數組）實現。二叉樹的鏈式存儲通過節點連接實現，每個節點包含數據域和兩個指針域（分別指向左子樹和右子樹）。
1.定義
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
2.基本操作
（1）初始化二叉樹
????????初始化操作將二叉樹根節點的左右子樹指針設為NULL，確保樹的初始狀態為空。
bool InitBiTree(BiTree &T){T->lchild = NULL;T->rchild = NULL;return true;
}（2）創建二叉樹（遞歸法）
????????基于先序遍歷規則構建二叉樹，通過遞歸方式依次創建根節點、左子樹和右子樹，#符號用于標識空節點。
void CreateBiTree(BiTree &T){char ch;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=(BiTNode *)malloc(sizeof(BiTNode));T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}（3）銷毀二叉樹
????????采用后序遍歷思路，先遞歸銷毀左、右子樹，再釋放當前節點，確保所有內存被正確回收。
void DestroyBiTree(BiTree &T){if(T){if(T->lchild)DestroyBiTree(T->lchild);if(T->rchild)DestroyBiTree(T->rchild); free(T);T=NULL;}
}（4）遍歷操作
????????二叉樹的遍歷是訪問所有節點的過程，常見方式包括先序、中序、后序（遞歸 / 非遞歸）和層序遍歷。
- 先序遍歷（遞歸）
遞歸實現簡潔，先訪問當前節點，再依次遍歷左、右子樹。
//訪問輸出結點
void visit(BiTree T){printf("%c",T->data);}
//先序-遞歸
void PreOrder(BiTree T){if(T!=NULL){visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}- 中序遍歷（非遞歸，借助棧）
非遞歸實現需借助棧，先將所有左節點入棧，再依次彈出并訪問，最后遍歷右子樹。
void InOrder2(BiTree T){SqStack S;InitStack(S);BiTree p=T;while(p!=NULL||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);visit(p);p=p->rchild;}}
} - 層序遍歷（借助隊列）
利用隊列實現，依次將每層節點入隊，出隊時訪問節點并將其子女入隊，確保按層次順序遍歷。
void LevelOrder(BiTree T){SqQueue Q;InitQueue(Q);BiTree p;EnQueue(Q,T);while(!IsEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild!=NULL){EnQueue(Q,p->lchild);}if(p->rchild!=NULL){EnQueue(Q,p->rchild);}}
}（5）二叉樹的屬性統計
????????二叉樹的屬性統計是分析樹結構特征的重要操作，包括節點類型計數、高度和寬度計算等。這些屬性不僅反映了樹的形態特征，也為算法設計（如平衡樹判斷、最優路徑搜索）提供基礎數據。
- 統計葉子節點（度為0的節點）
int Degree0(BiTree T){if(T==NULL) return 0;else if(T->lchild==NULL&&T->rchild==NULL) return 1;else return Degree0(T->lchild)+Degree0(T->rchild);
}- 統計度為1的節點
int Degree1(BiTree T){if(T==NULL) return 0;if((T->rchild==NULL && T->lchild!=NULL) || (T->rchild!=NULL && T->lchild==NULL))return Degree1(T->lchild)+Degree1(T->rchild)+1;else return Degree1(T->lchild)+Degree1(T->rchild);
}- 統計度為2的節點
int Degree2(BiTree T){if(T==NULL) return 0;if(T->rchild!=NULL && T->lchild!=NULL ) return Degree2(T->lchild)+Degree2(T->rchild)+1;else return Degree2(T->lchild)+Degree2(T->rchild);
}- 計算樹的高度
int BtDepth(BiTree T){if(T==NULL) return 0;int ldep = BtDepth(T->lchild);int rdep = BtDepth(T->rchild);if(ldep > rdep) return ldep+1;else return rdep+1;
}3.主函數示例（功能測試）
int main() {BiTree T1;InitBiTree(T1);printf("請輸入二叉樹的先序序列（以#表示空節點）：");CreateBiTree(T1); // 構建二叉樹printf("中序遍歷結果：");InOrder2(T1); // 測試中序非遞歸遍歷printf("\n層序遍歷結果：");LevelOrder(T1); // 測試層序遍歷printf("\n葉子節點個數：%d", Degree0(T1));printf("\n度為1,2的節點個數分別為：%d,%d", Degree1(T1),Degree2(T1));printf("\n樹的高度：%d", BtDepth(T1));DestroyBiTree(T1); // 銷毀二叉樹，釋放內存return 0;
}
三、總結與提示
-
時間復雜度分析：所有遍歷算法的時間復雜度均為O(n)，其中n為節點數量
-
空間復雜度分析：
-
遞歸遍歷：O(h)，h為樹高（遞歸棧空間）
-
非遞歸中序遍歷：O(h)（棧空間）
-
層序遍歷：O(w)，w為樹的最大寬度（隊列空間）
-
-
實用技巧：
-
先序+中序或后序+中序可以唯一確定一棵二叉樹
-
遞歸算法簡潔但可能存在棧溢出風險，非遞歸算法更安全
-
銷毀二叉樹務必使用后序遍歷，避免內存泄漏
-
四、附錄
????????完整源碼位于資源包中，有需要請自取。后續將繼續分享更多數據結構與算法相關內容。
? ? ? ? 數據結構專欄-實現源碼(基于C語言)資源-CSDN下載
