一、二叉樹(shù)、二叉查找樹(shù)、二叉排序樹(shù)、二叉平衡樹(shù)

二叉樹(shù)：每個(gè)結(jié)點(diǎn)非常多 2 棵子樹(shù)，沒(méi)有其它限制了。

二叉查找樹(shù)：也叫二叉搜索樹(shù)，首先它是二叉樹(shù)，并且左子樹(shù)上所有結(jié)點(diǎn)的值 小于 它根結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值大于它根結(jié)點(diǎn)的值。

二叉排序樹(shù)：就是二叉查找樹(shù)。

二叉平衡樹(shù)：更加準(zhǔn)確的應(yīng)該叫 “平衡二叉樹(shù)”，它是 “平衡二叉搜索樹(shù)” 的簡(jiǎn)稱(chēng)。首先它是 “二叉搜索樹(shù)”，其次，它是平衡的，即是它的每一個(gè)結(jié)點(diǎn)的左子樹(shù)的高度和右子樹(shù)的高度差至多為 1。

總結(jié)來(lái)說(shuō)，二叉樹(shù)就是每個(gè)節(jié)點(diǎn)非常多有兩個(gè)子節(jié)點(diǎn)的樹(shù)。它對(duì)節(jié)點(diǎn)的內(nèi)容沒(méi)要求。二叉排序樹(shù) = 二叉查找樹(shù)。它是一種二叉樹(shù)，但是對(duì)節(jié)點(diǎn)內(nèi)容有要求。每個(gè)節(jié)點(diǎn)的左子樹(shù)（如果有的話）里所有節(jié)點(diǎn)的值都必須小于當(dāng)前節(jié)點(diǎn)的值；每個(gè)節(jié)點(diǎn)的右子樹(shù)（如果有的話）里所有節(jié)點(diǎn)的值都必須大于當(dāng)前節(jié)點(diǎn)的值。如果一顆二叉樹(shù)看上去基本沒(méi)有缺胳膊少腿（從根到每片葉子的路徑長(zhǎng)度非常多相差1），那么它是棵平衡二叉樹(shù)。對(duì)于一般二叉樹(shù)而言，平衡不平衡沒(méi)啥特別意義，但是對(duì)二叉查找樹(shù)而言，越平衡則查找效率越高。

延伸閱讀：

二、完全二叉樹(shù)

完全二叉樹(shù)是一種特殊的二叉樹(shù)，滿(mǎn)足以下要求：