順序存儲 存儲適用性不強余境，一般只用于完全二叉樹

順序存儲

二叉樹的遍歷

二叉樹的遍歷方式有很多，如果限制了從左到右的習(xí)慣方式灌诅，那么主要就分為四種：

• 前序遍歷(DLR)：根結(jié)點芳来，遍歷左子樹，遍歷右子樹【根左右】百度百科
  

  前序遍歷: ABDGHCEIF

• 中序遍歷(LDR)：遍歷左子樹猜拾，根結(jié)點即舌，遍歷右子樹【左根右】百度百科
  

  中序遍歷: GDHBAEICF

• 后序遍歷(LRD)：遍歷左子樹，遍歷右子樹挎袜，根結(jié)點【左右根】百度百科
  

  后序遍歷：GHDBIEFCA

• 層序遍歷：從根結(jié)點顽聂，從上而下逐層遍歷

  
  
  層序遍歷：ABCDEFGHI

那為什么要有這么多遍歷方法呢

我們用圖形的方式來表現(xiàn)樹的結(jié)構(gòu)，可以非常直觀的理解盯仪，但是對于計算機來說紊搪，它只有循環(huán)、判斷等方式來處理全景，換種方式說耀石，就是它只會處理線性序列，而剛才四種遍歷方法爸黄，都是把樹中的結(jié)點變成某種意義的線性結(jié)構(gòu)滞伟。

推導(dǎo)二叉樹

很多面試會問這個問題揭鳞。給出前序ABCDEF，中序CBAEDF梆奈，問后序是什么野崇？
其實很簡單前序先訪問根結(jié)點 A，中序 A 左邊就是左子樹亩钟，可以根據(jù)上面的圖自己推導(dǎo)著畫一下乓梨，結(jié)果CBEFDA

簡單的二叉樹代碼實現(xiàn)

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ī)則上限制了數(shù)據(jù)。它不僅僅支持快速查找一個數(shù)據(jù)径荔，還支持快速插入、刪除一個數(shù)據(jù)脆霎。

它是怎么做到這些的呢总处？

二叉查找樹要求，在樹中的任意一個節(jié)點睛蛛，其左子樹中的每個節(jié)點的值鹦马，都要小于這個節(jié)點的值，而右子樹節(jié)點的值都大于這個節(jié)點的值忆肾。

時間復(fù)雜度其實都跟樹的高度成正比 O(logn)

散列表和二叉查找樹

散列表的插入荸频、刪除、查找操作的時間復(fù)雜度可以做到常量級的 O(1)
二叉查找樹在比較平衡的情況下客冈，插入旭从、刪除、查找操作時間復(fù)雜度才是 O(logn)
相對散列表场仲，好像并沒有什么優(yōu)勢和悦，那我們?yōu)槭裁催€要用二叉查找樹呢？

• 如果要輸出有序數(shù)據(jù)渠缕，散列表就要先排序鸽素，二叉樹則可以通過中序遍歷在 O(n) 時間復(fù)雜度內(nèi)輸出
• 散列表擴容耗時很多，而且當(dāng)遇到散列沖突時亦鳞，性能不穩(wěn)定馍忽，盡管二叉查找樹的性能不穩(wěn)定，但我們最常用的平衡二叉查找樹的性能非常穩(wěn)定燕差，時間復(fù)雜度穩(wěn)定在 O(logn)遭笋。
• 盡管散列表的查找等操作的時間復(fù)雜度是常量級的，平衡二叉查找樹是 O(logn) 但因為哈希沖突的存在徒探，這個常量不一定比 logn 小坐梯，所以實際的查找速度可能不一定快
• 散列表的構(gòu)造比二叉查找樹要復(fù)雜，需要考慮的東西很多刹帕。比如散列函數(shù)的設(shè)計吵血、沖突解決辦法谎替、擴容、縮容等蹋辅。平衡二叉查找樹只需要考慮平衡性這一個問題钱贯，而且這個問題的解決方案比較成熟、固定侦另。
• 為了避免過多的散列沖突秩命，散列表裝載因子不能太大，特別是基于開放尋址法解決沖突的散列表褒傅，不然會浪費一定的存儲空間弃锐。

平衡二叉查找樹，紅黑樹殿托？紅黑樹