Tree
樹是一種數(shù)據(jù)結(jié)構(gòu)，由n(>=0)個有限節(jié)點Node組成的一個具有層次關(guān)系的集合瓷患。
樹的特點
- 每個子節(jié)點都只有有限個子節(jié)點或無子節(jié)點骡尽。
- 沒有父節(jié)點的節(jié)點稱為
根節(jié)點(root)。 - 每一個非根節(jié)點
有且僅有一個父節(jié)點擅编。 - 除了根節(jié)點每個子節(jié)點可以分為多個
不相交的子樹攀细。 - 樹里面沒有環(huán)路。
術(shù)語
- 節(jié)點的度(Degree):
For a given node, its number of children. A leaf is necessarily degree zero.
給定節(jié)點的子樹的個數(shù)爱态。 - 樹的度(Degree)
樹中最大節(jié)點的度稱為樹的度 - 兄弟節(jié)點
具有相同父節(jié)的節(jié)點互稱兄弟節(jié)點 - 堂兄弟節(jié)點
父節(jié)點在同一層次的節(jié)點
樹的種類
1.無序樹(又稱自由樹)：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系谭贪。
自由樹就是一個無回路的連通圖，沒有確定根锦担，在自由樹種選取一個頂點做根俭识，成為一個通常的樹。
2.有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系洞渔。
- 有序樹
-
二叉樹 Binary tree：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹套媚。
- 完全二叉樹：一個二叉樹的深度為d,除了d層外，其他各層的節(jié)點數(shù)目均達到最大值磁椒。
- 滿二叉樹：所有葉節(jié)點都在最底層的完全二叉樹
- 平衡二叉樹（ALV樹）：當且僅當任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹堤瘤。
- 排序二叉樹（又稱二叉查找樹、二叉搜索樹浆熔，有序二叉樹）
- 霍夫曼樹（Huffman Coding又稱哈夫曼樹或最優(yōu)二叉樹）：帶權(quán)路徑最短的二叉樹本辐。霍夫曼編碼使用變長編碼表對源符號進行編碼医增，典型應(yīng)用圖文壓縮慎皱。
- B樹 一種對寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數(shù)據(jù)有序叶骨，擁有多于兩個子樹宝冕。典型應(yīng)用mysql索引。
- 紅黑樹邓萨，應(yīng)用于jdk TreeSet中，是一種自平衡二叉查找樹菊卷，是在計算機科學中用到的一種數(shù)據(jù)結(jié)構(gòu)缔恳，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組。
-
