一、樹

? ? 1、樹的常用概念

? ? ? ? 節(jié)點：樹中的每個元素稱為節(jié)點

? ? ? ? 父子關(guān)系：相鄰兩節(jié)點的連線，稱為父子關(guān)系

? ? ? ? 根節(jié)點：沒有父節(jié)點的節(jié)點

? ? ? ? 葉子節(jié)點：沒有子節(jié)點的節(jié)點

? ? ? ? 父節(jié)點：指向子節(jié)點的節(jié)點

? ? ? ? 子節(jié)點：被父節(jié)點指向的節(jié)點

? ? ? ? 兄弟節(jié)點：具有相同父節(jié)點的多個節(jié)點稱為兄弟節(jié)點關(guān)系

? ? ? ? 節(jié)點的高度：節(jié)點到葉子節(jié)點的最長路徑（邊數(shù)）

? ? ? ? 節(jié)點的深度：根節(jié)點到這個節(jié)點所經(jīng)歷的邊的個數(shù)

? ? ? ? 節(jié)點的層數(shù)：節(jié)點的深度 + 1（根節(jié)點的層數(shù)是1）

? ? ? ? 樹的高度：根節(jié)點的高度

二、二叉樹

? ? 1、二叉樹的概念

? ? ? ? 二叉樹的每個節(jié)點最多只有2個子節(jié)點的樹，這兩個節(jié)點分別是左子節(jié)點和右子節(jié)點。

? ? ? ? 有一種二叉樹，除了葉子節(jié)點外，每個節(jié)點都有左右兩個子節(jié)點，這種二叉樹叫做滿二叉樹。

? ? ? ? 有一種二樹數(shù)，葉子節(jié)點都在最底下兩層，最后一層葉子節(jié)點都靠左排列，并且除了最后一層，其它層的節(jié)點個數(shù)都要達到最大，這種二叉樹叫做完全二叉樹。

????2、完全叉樹的存儲

? ? ? ? 1）鏈式存儲 ：用鏈表實現(xiàn)；

? ? ? ? 2）順序存儲：用數(shù)組來存儲，完全二叉樹用數(shù)組來存儲時最省內(nèi)存；

? ? 3、二叉樹的遍歷

? ? ? ? 前序遍歷、中序遍歷、后序遍歷；

三、二叉查找數(shù)

? ? ? ? 二叉查找數(shù)又叫二叉搜索樹；二叉查找樹要求，在樹的任意一個節(jié)點，其左子樹中的每個節(jié)點的值，都要小于這個節(jié)點的值，而右子樹的節(jié)點的值都大于這個節(jié)點的值；二叉查找數(shù)的中序遍歷是有序的。

? ? ? ? 如果存在重復(fù)數(shù)據(jù)的二叉查找樹，一種是可? 以利用鏈表讓每個節(jié)點存儲多個值相同的數(shù)據(jù)；另一種是每個節(jié)點中存儲一個數(shù)據(jù)，讓相同的值往右子樹存儲。

? ? ? ? 在二叉樹中，查找、插入、刪除等很多操作的時間復(fù)雜度都跟樹的高度成正比，兩個極端情況的時間復(fù)雜度分別是O(n)和O(logn)，分別對應(yīng)二叉樹退化成鏈表的情況和完全二叉樹。

四、平衡二叉查找樹

? ? ? ? 1、定義：二叉樹中任意一個節(jié)點的左右子樹的高度相差不能大于1。

? ? ? ? 2、平衡二叉查找樹中“平衡的意思，其實就是讓整棵樹左右看起來比較”對稱“、比較”平衡“，不要出現(xiàn)左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應(yīng)的插入、刪除、查找等操作的效率高一些。