一，樹

樹是一種分層結(jié)構(gòu)螺戳。
樹結(jié)構(gòu)之所以在算法理論與實(shí)際應(yīng)用中始終都扮演著最關(guān)鍵的角色醋旦，并且有著不計(jì)其數(shù)的變種，其實(shí)并不足為怪??層次化的概念幾乎蘊(yùn)含于所有事物之中咒劲，乃是它們的本質(zhì)屬性之一顷蟆。從文件系統(tǒng)诫隅、Internet 的域名系統(tǒng)、數(shù)據(jù)庫系統(tǒng)到人類社會(huì)系統(tǒng)帐偎，層次結(jié)構(gòu)無所不在逐纬。

** 節(jié)點(diǎn)的深度 **——從樹根通往任一節(jié)點(diǎn)的路徑長(zhǎng)度，恰好等于該節(jié)點(diǎn)的深度削樊。
樹中的元素也稱作節(jié)點(diǎn)（Node）豁生。此外，按照如下規(guī)則漫贞，樹中的每個(gè)節(jié)點(diǎn)v都被賦予了一個(gè)特殊的指標(biāo)——深度甸箱，記作depth(v)：

• 每個(gè)節(jié)點(diǎn)的深度都是一個(gè)非負(fù)整數(shù)；
• 深度為0 的節(jié)點(diǎn)有且僅有一個(gè)迅脐，稱作樹根（Root）芍殖；
• 對(duì)于深度為k (k≥1)的每個(gè)節(jié)點(diǎn)u，都有且僅有一個(gè)深度為k-1 的節(jié)點(diǎn)v 與之對(duì)應(yīng)谴蔑，稱作u 的父親（Parent）或父節(jié)點(diǎn)豌骏。

樹的深度與高度——樹中所有節(jié)點(diǎn)的最大深度，稱作樹的深度或高度

任一節(jié)點(diǎn)的孩子數(shù)目隐锭，稱作它的“度”（Degree）
一個(gè)節(jié)點(diǎn)是葉子窃躲，當(dāng)且僅當(dāng)它的度數(shù)為零。

樹中節(jié)點(diǎn)的數(shù)目成榜，總是等于邊數(shù)加一
它告訴我們：就漸進(jìn)復(fù)雜度而言，樹中邊的總數(shù)與節(jié)點(diǎn)的總數(shù)相當(dāng)蹦玫。正是基于這一事實(shí)赎婚，在對(duì)涉及樹結(jié)構(gòu)的有關(guān)算法做復(fù)雜度分析時(shí)，我們可以用節(jié)點(diǎn)的數(shù)目來度量樹結(jié)構(gòu)本身的存儲(chǔ)空間復(fù)雜度樱溉。

樹中任何兩個(gè)節(jié)點(diǎn)之間都存在唯一的一條路徑

{ (p, l), (l, f), (f, b), (b, a), (a, d), (d, h), (h, n) }構(gòu)成了一條聯(lián)接于節(jié)點(diǎn)p和n之間長(zhǎng)度為7 的路徑挣输。

二叉樹——每個(gè)節(jié)點(diǎn)均不超過2 度的有序樹，稱作二叉樹（Binary tree）福贞。

二叉樹相關(guān)結(jié)論

• 在二叉樹中撩嚼，深度為k 的節(jié)點(diǎn)不超過2k 個(gè)
• 高度為h 的二叉樹最多包含2h+1-1 個(gè)節(jié)點(diǎn)
• 由n 個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹，高度至少為?log2n?挖帘。
• 在二叉樹中完丽，葉子總是比2 度節(jié)點(diǎn)多一個(gè)。

真二叉樹——不含1 度節(jié)點(diǎn)的二叉樹拇舀，稱作真二叉樹（Proper binary tree）逻族，否則稱作非真二叉樹（Improper binary tree）。

滿二叉樹——若二叉樹T 中所有葉子的深度完全相同骄崩，則稱之為滿二叉樹（Full binary tree）聘鳞，如下圖為高度為3的滿二叉樹

完全二叉樹——若在一棵滿二叉樹中薄辅，從最右側(cè)起將相鄰的若干匹葉子節(jié)點(diǎn)摘除掉，則得到的二叉樹稱作完全二叉樹（Complete binary tree）抠璃。

二站楚，樹抽象數(shù)據(jù)類型及其實(shí)現(xiàn)

1，樹的模型——“父親-長(zhǎng)子-弟弟”模型

根據(jù)樹的定義搏嗡，每個(gè)節(jié)點(diǎn)的所有后代均構(gòu)成了一棵子樹窿春，故從數(shù)據(jù)類型的角度來看，樹彻况、子樹以及樹節(jié)點(diǎn)都是等同的谁尸。這里，將它們統(tǒng)一為一個(gè)類：Tree纽甘。

節(jié)點(diǎn)的結(jié)構(gòu)：

樹的結(jié)構(gòu)：

2良蛮，樹ADT

3悍赢，基于鏈表實(shí)現(xiàn)樹

接口：

package dsa.Tree;

/*
 * 樹ADT接口
 */
public interface Tree {
    // 返回當(dāng)前節(jié)點(diǎn)中存放的對(duì)象
    public Object getElem();

    // 將對(duì)象obj存入當(dāng)前節(jié)點(diǎn)决瞳，并返回此前的內(nèi)容
    public Object setElem(Object obj);

    // 返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
    public TreeLinkedList getParent();

    // 返回當(dāng)前節(jié)點(diǎn)的長(zhǎng)子
    public TreeLinkedList getFirstChild();

    // 返回當(dāng)前節(jié)點(diǎn)的最大弟弟
    public TreeLinkedList getNextSibling();

    // 返回當(dāng)前節(jié)點(diǎn)后代元素的數(shù)目，即以當(dāng)前節(jié)點(diǎn)為根的子樹的規(guī)模
    public int getSize();

    // 返回當(dāng)前節(jié)點(diǎn)的高度
    public int getHeight();

    // 返回當(dāng)前節(jié)點(diǎn)的深度
    public int getDepth();

}

基于鏈表實(shí)現(xiàn)樹結(jié)構(gòu)

package dsa.Tree;

/*
 * 基于鏈表實(shí)現(xiàn)樹結(jié)構(gòu)
 */
public class TreeLinkedList implements Tree {
    private Object element;// 樹根節(jié)點(diǎn)
    private TreeLinkedList parent, firstChild, nextSibling;// 父親左权、長(zhǎng)子及最大的弟弟
            // （單節(jié)點(diǎn)樹）構(gòu)造方法

    public TreeLinkedList() {
        this(null, null, null, null);
    }

    // 構(gòu)造方法
    public TreeLinkedList(Object e, TreeLinkedList p, TreeLinkedList c,
            TreeLinkedList s) {
        element = e;
        parent = p;
        firstChild = c;
        nextSibling = s;
    }

    /*---------- Tree接口中各方法的實(shí)現(xiàn) ----------*/
    // 返回當(dāng)前節(jié)點(diǎn)中存放的對(duì)象
    public Object getElem() {
        return element;
    }

    // 將對(duì)象obj存入當(dāng)前節(jié)點(diǎn)皮胡，并返回此前的內(nèi)容
    public Object setElem(Object obj) {
        Object bak = element;
        element = obj;
        return bak;
    }

    // 返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)；對(duì)于根節(jié)點(diǎn)赏迟，返回null
    public TreeLinkedList getParent() {
        return parent;
    }

    // 返回當(dāng)前節(jié)點(diǎn)的長(zhǎng)子屡贺；若沒有孩子，則返回null
    public TreeLinkedList getFirstChild() {
        return firstChild;
    }

    // 返回當(dāng)前節(jié)點(diǎn)的最大弟弟锌杀；若沒有弟弟甩栈，則返回null
    public TreeLinkedList getNextSibling() {
        return nextSibling;
    }

    // 返回當(dāng)前節(jié)點(diǎn)后代元素的數(shù)目，即以當(dāng)前節(jié)點(diǎn)為根的子樹的規(guī)模
    public int getSize() {
        int size = 1;// 當(dāng)前節(jié)點(diǎn)也是自己的后代
        TreeLinkedList subtree = firstChild;// 從長(zhǎng)子開始
        while (null != subtree) {// 依次
            size += subtree.getSize();// 累加
            subtree = subtree.getNextSibling();// 所有孩子的后代數(shù)目
        }
        return size;// 即可得到當(dāng)前節(jié)點(diǎn)的后代總數(shù)
    }

    // 返回當(dāng)前節(jié)點(diǎn)的高度
    public int getHeight() {
        int height = -1;
        TreeLinkedList subtree = firstChild;// 從長(zhǎng)子開始
        while (null != subtree) {// 依次
            height = Math.max(height, subtree.getHeight());// 在所有孩子中取最大高度
            subtree = subtree.getNextSibling();
        }
        return height + 1;// 即可得到當(dāng)前節(jié)點(diǎn)的高度
    }

    // 返回當(dāng)前節(jié)點(diǎn)的深度
    public int getDepth() {
        int depth = 0;
        TreeLinkedList p = parent;// 從父親開始
        while (null != p) {// 依次
            depth++;
            p = p.getParent();// 訪問各個(gè)真祖先
        }
        return depth;// 真祖先的數(shù)目糕再，即為當(dāng)前節(jié)點(diǎn)的深度
    }
}

三量没，樹的遍歷

所謂樹的遍歷（Traversal），就是按照某種次序訪問樹中的節(jié)點(diǎn)突想，且每個(gè)節(jié)點(diǎn)恰好訪問一次殴蹄。也就是說，按照被訪問的次序猾担，可以得到由樹中所有節(jié)點(diǎn)排成的一個(gè)序列袭灯。

深度優(yōu)先遍歷（Depth-first Traversal）：
前序遍歷、中序遍歷绑嘹、后序遍歷都屬于深度優(yōu)先遍歷

1妓蛮，前序遍歷（Preoder traversal）——中>左>右

PreorderTraversal.PNG

2，中序遍歷（Inorder traversal）——左>中>右

中中序遍歷只有對(duì)二叉樹才有意義

3圾叼，后序遍歷（Postorder traversal）——左>右>中

PostorderTraversal.PNG

廣度優(yōu)先遍歷（Breadth-first traversal）
層次遍歷屬于廣度優(yōu)先遍歷

1蛤克，層次遍歷（Traversal by level）

LevelorderTraversal.PNG