學習目標：
- 熟悉樹的定義、表示方法、有關術語和基本概念，
- 掌握二叉樹的遞回定義、二叉樹的性質，
- 掌握二叉樹的兩種存盤方法、特點及適用范圍，
- 掌握二叉樹的各種次序的遍歷，
樹
1.樹的定義
它是由n（n>=1）個有限節點組成一個具有層次關系的集合，把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，（如下圖）
樹（tree）是包含n（n>0）個結點的有窮集，其中：
（1）每個元素稱為結點（node）；
（2）有一個特定的結點被稱為根結點或樹根（root），
（3）除根結點之外的其余資料元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）
2.樹的表示方法
樹形表示方法、嵌套集合表示、凹形表表示、廣義表表示
3.基本術語
為了更清晰看懂，就從下面這張圖來理解
- 度：一棵樹中結點的最大度數稱為該樹的度；
- 葉子結點（終端結點）：度數為零的節點；
- 雙親（父結點）：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
- 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
- 兄弟節點：具有相同父節點的節點互稱為兄弟節點；
- 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
- 樹的高度或深度：樹中節點的最大層次；
- 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
二叉樹
1.二叉樹的定義
二叉樹，就是度不差過2的樹（節點最多有兩個叉）
2.兩種特殊的二叉樹
-
滿二叉樹
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹， -
完全二叉樹
葉節點只能出現在最下層和次下層，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹（只有左邊有枝干）
3.二叉樹的性質
- 性質1：二叉樹第i層上的結點數目最多為 “2的i-1次方”個結點 (i≥1)，
- 性質2：深度為k的二叉樹至多有 “2的k次方-1”個結點(k≥1)，
- 性質3：包含n個結點的二叉樹的高度至少為log2 (n+1)，
- 性質4：在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1，
4.二叉樹的存盤方法
- 4.1 順序存盤結構（僅適用于完全二叉樹）
在順序存盤一棵具有n結點的完全二叉樹，只要從樹根開始自上到下，每層從左至右地給該樹中每個結點進行編號（假定編號從0開始），就能夠得到一個反映整個二叉樹結構地線性序列，
- 4.2 鏈式存盤結構
在二叉樹地鏈式存盤表示中，通常采用地方法：每個結點設定三個域，即值域、左指標域和右指標域，用data表示值，lchild和rchild分別表示指向左右子樹（孩子）地指標域，
5.二叉樹地遍歷
- 5.1遞回遍歷
遞回演算法定義：
a.前序遍歷：根——左——右
b.中序遍歷：左——根——右
c.后序遍歷：左——右——根
有圖來理解：
前序遍歷：
遍歷的結果是：GEDACHS，
中序遍歷：
遍歷的結果是：DEAGHCS
后序遍歷：
遍歷的結果是：DAEHSCG
- 5.非遞回遍歷
恭喜你耐著性子讀完這篇博客啦~
學習建議：
茅盾在他總結自己的讀書經驗時說：“讀名著起碼要讀三遍，
第一遍最好很快地把它讀完，這好像在飛機上鳥瞰桂林城全景；
第二遍要慢慢地讀，細細地咀嚼，注意到各章各段的結構；
第三遍要細細地一段一段地讀、領會、運用，這時要注意它的煉字煉句，”
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317920.html
標籤：其他
上一篇：C語言|排序問題