二叉樹特殊類型

二叉樹(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)有孩子。分為左偏二叉樹和右偏二叉樹兩種。

評(píng)論
圖片
表情
