algorithms_rogramming.jpg
二叉樹(shù)
二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)，就是每一個(gè)節(jié)點(diǎn)度最大是 2 。通常子樹(shù)被稱作左子樹(shù)和右子樹(shù)，二叉樹(shù)是有序樹(shù)，那么什么又是有序樹(shù)和無(wú)序樹(shù)呢？
Binary Tree vs Tree
有序樹(shù)和無(wú)序樹(shù)
如果樹(shù)中結(jié)點(diǎn)的子樹(shù)從左到右看，誰(shuí)在左邊，誰(shuí)在右邊，是有規(guī)定的，這棵樹(shù)稱為有序樹(shù)，反之稱為無(wú)序樹(shù)。
在有序樹(shù)中，一個(gè)結(jié)點(diǎn)最左邊的子樹(shù)稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。
Binary Tree vs Tree
二叉樹(shù)的性質(zhì)
經(jīng)過(guò)前人的總結(jié)，二叉樹(shù)具有以下幾個(gè)性質(zhì)：
- 二叉樹(shù)中，第 i 層最多有
個(gè)結(jié)點(diǎn)，例如在
- 深度為 K 的二叉樹(shù)最多有
個(gè)結(jié)點(diǎn)。
- 二叉樹(shù)中，終端結(jié)點(diǎn)數(shù)（葉子結(jié)點(diǎn)數(shù)）為
，度為 2 的結(jié)點(diǎn)數(shù)為
，則
。
滿二叉樹(shù)
如果二叉樹(shù)中除了葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度都為 2，則此二叉樹(shù)稱為滿二叉樹(shù)。
完全二叉樹(shù)
如果二叉樹(shù)中除去最后一層節(jié)點(diǎn)為滿二叉樹(shù)，且最后一層的結(jié)點(diǎn)依次從左到右分布，則此二叉樹(shù)被稱為完全二叉樹(shù)。
