簡(jiǎn)介

二叉樹(shù)的相關(guān)概念，如，樹(shù)高度，節(jié)點(diǎn)層數(shù)，節(jié)點(diǎn)度數(shù)，路徑，葉節(jié)點(diǎn)，分支節(jié)點(diǎn)，根節(jié)點(diǎn)，父節(jié)點(diǎn)，左節(jié)點(diǎn)，右節(jié)點(diǎn)，兄弟節(jié)點(diǎn)，祖先節(jié)點(diǎn)，子孫節(jié)點(diǎn)，左子樹(shù)，右子樹(shù)等基本概念，不再贅述。
二叉樹(shù)分類(lèi)

1、完全二叉樹(shù)

若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹(shù)。
一維數(shù)組可以作為完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，堆排序使用的數(shù)據(jù)結(jié)構(gòu)就是完全二叉樹(shù)。

2、滿(mǎn)二叉樹(shù)

國(guó)際標(biāo)準(zhǔn)定義是除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子結(jié)點(diǎn)的二叉樹(shù)
在這里插入圖片描述
國(guó)內(nèi)的定義是：除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)。很顯然，按照這個(gè)定義，上面的圖示二叉樹(shù)就不是滿(mǎn)二叉樹(shù)。

3、擴(kuò)充二叉樹(shù)

擴(kuò)充二叉樹(shù)是對(duì)已有二叉樹(shù)的擴(kuò)充，擴(kuò)充后的二叉樹(shù)的節(jié)點(diǎn)都變?yōu)槎葦?shù)為2的分支節(jié)點(diǎn)。也就是說(shuō)，如果原節(jié)點(diǎn)的度數(shù)為2，則不變，度數(shù)為1，則增加一個(gè)分支，度數(shù)為0的葉子節(jié)點(diǎn)則增加兩個(gè)分支。

4、平衡二叉樹(shù)

是一棵空樹(shù)或它的任意節(jié)點(diǎn)的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1
在這里插入圖片描述
二叉樹(shù)的應(yīng)用場(chǎng)景
普通的二叉樹(shù)，很難構(gòu)成現(xiàn)實(shí)的應(yīng)用場(chǎng)景，但因其簡(jiǎn)單，常用于學(xué)習(xí)研究，平衡二叉樹(shù)則是實(shí)際應(yīng)用比較多的。常見(jiàn)于快速匹配、搜索等方面。
常用的樹(shù)有：AVL樹(shù)、紅黑樹(shù)、B+樹(shù)、Trie（字典）樹(shù)。

1、AVL樹(shù):

最早的平衡二叉樹(shù)之一。應(yīng)用相對(duì)其他數(shù)據(jù)結(jié)構(gòu)比較少。windows對(duì)進(jìn)程地址空間的管理用到了AVL樹(shù)。

2、紅黑樹(shù):

平衡二叉樹(shù)，廣泛用在C++的STL中。如map和set都是用紅黑樹(shù)實(shí)現(xiàn)的。還有Linux文件管理。

3、B/B+樹(shù):

用在磁盤(pán)文件組織 數(shù)據(jù)索引和數(shù)據(jù)庫(kù)索引。

4、Trie樹(shù)(字典樹(shù)):

用在統(tǒng)計(jì)和排序大量字符串，如自動(dòng)機(jī)、M數(shù)據(jù)庫(kù)索引。

二叉樹(shù)的構(gòu)建

0、遍歷方式

前序遍歷：root -> left -> right
中序遍歷：left -> root -> right
后續(xù)遍歷：left ->right -> root
層序遍歷：按照層次遍歷