二叉樹的基本知識就不說了，談一些有意思的問題！
想要存儲一棵二叉樹，我們有兩種方法
一種是基于指針或者引用的二叉鏈式存儲法，
一種是基于數組的順序存儲法。
鏈式存儲 大部分二叉樹代碼都是通過這種結構來實現的。
每個節(jié)點有 3 個字段，data 存儲數據，另外兩個是指向左右子節(jié)點的指針
順序存儲 存儲適用性不強，一般只用于完全二叉樹
二叉樹的遍歷
二叉樹的遍歷方式有很多，如果限制了從左到右的習慣方式，那么主要就分為四種：
-
前序遍歷(DLR)：根結點，遍歷左子樹，遍歷右子樹【根左右】百度百科
前序遍歷: ABDGHCEIF -
中序遍歷(LDR)：遍歷左子樹，根結點，遍歷右子樹【左根右】百度百科
中序遍歷: GDHBAEICF -
后序遍歷(LRD)：遍歷左子樹，遍歷右子樹，根結點【左右根】百度百科
后序遍歷：GHDBIEFCA -
層序遍歷：從根結點，從上而下逐層遍歷
層序遍歷：ABCDEFGHI
那為什么要有這么多遍歷方法呢
我們用圖形的方式來表現樹的結構，可以非常直觀的理解，但是對于計算機來說，它只有循環(huán)、判斷等方式來處理，換種方式說，就是它只會處理線性序列，而剛才四種遍歷方法，都是把樹中的結點變成某種意義的線性結構。
推導二叉樹
很多面試會問這個問題。給出前序ABCDEF，中序CBAEDF，問后序是什么？
其實很簡單前序先訪問根結點 A，中序 A 左邊就是左子樹，可以根據上面的圖自己推導著畫一下，結果CBEFDA
簡單的二叉樹代碼實現
class node
{
public $data = null;
public $left = null;
public $right = null;
public $parent = null;
function __construct($data)
{
$this->data = $data;
}
}
class tree
{
public $root = null;
public $size = 0;
public $depth = null;
function __construct($data)
{
$this->root = new node($data);
$this->size++;
$this->depth++;
}
function addNode($arr)
{
foreach ($arr as $value) {
$current = $this->root;
$parent = null;
$currentDept = 1;
while ($current !== null) {
$parent = $current;
if ($value == $current->data) {
continue 2;
} elseif ($current->data > $value) {
$current = $current->left;
} else {
$current = $current->right;
}
$currentDept++;
}
$node = new node($value);
$node->parent = $parent;
if ($parent->data > $value) {
$parent->left = $node;
} else {
$parent->right = $node;
}
if ($this->depth < $currentDept) {
$this->depth++;
}
$this->size++;
}
return true;
}
function showTree()
{
return $this->root;
}
}
二叉查找樹
查找樹其實就是在規(guī)則上限制了數據。它不僅僅支持快速查找一個數據，還支持快速插入、刪除一個數據。
它是怎么做到這些的呢？
二叉查找樹要求，在樹中的任意一個節(jié)點，其左子樹中的每個節(jié)點的值，都要小于這個節(jié)點的值，而右子樹節(jié)點的值都大于這個節(jié)點的值。
時間復雜度其實都跟樹的高度成正比 O(logn)
散列表和二叉查找樹
散列表的插入、刪除、查找操作的時間復雜度可以做到常量級的 O(1)
二叉查找樹在比較平衡的情況下，插入、刪除、查找操作時間復雜度才是 O(logn)
相對散列表，好像并沒有什么優(yōu)勢，那我們?yōu)槭裁催€要用二叉查找樹呢？
- 如果要輸出有序數據，散列表就要先排序，二叉樹則可以通過中序遍歷在 O(n) 時間復雜度內輸出
- 散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩(wěn)定，盡管二叉查找樹的性能不穩(wěn)定，但我們最常用的平衡二叉查找樹的性能非常穩(wěn)定，時間復雜度穩(wěn)定在 O(logn)。
- 盡管散列表的查找等操作的時間復雜度是常量級的，平衡二叉查找樹是 O(logn) 但因為哈希沖突的存在，這個常量不一定比 logn 小，所以實際的查找速度可能不一定快
- 散列表的構造比二叉查找樹要復雜，需要考慮的東西很多。比如散列函數的設計、沖突解決辦法、擴容、縮容等。平衡二叉查找樹只需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定。
- 為了避免過多的散列沖突，散列表裝載因子不能太大，特別是基于開放尋址法解決沖突的散列表，不然會浪費一定的存儲空間。
平衡二叉查找樹，紅黑樹？紅黑樹
