樹
- 非線性結構
- 樹是n(n >= 0)個元素的集合:
- （1）每個元素稱為結點（node）；
- （2）有一個特定的結點，稱為根結點或根（root）；
- （3）除根結點外，其余結點被分成m（m>=0）個互不相交的有限集合，而每個子集又都是一棵樹（稱為原樹的子樹Subtree）
- 注意
- n = 0時，稱為空樹
- 樹只有一個特殊的沒有前驅的元素，稱為樹的根（Root）
- 樹中除了根結點外，其余元素只能有一個前驅，可以有零個或多個后繼
- 子樹也有自己的根
樹的概念
- 結點（node）：樹中的數據元素
- 結點的度（degree）：結點擁有的子樹的數目稱為度（該結點的分支數），記作d(v)
- 葉子結點：結點的度為0，稱為葉子結點leaf、終端結點、末端結點
- 分支結點：結點的度不為0，稱為非終端結點或分支結點
- 分支：結點之間的關系
- 內部結點：除根結點外的分支結點，也不包括葉子結點
- 樹的度是樹內各結點的度的最大值。? D子樹的度就是3
- 孩子結點（Child）：
- B是A的孩子
- 雙親結點（Parent）：
- C是E,F的雙親
- 兄弟結點（Sibling）：
- 具有相同雙親結點的結點
- B和C是兄弟
- 祖先結點:
- 從根結點到該結點所經分支上所有的點
- A,B,D都是G的祖先結點
- 子孫結點：
- 結點的所有子樹上結點都稱為該結點的子孫
- C的子孫是E,F,J
- 結點的層次（level）：
- 根結點為第一層，根的孩子為第二層，以此類推，記作L(v)
- 樹的深度（高度Depth）：
- 樹的層次的最大值
- 上圖樹深度為4
- 堂兄弟：
- 雙親在同一層的結點
- D,E或F是堂兄弟
- 有序樹
- 結點的子樹是有順序的（兄弟有大小，先后次序）
- 無序樹
- 結點的子樹是無序的，可以交換
- 路徑
- 一條線串下來的，前一個都是后一個的雙親結點
- 路徑長度 ? = ? 路徑上的結點數 – 1 ，也是分支數
- 森林
- m（m>=0）顆不相交的樹的集合
- 對于結點而言，其子樹的集合就是森林。
- A結點的2顆子樹的集合就是森林
樹的特點
- 唯一的根
- 子樹不相交
- 除根以外，每個元素只能有一個前驅，可以有零個或多個后繼
- 根結點沒有雙親，葉子結點沒有孩子
- vi是vj的雙親，則L(vi) = L(vj) – 1, 也就是說雙親比孩子結點的層次小1
- 堂兄弟的雙親未必是兄弟，例如I,J是堂兄弟，而他們的雙親也是堂兄弟
二叉樹
- 每個結點最多2顆子樹
- 二叉樹不存在degree > 2 的結點
- 是有序樹，左子樹、右子樹是順序的，不能交換次序
- 即使某個結點有一顆子樹，也要確定是左子樹還是右子樹
- 二叉樹的五種基本形態
- 空二叉樹
- 只有一個根結點
- 根節點只有左子樹
- 根節點只有右子樹
- 根節點只有左子樹和右子樹
斜樹
- 左斜樹，所有結點都只有左子樹
- 右斜樹，相反
滿二叉樹
- 一顆二叉樹的所有分支結點都有左右子樹，并且所有葉子結點都在最下面一層
- 同樣深度二叉樹中，滿二叉樹結點最多
- k為深度，則結點總數為2**k-1
- 如下圖，深度為4的15個結點的滿二叉樹
完全二叉樹Complete Binary Tree
- 除了最后一層的所有的結點都集中在最左邊，其他層都是滿的
- 完全二叉樹有滿二叉樹引出
- 區別在于他們的最后一層，完全二叉樹最后一層的結點可以不滿
二叉樹的性質
1.在二叉樹的第i層上最多有2**(i-1)個結點
2.深度為 k 的二叉樹，最多有 2**k-1 個結點
3.對任何一顆二叉樹，如果其終端結點數為n0,度數為2的結點數為n3，則有n0 = n2 + 1
- 換句話說，就是葉子結點數 -1 就等于度數為2 的結點數
- 證明
4.其他性質
- 高度為k的二叉樹，至少有k個結點
- 含有n個的結點的二叉樹的高度之多為n，最小為
math.ceil(log2 (n+1))
5.具有n個結點的完全二叉樹的深度為 int(log 2 n) + 1或者math.ceil(log2 (n+1))
6.如果有一顆n個結點的完全二叉樹，結點按照層序編號，如下圖
- 如果i = 1，則結點i是二叉樹的根
- i > 1，雙親是int(i/2），這是向下取整
- 雙親結點是 i, 左孩子結點就是 2i， 右孩子結點就是 2i+1
- 2i > n，則結點 i 無左孩子，即結點i為葉子結點；否則其左孩子結點存在，編號為2i
- 2i+1 > n，則結點 i 無右孩子；這里不能說明結點i沒有左孩子。否則其右孩子結點存在，編號為2i+1
本文來自投稿，不代表Linux運維部落立場，如若轉載，請注明出處：http://www.www58058.com/87842
