一、二叉樹(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)足以下要求:
所有葉子節(jié)點(diǎn)都出現(xiàn)在 k 或者 k-1 層,而且從 1 到 k-1 層必須達(dá)到最大節(jié)點(diǎn)數(shù);第 k 層可以不是滿(mǎn)的,但是第 k 層的所有節(jié)點(diǎn)必須集中在最左邊。?需要注意的是不要把完全二叉樹(shù)和“滿(mǎn)二叉樹(shù)”搞混了,完全二叉樹(shù)不要求所有樹(shù)都有左右子樹(shù),但它要求:任何一個(gè)節(jié)點(diǎn)不能只有左子樹(shù)沒(méi)有右子樹(shù);葉子節(jié)點(diǎn)出現(xiàn)在最后一層或者倒數(shù)第二層,不能再往上。