數據結構自學Days10 -- 二叉樹的常用實現

? 一、為什么要學習二叉樹？

1. 📦 組織數據的高效方式

二叉樹可以快速插入、刪除、查找數據，尤其在平衡時，時間復雜度為 $O(\log n)$。
適合表示分層結構（如組織結構、文件系統、語法樹）。

2. 💡 各種高級結構的基礎

很多更復雜的數據結構都以二叉樹為基礎，例如：

堆（Heap）：用于實現優先隊列
平衡樹（如 AVL、紅黑樹）：用于快速搜索和動態數據更新
線段樹、區間樹、樹狀數組：用于范圍查詢
表達式樹、Huffman 樹：用于編譯器、壓縮算法等

3. 🧠 算法題中的常客

很多算法競賽、筆試題會考查二叉樹的構造、遍歷、查找、平衡、路徑計算等問題。
是程序員面試中的高頻知識點

4、二叉樹的常用功能

功能	說明
? 遍歷	先序、中序、后序、層序遍歷
🔍 搜索	二叉搜索樹（BST）可高效查找
📁 分層結構表示	文件系統、組織架構樹、語法樹
🧮 表達式處理	表達式樹支持中綴轉后綴、求值
🧠 平衡維護	AVL、紅黑樹保證查找平衡性
🔧 范圍查詢	線段樹、區間樹等支持快速區間操作
🔗 哈夫曼編碼	構造最優前綴編碼
🔄 結構轉換	鏡像、翻轉、扁平化等結構操作

二叉樹是一種既基礎又強大的數據結構，學習它不僅是算法的入門，也是邁向更高階算法和工程應用的必經之路。

下面我們總結一下對于二叉樹言的常用接口包括：

二、二叉樹的常用實現

1、如何創建二叉樹。2、銷毀創建的二叉樹釋放內存。3、計算二叉樹的節點個數。4、計算二叉樹葉節點的個數。5、計算二叉樹第k層的節點個數。6、找到二叉樹中指定的節點。7、二叉樹的前序，后序，中序。8、層序遍歷（利用隊列實現）。9、判斷是否為完全二叉樹。

1、如何創建二叉樹

代碼實現：

typedef char BTreeDataType;typedef struct BTreeNode
{BTreeDataType _data;struct BTreeNode* _left;struct BTreeNode* _right;
}BTreeNode;BTreeNode* CreateTree(BTreeDataType* str,int* pi){if(*str == '\0'){return NULL;}if(str[*pi] == '#'){(*pi)++;return NULL;}BTreeNode* root = (BTreeNode*)malloc(sizeof(BTreeNode));root->_data = str[*pi];(*pi)++;root->_left = CreateTree(str,pi);root->_right = CreateTree(str,pi);return root;
}

測試函數：

int main(){char str[100] = {0};scanf("%s",str);int i = 0;BTreeNode* root = CreateTree(str,&i);}
輸入：ABC##DE#G##F###，注意這里我們構建二叉樹是通過“前序遍歷的思想”

2、銷毀創建的二叉樹釋放內存

void BTree_Destroy(BTreeNode* root){if(!root){return;}BTree_Destroy(root->_left);BTree_Destroy(root->_right);free(root);root = NULL;
}

3、計算二叉樹的節點個數

? ? ? ? 利用前序遍歷的思想進行二叉樹的遍歷，統計非空子樹即可，可參考二叉樹的前序遍歷。

int BTreeSize(BTreeNode* root){if(!root){return 0;}return 1+ BTreeSize(root->_left)+BTreeSize(root->_right);
}

4、計算二叉樹葉節點的個數

?? ? ? ?同樣你可以利用前序遍歷的思想，但是統計葉節點，需滿足左右子樹為空才統計

int BTreeLeafSize(BTreeNode* root){if(!root){return 0;}if(!(root->_left) && !(root->_right)){return 1;}return (BTreeLeafSize(root->_left)+BTreeLeafSize(root->_right));
}

5、計算二叉樹第k層的節點個數。

? ? ? ? 這里我們需要輸入k這個參數，首先我們需要找到第k層，當遍歷二叉樹時，遍歷至當前節點的左右子樹，則k--，知道k==0時，就是我們的第k層，然后在統計節點個數就行。? ? ? ??

代碼實現:

int BTreeLevelKSize(BTreeNode* root,int k){if(!root){return 0;}k--;if(k == 0){return 1;}return (BTreeLevelKSize(root->_left,k)+BTreeLevelKSize(root->_right,k));
}

6、找到二叉樹中指定的節點

?? ? ? ?只需判斷節點值是否為指定值，是就直接返回當前節點，否則繼續遍歷。

代碼實現：

BTreeNode* BTreeFind(BTreeNode* root,int _val){if(!root){return NULL;}if(root->_data == _val){return root;}BTreeNode* node = BTreeFind(root->_left,_val);if(node){return node;}node = BTreeFind(root->_right,_val);if(node){return node;}return NULL;
}

7、二叉樹的前序，后序，中序

?? ? ? ?這部分內容我們已經實現過很多次了，這里直接給出源碼

代碼實現：

//前序
void PreOrder(BTreeNode* root){if(!root){printf("NULL");return;}printf("%c ",root->_data);PreOrder(root->_left);PreOrder(root->_right);return;
}
//中序
void InOrder(BTreeNode* root){if(!root){printf("NULL");return;}InOrder(root->_left);printf("%c ",root->_data);InOrder(root->_right);return;
}
//后序
void PostOrder(BTreeNode* root){if(!root){printf("NULL");return;}PostOrder(root->_left);PostOrder(root->_right);printf("%c ",root->_data);return;
}

8、層序遍歷（利用隊列實現）

? ? ? ? 這里我們需要使用到隊列的思想，“先進先出”，當前節點不為空，我們把當前節點放入隊列中，然后再輸出該節點，然后將該節點的左右子節點放入隊列，然后再刪除左節點，再把左節點的左右子節點再放入，當節點為空時不再放入，當隊列為空時不在放出，不斷重復放入放出。就是層序遍歷。

思維導圖：

代碼實現：

//隊列的聲明
typedef struct Queue
{QueueDataType btnode;struct Queue* next;}Queue;typedef struct my_Queue{Queue* _head;Queue* _tail;
}my_Queue;//隊列初始化
my_Queue* Queue_Init(){my_Queue* pq = (my_Queue*)malloc(sizeof(my_Queue));pq->_head = pq->_tail = NULL;return pq;
}
//隊列的摧毀
void QueueDestroy(my_Queue* pq){assert(pq);Queue* Cur = pq->_head;while (Cur){Queue* Del = Cur;Cur = Cur->next;free(Del);}pq->_head = pq->_tail = NULL;return;
}
//插入元素
void QueuePush(my_Queue* pq,QueueDataType _val){assert(pq);Queue* NewNode = (Queue*)malloc(sizeof(Queue));NewNode->btnode = _val;NewNode->next = NULL;if(pq->_head == NULL){pq->_tail = NewNode;pq->_head = NewNode;  }else{pq->_tail->next = NewNode;pq->_tail = NewNode;}
}
// 刪除元素
void QueuePop(my_Queue* pq){assert(pq);if(pq->_head == NULL){return;}else{Queue* Cur = pq->_head;pq->_head = (pq->_head)->next;free(Cur);}if(pq->_head == NULL){pq->_tail = NULL;}return;
}// 返回隊列開頭元素
QueueDataType QueueFront(my_Queue* pq){assert(pq);if(pq->_head){return pq->_head->btnode;}return NULL;
}//判斷隊列是否為空
bool IsQueueEmpty(my_Queue* pq){assert(pq);return !pq->_head;
}

隊列的構建以及常用函數的實現：參考棧與隊列的實現

//層序遍歷
void BTree_LevelOrder(BTreeNode* root){if(!root){printf("NULL");return;}my_Queue* BTqueue = Queue_Init();QueuePush(BTqueue,root);while (!IsQueueEmpty(BTqueue)){QueueDataType Front = QueueFront(BTqueue);printf("%c ",Front->_data);QueuePop(BTqueue);if(Front->_left){QueuePush(BTqueue,Front->_left);};if(Front->_right){QueuePush(BTqueue,Front->_right);}}QueueDestroy(BTqueue);BTqueue = NULL;return;
}

9、判斷是否為完全二叉樹。

? ? ? ? 完全二叉樹的概念是?除最后一層外，其他層都是滿的，且最后一層從左到右連續填滿。

這里我們需要利用層序遍歷的思想去判斷是否為完全二叉樹。

思維導圖：

代碼實現：

bool IsCompleteTree(BTreeNode* root){if(!root){return true;}my_Queue* BTqueue = Queue_Init();QueuePush(BTqueue,root);bool null_seen = false;while (!IsQueueEmpty(BTqueue)){QueueDataType Front = QueueFront(BTqueue);QueuePop(BTqueue);if(Front == NULL){null_seen = true;}else{if(null_seen){QueueDestroy(BTqueue);BTqueue = NULL;return false;}QueuePush(BTqueue,Front->_left);QueuePush(BTqueue,Front->_right); }}QueueDestroy(BTqueue);BTqueue = NULL;return true;
}

10、測試函數如下：

//測試函數
int main(){char str[100] = {0};scanf("%s",str);int i = 0;BTreeNode* root = CreateTree(str,&i);PreOrder(root);printf("\n");printf("%d ",BTreeSize(root));printf("%d ",BTreeLeafSize(root));printf("%d ",BTreeLevelKSize(root,3));BTreeNode* target = BTreeFind(root,'D');printf("%c ",target->_data);BTree_LevelOrder(root);if(IsCompleteTree(root)){printf("yes\n");}else{printf("No\n");}
}

好了，關于二叉樹的c語言相關的內容就分享到這了，后續有關二叉樹的內容我們利用c++實現。

謝謝大家的點贊和收藏！👍