摘要：原文博客地址學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)四樹知乎專欄簡書專題前端進(jìn)擊者知乎前端進(jìn)擊者簡書博主博客地址的個(gè)人博客人之所能，不能兼?zhèn)?，棄其所短，取其所長。通常子樹被稱作左子樹和右子樹。敬請(qǐng)期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)五圖參考文章樹數(shù)據(jù)結(jié)構(gòu)二叉樹

總括： 本文講解了數(shù)據(jù)結(jié)構(gòu)中的[樹]的概念，盡可能通俗易懂的解釋樹這種數(shù)據(jù)結(jié)構(gòu)的概念，使用javascript實(shí)現(xiàn)了樹，如有紕漏，歡迎批評(píng)指正。

原文博客地址：學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(四)——樹

知乎專欄&&簡書專題：前端進(jìn)擊者（知乎）&&前端進(jìn)擊者（簡書）

博主博客地址：Damonare的個(gè)人博客

人之所能，不能兼?zhèn)洌瑮壠渌?，取其所長。

在上一篇學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(三)——集合中我們說了集合這種數(shù)據(jù)結(jié)構(gòu)，在學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(一)——棧和隊(duì)列和學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(二)——鏈表說了棧和隊(duì)列以及鏈表這類線性表數(shù)據(jù)結(jié)構(gòu)。接下來這一篇說的是樹這種數(shù)據(jù)結(jié)構(gòu)。首先想讓大家明白的是數(shù)據(jù)結(jié)構(gòu)是個(gè)什么玩意兒，數(shù)據(jù)結(jié)構(gòu)可以分為數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)，所謂的數(shù)據(jù)邏輯結(jié)構(gòu)在我理解就是計(jì)算機(jī)對(duì)于數(shù)據(jù)的組織方式的研究。也就是說研究的是數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系。而數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的具體實(shí)現(xiàn)，也就是說一種邏輯結(jié)構(gòu)可能會(huì)有多種存儲(chǔ)結(jié)構(gòu)與之相對(duì)應(yīng)。

那么我們這一篇所說的樹就是一種數(shù)據(jù)邏輯結(jié)構(gòu)，即研究的是數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系。之前所說的棧、隊(duì)列、鏈表都是一種線性結(jié)構(gòu)，相信大家也能發(fā)現(xiàn)這種線性結(jié)構(gòu)的數(shù)據(jù)關(guān)系有一個(gè)共同點(diǎn)，就是數(shù)據(jù)都是一對(duì)一的，而上一篇說到的集合這種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)是散亂的，他們之間的關(guān)系就是隸屬于同一個(gè)集合，如上一篇例子所說，這些小孩子都是同一個(gè)幼兒園的，但是這些小孩子之間的關(guān)系我們并不知道。線性表(棧、隊(duì)列、鏈表)就是對(duì)這些小孩子關(guān)系的一種表達(dá)(一對(duì)一)。而集合也是對(duì)于這些小孩子關(guān)系的一種表達(dá)。和線性表不同的是，樹這種數(shù)據(jù)結(jié)構(gòu)是一對(duì)多的，也就是說他所描述的是某個(gè)小孩子和其它小孩子之間的關(guān)系。

樹這種結(jié)構(gòu)實(shí)際上我們平時(shí)也有見到，比如下圖這種簡單的思維導(dǎo)圖：

如下也是一棵樹：

關(guān)于樹概念總結(jié)如下:

?1）樹形結(jié)構(gòu)是一對(duì)多的非線性結(jié)構(gòu)。
?2）樹形結(jié)構(gòu)有樹和二叉樹兩種，樹的操作實(shí)現(xiàn)比較復(fù)雜，但樹可以轉(zhuǎn)換為二叉樹進(jìn)行處理。
?3）樹的定義：樹(Tree)是 n(n≥0)個(gè)相同類型的數(shù)據(jù)元素的有限集合。
?4）樹中的數(shù)據(jù)元素叫節(jié)點(diǎn)(Node)。
?5）n=0 的樹稱為空樹(Empty Tree)；
?6）對(duì)于 n＞0 的任意非空樹 T 有：?
???? （1）有且僅有一個(gè)特殊的節(jié)點(diǎn)稱為樹的根(Root)節(jié)點(diǎn)，根沒有前驅(qū)節(jié)點(diǎn)；?
???? （2）若n＞1，則除根節(jié)點(diǎn)外，其余節(jié)點(diǎn)被分成了m(m＞0)個(gè)互不相交的集合
???? ? ? ? T1，T2，。。。，Tm，其中每一個(gè)集合Ti(1≤i≤m)本身又是一棵樹。樹T1，T2，。。。，Tm稱為這棵樹的子樹(Subtree)。?
?7）樹的定義是遞歸的，用樹來定義樹。因此，樹（以及二叉樹）的許多算法都使用了遞歸。?

參看維基百科對(duì)于樹的定義：

在計(jì)算機(jī)科學(xué)中，樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；

沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；

除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；

樹的種類：

無序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹；


有序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹；

二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹；完全二叉樹：對(duì)于一顆二叉樹，假設(shè)其深度為d（d>1）。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹；滿二叉樹：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹；平衡二叉樹（AVL樹）：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹的高度差不大于1的二叉樹；排序二叉樹(二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹)；

霍夫曼樹：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；

B樹：一種對(duì)讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹。

有關(guān)樹的術(shù)語:

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)；

父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；

節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；

堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。

森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

（我是維基百科搬運(yùn)工，哈哈哈）

二叉樹（英語：Binary tree）是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二元堆積。

我們主要研究的就是二叉樹，也就是數(shù)據(jù)為一對(duì)二的關(guān)系。那么在二叉樹中又有些分類；

二叉樹分類：

一棵深度為k，且有個(gè)節(jié)點(diǎn)稱之為滿二叉樹；

深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱之為完全二叉樹。

平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。

1）一棵二叉樹由根結(jié)點(diǎn)、左子樹和右子樹三部分組成，
2） D、L、R 分別代表遍歷根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹，則二叉樹的
3） 遍歷方式有6 種：DLR、DRL、LDR、LRD、RDL、RLD。先左或先右算法基本一樣，所以就剩下三種DLR（先序或是前序）、LDR（中序）、LRD（后序）。

前序遍歷：首先訪問根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，可記錄為根—左—右；

中序遍歷：首先訪問左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹，可記錄為左—根—右；

后序遍歷：首先遍歷左子樹，然后遍歷右子樹，最后遍歷根節(jié)點(diǎn)，可記錄為左—右—根。

以上圖1為例解釋前序遍歷：

首先訪問根節(jié)點(diǎn)a=>然后遍歷左子樹b=>左子樹b的左子樹d=>d的右孩子e>此時(shí)b的左子樹遍歷完，遍歷b的右子樹f=>f的左孩子g=>左子樹b遍歷完，遍歷根節(jié)點(diǎn)的右孩子c，完成=>abdefgc

中序遍歷，后序遍歷就不多說了，不同的只是訪問的順序。

注意：

(1)已知前序、后序遍歷結(jié)果，不能推導(dǎo)出一棵確定的樹；

(2)已知前序、中序遍歷結(jié)果，能夠推導(dǎo)出后序遍歷結(jié)果；

(3)已知后序、中序遍歷結(jié)果，能夠推導(dǎo)出前序遍歷結(jié)果；

二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

? ? （1）若它的左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

? ? （2）若它的右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

? ? （3）它的左、右子樹也分別為二叉查找樹。

首先我們聲明一個(gè)BinarySearchTree類：

function BinarySearchTree() {
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root=null;
}

和鏈表一樣，二叉樹也通過指針來表示節(jié)點(diǎn)之間的關(guān)系。在雙向鏈表中，每一個(gè)節(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，一個(gè)指向上一個(gè)節(jié)點(diǎn)。對(duì)于樹，使用同樣的方式，只不過一個(gè)指向左孩子，一個(gè)指向右孩子?，F(xiàn)在我們給這棵樹弄一些方法：

insert(key):向樹中插入一個(gè)新的鍵(節(jié)點(diǎn));

search(key):在書中查找一個(gè)鍵，如果節(jié)點(diǎn)存在，返回true;如果不存在，返回false;

inOrdertraverse:通過中序遍歷方式遍歷所有節(jié)點(diǎn)；

preorderTraverse:通過先序遍歷方式遍歷所有的節(jié)點(diǎn)；

postOrdertraverse:通過后序遍歷的方式遍歷所有的節(jié)點(diǎn)；

min:返回樹中的最小值；

max:返回樹中的最大值；

remove(key):從樹中移除某個(gè)鍵；

BinarySearchTree類的完整代碼（充分添加注釋）：

function BinarySearchTree() {
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null;
    this.insert = function(key){

        var newNode = new Node(key);

        //判斷是否是第一個(gè)節(jié)點(diǎn)，如果是作為根節(jié)點(diǎn)保存。不是調(diào)用inserNode方法
        if (root === null){
            root = newNode;
        } else {
            insertNode(root,newNode);
        }
    };
    var insertNode = function(node, newNode){
      //判斷兩個(gè)節(jié)點(diǎn)的大小，根據(jù)二叉搜索樹的特點(diǎn)左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
        if (newNode.key < node.key){
            if (node.left === null){
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null){
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    };
    this.getRoot = function(){
        return root;
    };
    this.search = function(key){
        return searchNode(root, key);
    };

    var searchNode = function(node, key){
        if (node === null){
            return false;
        }
        if (key < node.key){
            return searchNode(node.left, key);
        } else if (key > node.key){
            return searchNode(node.right, key);
        } else { //element is equal to node.item
            return true;
        }
    };
    this.inOrderTraverse = function(callback){
        inOrderTraverseNode(root, callback);
    };
    var inOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    };
    this.preOrderTraverse = function(callback){
        preOrderTraverseNode(root, callback);
    };
    var preOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
        }
    };
    this.postOrderTraverse = function(callback){
        postOrderTraverseNode(root, callback);
    };
    var postOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    };
    this.min = function() {
        return minNode(root);
    };
    var minNode = function (node) {
        if (node){
            while (node && node.left !== null) {
                node = node.left;
            }

            return node.key;
        }
        return null;
    };
    this.max = function() {
        return maxNode(root);
    };
    var maxNode = function (node) {
        if (node){
            while (node && node.right !== null) {
                node = node.right;
            }

            return node.key;
        }
        return null;
    };
    this.remove = function(element){
        root = removeNode(root, element);
    };
    var findMinNode = function(node){
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    };
    var removeNode = function(node, element){
        if (node === null){
            return null;
        }
        if (element < node.key){
            node.left = removeNode(node.left, element);
            return node;
        } else if (element > node.key){
            node.right = removeNode(node.right, element);
            return node;
        } else { 
            //處理三種特殊情況
            //1 - 葉子節(jié)點(diǎn)
            //2 - 只有一個(gè)孩子的節(jié)點(diǎn)
            //3 - 有兩個(gè)孩子的節(jié)點(diǎn)
            //case 1
            if (node.left === null && node.right === null){
                node = null;
                return node;
            }
            //case 2
            if (node.left === null){
                node = node.right;
                return node;
            } else if (node.right === null){
                node = node.left;
                return node;
            }
            //case 3
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
        }
    };
}

樹是一種比較常見的數(shù)據(jù)結(jié)構(gòu)，不管是考試還是日常編碼或是面試都是沒法避免的一個(gè)知識(shí)點(diǎn)，此篇總結(jié)不甚完善，紕漏之處還望指出方便之后更改。敬請(qǐng)期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章：[學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)（五）——圖]

樹（數(shù)據(jù)結(jié)構(gòu)）)

二叉樹