前言

上一章節主要講解的是C語言哈希表，不清楚的可以回過頭去複習一下。

本章節主要講解的C語言描述的二叉樹的存儲和遍歷。

二叉樹

在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。而二叉搜索樹和二叉堆在後續章節會介紹。

二叉樹有五種基本形態

• (1).空二叉樹；
• (2).只有一個根結點的二叉樹；
• (3).只有左子樹；
• (4).只有右子樹；
• (5).完全二叉樹；

注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形.

二叉樹相關概念

• 樹的結點：包含一個數據元素及若干指向子樹的分支；
• 孩子結點：結點的子樹的根稱為該結點的孩子；
• 雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；
• 兄弟結點：同一雙親的孩子結點； 堂兄結點：同一層上結點；
• 祖先結點: 從根到該結點的所經分支上的所有結點
• 子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫
• 結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；
• 樹的深度：樹中最大的結點層
• 結點的度：結點子樹的個數
• 樹的度： 樹中最大的結點度。
• 葉子結點：也叫終端結點，是度為 0 的結點；

分枝結點：

• 度不為0的結點；
• 有序樹：子樹有序的樹，如：家族樹；
• 無序樹：不考慮子樹的順序；

二叉樹遍歷

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。主要有以下四種遍歷方式:

• 先序遍歷
• 中序遍歷
• 後序遍歷
• 層次遍歷

ps： 層次訪問，通常用 隊列 來做。訪問根，訪問子女，再訪問子女的子女（越往後的層次越低）（兩個子女的級別相同），這裡不做分析討論

二叉樹存儲和實現代碼

1.創建二叉樹結點結構體，以及創建節點函數。

2.插入節點，因為做的無規律二叉樹，故手動連接。

3.遞歸法遍歷二叉樹。

每個結點都需要按照相應的規則去做遍歷，故遞歸實現 ，代碼很簡單，原理自我回味下。

4.非遞歸法

主要採用棧的方式去記錄走過的節點，然後出棧回退去實現，具體原理不多說，詳細講解可參見數據結構視頻專欄。

先序遍歷非遞歸法

中序遍歷非遞歸法

後序遍歷非遞歸法

測試代碼

尾言

本欄目作業:寫出一下二叉樹的三種遍歷結果。

有些人在激烈競爭的洶濤駭浪中被捲走，從此一蹶不振;有些人卻迎著風口、踏上浪尖，上了岸，他們成功了。因為他們多了一份堅持。風口浪尖對於他們來說不是絆腳石，而是墊高自己的基石。

閱讀更多 C語言基礎 的文章

關鍵字: C語言 數據結構 不完美媽媽