国产麻豆一区二区精选,国产乱屌精品,久久色人妻在线

1. 什么是樹？

樹(Tree）是n（n>=0)個結(jié)點(diǎn)的有限集。n=0時稱為空樹。在任意一棵非空樹中：
（1）有且僅有一個特定的稱為根（root）的結(jié)點(diǎn)。
（2）當(dāng)n>1時，其余結(jié)點(diǎn)可分為m（m>0)個互不相交的有限集T₁,T₂,....,T_m, 其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree)

2. 樹的構(gòu)成

1.1 節(jié)點(diǎn)

分類

節(jié)點(diǎn)分類	特點(diǎn)	說明
根(root)	沒有父節(jié)點(diǎn)只有子節(jié)點(diǎn)的節(jié)點(diǎn)
葉子(leaf)/終端節(jié)點(diǎn)	沒有子節(jié)點(diǎn)或者子節(jié)點(diǎn)是空的節(jié)點(diǎn)	葉子結(jié)點(diǎn)度為0
分支節(jié)點(diǎn)/非終端節(jié)點(diǎn)		分支節(jié)點(diǎn)包含根節(jié)點(diǎn)

關(guān)系
- 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)(Parent)：若一個節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)。
- 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)(Child)：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)。
- 兄弟節(jié)點(diǎn)(Sibling)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)。
- 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
- 節(jié)點(diǎn)的子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。

1.2 度

節(jié)點(diǎn)的度數(shù)：節(jié)點(diǎn)孩子的個數(shù)
樹的度：樹中節(jié)點(diǎn)的度最大值。

1.3 層次

層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；

1.4 深度與高度

維基百科

節(jié)點(diǎn)的高度：節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上邊的數(shù)量。葉子節(jié)點(diǎn)高度為0。

節(jié)點(diǎn)的深度：節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上邊的數(shù)量。所有根節(jié)點(diǎn)深度為0。

樹的高度：樹的高度等于根節(jié)點(diǎn)的高度，等于最遠(yuǎn)葉子節(jié)點(diǎn)的深度。

樹的深度：樹的深度等于樹的高度。

樹的寬度：兩個最長路徑的葉子節(jié)點(diǎn)之間節(jié)點(diǎn)數(shù)。

Leetcode

樹的深度：根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)之間最長路徑上節(jié)點(diǎn)的數(shù)量。

樹的高度：根節(jié)點(diǎn)和最遠(yuǎn)葉子節(jié)點(diǎn)之間最長路徑上邊的數(shù)量。
樹的深度與樹的高度是樹中節(jié)點(diǎn)的最大層次

111. 二叉樹的最小深度
104. 二叉樹的最大深度
559. N叉樹的最大深度

3. 樹的分類

樹按照子節(jié)點(diǎn)的數(shù)量分為二叉樹和多叉樹。

二叉樹是n(n>=0)個結(jié)點(diǎn)的有限集合,該集合或者為空集(稱為空二叉樹),每個節(jié)點(diǎn)最多有2個子節(jié)點(diǎn),分別稱為根結(jié)點(diǎn)的左子樹和右子樹。
多叉樹是n(n>=0)個結(jié)點(diǎn)的有限集合,該集合或者為空集(稱為空樹)。每個節(jié)點(diǎn)有多個子節(jié)點(diǎn)。

No.	分類	經(jīng)典分類
1	二叉樹	平衡二叉樹、二叉搜索樹、AVL、堆、紅黑樹
2	多叉樹	2-3樹、B樹、B+樹

樹按照子樹是否有序分為有序樹和無序樹。

有序樹：節(jié)點(diǎn)各子樹從左到右有次序（不能互換）。
無序樹：節(jié)點(diǎn)各子樹從左到右無次序（能互換）。

二叉樹是最簡單，最基礎(chǔ)的樹結(jié)構(gòu)。

4. 特殊的樹

滿二叉樹(Full Binary Tree)：二叉樹中的每個結(jié)點(diǎn)恰好有兩個孩子結(jié)點(diǎn)且所有葉子結(jié)點(diǎn)都在同一層。
完全二叉樹(Complete Binary Tree)：每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。

深度為 $k$ ，有 $n$ 個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為 $k$ 的滿二叉樹中編號從 $1$ 到 $n$ 的結(jié)點(diǎn)一一對應(yīng)，該二叉樹稱為完全二叉樹。 $2^{k-1} ≦n≦2^k-1$

不同的書籍對滿二叉樹和完全二叉樹定義不一樣。
《算法導(dǎo)論》第3版

滿二叉樹：每個節(jié)點(diǎn)是葉節(jié)點(diǎn)或者度為2.

完全二叉樹：所有葉節(jié)點(diǎn)深度相同，且所有內(nèi)部節(jié)點(diǎn)度為2. （樹的節(jié)點(diǎn)總數(shù)達(dá)到最大）

5. 二叉樹的性質(zhì)

5.1 通用性質(zhì)

在非空二叉樹上，第 $i$ 層至多有 $2^{i-1}$ 個結(jié)點(diǎn)。
深度為 $k$ 的二叉樹至多有 $2^k-1$ 個結(jié)點(diǎn)；
對任何一個二叉樹，若其葉子結(jié)點(diǎn)數(shù)為 $n_0$ ，度為 $2$ 的節(jié)點(diǎn)數(shù)為 $n_2$ ，則 $n_0=n_2+1$ ；

5.2 滿二叉樹的性質(zhì)

深度為 $k$ 的滿二叉樹且有 $2^k-1$ 個結(jié)點(diǎn)。

5.3 完全二叉樹的性質(zhì)

$n$ 個結(jié)點(diǎn)的完全二叉樹的深度 $k=[log2 n]+1$ ,這里這個符號 $[x]$ 表示小于等于 $x$ 的整數(shù);
若對一棵有個結(jié)點(diǎn)的完全二叉樹(深度為)的結(jié)點(diǎn)按層（從第層到第層)序自左至右進(jìn)行編號,則對于編號為（)的結(jié)點(diǎn)：
1. 如果 $i=1$ ，則結(jié)點(diǎn) $i$ 是二叉樹的根，無雙親結(jié)點(diǎn)；如果 $i>1$ ，則其雙親結(jié)點(diǎn)編號是 $[i/2]$ 。
2. 如果 $2i>n$ ：則結(jié)點(diǎn) $i$ 為葉子結(jié)點(diǎn)，無左孩子；否則，其左孩子結(jié)點(diǎn)編號是 $2i$ 。
3. 如果 $2i+1>n$ ：則結(jié)點(diǎn) $i$ 無右孩子；否則，其右孩子結(jié)點(diǎn)編號是 $2i+1$ 。