二叉樹特殊類型

二叉樹（Binary tree）是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹顯得特別重要。二叉樹特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，且有左右之分。

二叉樹是 n 個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根（root）的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。在二叉樹中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。

二叉樹的類型

全二叉樹

在這種類型的樹中，除了葉子之外的所有節(jié)點(diǎn)都有兩個(gè)孩子。

完美二叉樹

所有內(nèi)部節(jié)點(diǎn)都有兩個(gè)孩子，所有葉子都在同一級(jí)別。

退化二叉樹

在這種樹中，所有節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)。

完全二叉樹

就像一棵完整的二叉樹，所有的層次都被填滿，但所有的葉子都應(yīng)該向左傾斜。

平衡二叉樹

左右子樹高度差的絕對(duì)值小于等于1。

| height(left_sub_tree) - height(right_sub_tree) | <= 1

偏斜二叉樹

所有節(jié)點(diǎn)只有一個(gè)孩子，除了最后一個(gè)（葉子）沒(méi)有孩子。分為左偏二叉樹和右偏二叉樹兩種。