複旦大學961-資料結構-第二章-樹（1）基本概念和術語；樹的性質；樹的定義；樹的周遊

961全部内容連結

文章目錄

• 基本概念和術語
• 樹的性質
• 樹的定義（非二叉樹）
• 樹的周遊（非二叉樹）

基本概念和術語

1. 樹：樹是n個節點的有限集合
2. 空樹：n=0時（一個節點都沒有），稱為空樹。
3. 根：樹最上層的那個節點稱為根
4. 子樹：從樹中抽取一個集合，該集合仍是一棵樹，則這個樹稱為該樹的子樹
5. 樹的高度（或深度）：從根節點算起（包括根節點），樹的層數就是樹的高度
6. 樹的節點關系：
   • 祖先：從根A到節點K的唯一路徑上的任意節點，稱為節點K的祖先
   • 子孫：若節點K是節點B的祖先，那節點B稱為節點K的子孫
   • 雙親：父節點。
   • 孩子：子節點
   • 兄弟：有相同雙親的節點稱為兄弟
7. 節點的度：一個節點的孩子個數稱為該節點的度。
8. 樹的度：樹中節點的最大度數稱為樹的度
9. 分支節點（非終端節點）：度大于0的節點稱為分支節點（非終端節點）
10. 葉子結點（終端節點） ：度為0的節點，即沒有孩子的節點
11. 節點的深度：從根節點開始自頂向下逐層累加的，根節點算1。
12. 節點的高度：從葉節點開始自底向上逐層累加的，葉節點算1。
13. 有序樹：每個節點的左右子樹不能随便換
14. 無序樹：不是有序樹，那就是無序樹
15. 路徑：兩個節點之間所經過的節點序列就是兩個節點之間的路徑
16. 路徑長度：路徑上所經過的邊的個數
17. 森林：多個互不相交的樹，組成森林

樹的性質

1. 樹 中 的 節 點 數 等 于 所 有 節 點 的 度 數 加 1 2. 度 為 m 的 樹 第 i 層 上 至 多 有 m i − 1 個 節 點 ( i ≥ 1 ) 3. 高 度 為 h 的 m 叉 樹 至 多 有 ( 1 − m h ) ( 1 − m ) 節 點 4. 具 有 n 個 節 點 的 m 叉 樹 最 小 高 度 為 ⌈ log ⁡ m ( n ( m − 1 ) + 1 ) ⌉ \begin{aligned} & 1. 樹中的節點數等于所有節點的度數加1 \\ & 2. 度為m的樹第i層上至多有m^{i-1}個節點(i\ge1) \\ & 3. 高度為h的m叉樹至多有 \frac{(1-m^h)}{(1-m)} 節點 \\ & 4. 具有n個節點的m叉樹最小高度為 \lceil \log_m(n(m-1)+1)\rceil \end{aligned} ​1.樹中的節點數等于所有節點的度數加12.度為m的樹第i層上至多有mi−1個節點(i≥1)3.高度為h的m叉樹至多有(1−m)(1−mh)​節點4.具有n個節點的m叉樹最小高度為⌈logm​(n(m−1)+1)⌉​

樹的定義（非二叉樹）

public class TreeNode<AnyType> {
	    AnyType element;
	    TreeNode<AnyType> firstChild;
	    TreeNode<AnyType> nextSibling;  // sibling: 兄弟姐妹
	}
           

樹的周遊（非二叉樹）

todo，前序，後序，層序