這篇文章收錄在我的 Github 上 algorithms-tutorial，另外記錄了些算法題解，感興趣的可以看看，轉(zhuǎn)載請(qǐng)注明出處。

(一) 基本概念

樹是一種數(shù)據(jù)結(jié)構(gòu)，它看上去像一棵 "圣誕樹"，它的根在上，葉朝下。

樹有多個(gè)節(jié)點(diǎn)(node)，用以儲(chǔ)存元素。某些節(jié)點(diǎn)之間存在一定的關(guān)系，用連線表示，連線稱為邊(edge)。邊的上端節(jié)點(diǎn)稱為父節(jié)點(diǎn)，下端稱為子節(jié)點(diǎn)。樹像是一個(gè)不斷分叉的樹根。

例如：

tree.jpg

樹要嗎為空樹(empty tree)，要嗎具有以下特性：

1. 每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)(children)，而該節(jié)點(diǎn)是相應(yīng)子節(jié)點(diǎn)的父節(jié)點(diǎn)(parent) - 比如說(shuō)，1,2 是 0 的子節(jié)點(diǎn)，3 是 7,8 的父節(jié)點(diǎn)
2. 樹有一個(gè)沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)，稱為根節(jié)點(diǎn)(root) - 比如圖中的 0 節(jié)點(diǎn)
3. 沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)(leaf) - 比如圖中的 7，8，9，10 節(jié)點(diǎn)
4. 兩個(gè)具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)(sibling) - 比如圖中 4，5 節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)
5. 一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)以及子節(jié)點(diǎn)的后代稱為該節(jié)點(diǎn)的子樹 (subtree) - 比如 1 和 1 的子節(jié)點(diǎn)構(gòu)成了節(jié)點(diǎn) 0 的一棵子樹

樹的深度和高度的定義：(這里不太確定)

• 樹的深度(depth)是從根節(jié)點(diǎn)開(kāi)始（其深度為1）自頂向下逐層累加的
• 高度(height)也是從根節(jié)點(diǎn)開(kāi)始（其高度為0）自頂向下逐層累加的

例如：該樹深度為 3，高度為 2。

tree-level.png

我們將根節(jié)點(diǎn)定義為 level0，然后子節(jié)點(diǎn)逐層加一，直到葉節(jié)點(diǎn)。此時(shí)葉節(jié)點(diǎn)的 level 數(shù)即為樹的高度。

(二) 二叉樹 (Binary Tree)

首先，二叉樹(binary)是一種特殊的樹，它是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)，通常子樹被稱作是 "左子樹" 和 "右子樹"，二叉樹常用于實(shí)現(xiàn)二叉搜索樹和二叉堆。(這些在后面都會(huì)介紹)

例如: 下面這個(gè)就是一棵二叉樹

binary-tree.jpg

常見(jiàn)的二叉樹有：完全二叉樹，滿二叉樹，二叉搜索樹，二叉堆，AVL 樹，紅黑樹，哈夫曼樹。這些都會(huì)在后面一一介紹。

(三) 完全二叉樹 (Complete Binary Tree)

若設(shè)二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。

例如:

complete-binary-tree.jpeg

即除了最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。而像這樣就不是完全二叉樹, 例如下圖：(# 代表有元素)

binary-tree.jpg

用途：

完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，堆是一種完全二叉樹或者近似完全二叉樹，所以效率極高。后面介紹的二叉堆也是基于完全二叉樹來(lái)實(shí)現(xiàn)的。

(五) 滿二叉樹 (Full Binary Tree)

很好理解，除最后一層無(wú)任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹被稱之為滿二叉樹。

滿二叉樹一定是完全二叉樹，完全二叉樹不一定滿二叉樹。

例如：

compare.png

一個(gè)高度為 h 的滿二叉樹含有 1 + 2 + 4 + ... + 2^h = 2^(h + 1) - 1個(gè)節(jié)點(diǎn)，所以滿二叉樹的節(jié)點(diǎn)個(gè)數(shù)一定為奇數(shù)。

(六) 二叉搜索樹 (Binary Search Tree)

二叉搜索樹是一種特殊的二叉樹，也可以稱為二叉排序樹，二叉查找樹。除了具有二叉樹的基本性質(zhì)外，它還具備：

1. 樹中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹，通常稱為左子樹和右子樹
2. 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值
3. 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
4. 它的左右子樹仍然是一棵二叉搜索樹 (recursive)

例圖：

binary-search-tree.png

基本操作：

在實(shí)行基本操作之前，我們需要先定義一下基本數(shù)據(jù)類型：

class TreeNode<E extends Comparable<E>>{
    private E data;
    private TreeNode<E> left;
    private TreeNode<E> right;
    TreeNode(E theData){
        data = theData;
        left = null;
        right = null;
    }
}
public class BinarySearchTree<E extends Comparable<E>>{
    private TreeNode<E> root = null;
}

1.樹的遍歷：

假設(shè)我們需要遍歷樹中所有節(jié)點(diǎn)，這里有許多遞歸方法可以實(shí)現(xiàn)：

1.中序遍歷：當(dāng)?shù)竭_(dá)某個(gè)節(jié)點(diǎn)時(shí)，先訪問(wèn)左子節(jié)點(diǎn)，再輸出該節(jié)點(diǎn)，最后訪問(wèn)右子節(jié)點(diǎn)。

代碼實(shí)現(xiàn):

public void inOrder(TreeNode<E> cursor){
    if(cursor == null) return;
    inOrder(cursor.getLeft());
    System.out.println(cursor.getData());
    inOrder(cursor.getRight());
}

2. 前序遍歷：當(dāng)?shù)竭_(dá)某個(gè)節(jié)點(diǎn)時(shí)，先輸出該節(jié)點(diǎn)，再訪問(wèn)左子節(jié)點(diǎn)，最后訪問(wèn)右子節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

public void preOrder(TreeNode<E> cursor){
    if(cursor == null) return;
    System.out.println(cursor.getData());
    inOrder(cursor.getLeft());
    inOrder(cursor.getRight());
}

3. 后序遍歷：當(dāng)?shù)竭_(dá)某個(gè)節(jié)點(diǎn)時(shí)，先訪問(wèn)左子節(jié)點(diǎn)，再訪問(wèn)右子節(jié)點(diǎn)，最后輸出該節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

public void postOrder(TreeNode<E> cursor){
    if(cursor == null) return;
    inOrder(cursor.getLeft());
    inOrder(cursor.getRight());
    System.out.println(cursor.getData());
}

2.樹的搜索：

樹的搜索和樹的遍歷差不多，就是在遍歷的時(shí)候只搜索不輸出就可以了。

例如：我們?cè)跇渲兴阉髟?20

search-element.gif

代碼實(shí)現(xiàn)：

public boolean searchNode(TreeNode<E> node){
    TreeNode<E> currentNode = root;
    while(true){
        if(currentNode == null){
            return false;
        }
        if(currentNode.getData().compareTo(node.getData()) == 0){
            return true;
        }else if(currentNode.getData().compareTo(node.getData()) < 0){
            currentNode = currentNode.getLeft();
        }else{
            currentNode = currentNode.getRight();
        }
    }
}

3.節(jié)點(diǎn)插入：

步驟：

1. 遞歸地去查找該二叉樹，找到應(yīng)該插入的節(jié)點(diǎn)
2. 若當(dāng)前的二叉查找樹為空，則插入的元素為根節(jié)點(diǎn)
3. 若插入的元素值小于根節(jié)點(diǎn)值，則將元素插入到左子樹中
4. 若插入的元素值不小于根節(jié)點(diǎn)值，則將元素插入到右子樹中

比如：我們往樹種插入元素 21

tree-insert-element.gif

代碼實(shí)現(xiàn)：

public void insertNode(TreeNode<E> node){
    TreeNode<E> currentNode = root;
    if(currentNode == null){
        root = node;
        return;
    }else{
        while(true){
            if(node.getData().compareTo(currentNode.getData()) < 0){
                if(currentNode.getLeft() == null){
                    break;
                }else{
                    currentNode = currentNode.getLeft();
                }
            }else if(node.getData().compareTo(currentNode.getData()) > 0){
            
                if(currentNode.getRight() == null){
                    break;
                }else{
                    currentNode = currentNode.getRight();
                }
            }
        }   
    }
    if(node.getData().compareTo(currentNode.getData()) < 0){
        currentNode.setLeft(node);
    }else if(node.getData().compareTo(currentNode.getData()) > 0){
        currentNode.setRight(node);
    }
}

4.節(jié)點(diǎn)刪除：

首先需要搜索該節(jié)點(diǎn)，然后可以分為以下四種情況進(jìn)行討論：

1.如果找不到該節(jié)點(diǎn)，那么什么都不用做

例如：要在樹中刪除元素 22

tree-delete-element-1.gif

2.如果被移除的元素在葉節(jié)點(diǎn)(no children)：那么直接移除該節(jié)點(diǎn)，并且將父節(jié)點(diǎn)原本指向該位置改為 null (如果是根節(jié)點(diǎn)，那就不用修改父節(jié)點(diǎn)指向位置)

例如：要在樹中刪除元素 6

tree-delete-element-2.gif

3.如果刪除的元素只有一個(gè)兒子(one child)：那么也很簡(jiǎn)單，直接刪除該節(jié)點(diǎn)，并且將父節(jié)點(diǎn)原本指向的位置改為該兒子 (如果是根節(jié)點(diǎn)，那么該兒子成為新的根節(jié)點(diǎn))

例如：要在樹中刪除元素 20

tree-delete-element-3.gif

4.如果刪除的元素有兩個(gè)兒子，那么可以取左子樹中最大元素或者右子樹中最小元素進(jìn)行替換，然后將最大元素最小元素原位置置空

例如：要在樹中刪除元素 15

tree-delete-element-4.gif

平衡樹的應(yīng)用：

1. 排序：我們可以將數(shù)據(jù)一個(gè)個(gè)讀取，構(gòu)造出一棵平衡樹。但我們讀取完所有數(shù)據(jù)后，我們可以按次序遍歷該樹。但是在插入的過(guò)程中需要不斷調(diào)整。否則他有可能會(huì)越來(lái)與不平衡，調(diào)整的方式有我們后面介紹的 AVL 樹和紅黑樹兩種方法。
2. 時(shí)間復(fù)雜度為 O(nlog2n + n)
3. 編譯算數(shù)表達(dá)式：
   我們可以將算術(shù)表達(dá)式展現(xiàn)為一棵搜索樹：所有的葉子節(jié)點(diǎn)都是常量或者變量，而除葉節(jié)點(diǎn)外所有節(jié)點(diǎn)都是操作符。

比如：我們可以將 (A + B) * (C + D) * 2 - X / Y展現(xiàn)為

post order.png

(七) 平衡樹 (Balanced Tree)

二叉搜索樹雖然在插入和刪除時(shí)的效率都有所提升，但是如果二叉樹變成了下圖：

LinkList.png

二叉樹快退化成了，那么搜索效率效率就會(huì)變得很低,時(shí)間復(fù)雜度由 logn 退化到 n，這時(shí)候我們需要添加一些額外的條件來(lái)約束它，使其可以保持具有 logn 的時(shí)間復(fù)雜度。

老師上課講的平衡樹跟我在網(wǎng)上搜到的絕大部分平衡樹都不一樣，網(wǎng)上介紹的平衡樹就是 AVL 樹，而老師介紹的則是另一種平衡樹，這里我以老師介紹的為主。

首先平衡樹得是二叉樹，它滿足二叉樹的所有性質(zhì)。

判定是否為平衡樹的條件：將該樹重新排序，若不存在重新排序后的二叉樹的樹高比原來(lái)的樹小，則判定該樹為平衡樹。

比如:

balanced-tree.png

這里有棵樹高度為 2，那么我們知道高度為 1 的樹最多只有三個(gè)節(jié)點(diǎn)，五個(gè)節(jié)點(diǎn)是無(wú)法構(gòu)成一棵高度為 1 的二叉樹，故上圖的二叉樹是平衡樹。

又比如：

no-balanced-tree.png

該樹高度為 3，我們知道一棵高度為 2 的樹最多可以有 2^(h + 1) - 1 = 7(滿二叉樹)的節(jié)點(diǎn)，故圖上的的樹只有五個(gè)節(jié)點(diǎn)，那么它經(jīng)過(guò)重新調(diào)整之后可以變?yōu)橐粋€(gè)高度為 2 的二叉樹，故不符合平衡樹的性質(zhì)，故該樹不是平衡樹。

由上我們可以得出一個(gè)結(jié)論：

1. 如果一棵樹是平衡的，那么它所滿足的節(jié)點(diǎn)數(shù) n 需要滿足 2^h - 1 < n <= 2^(h + 1) - 1
2. 插入和刪除一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度均為: O(logn)
3. 這里雖然有一些算法可以使平衡二叉樹 - 但是它們并沒(méi)什么卵用，因?yàn)槲覀円话愣际窃谔砑踊騽h除操作時(shí)候來(lái)去平衡樹，而不是再一開(kāi)始去平衡樹。