前言
總括： 本文講解了數(shù)據(jù)結(jié)構(gòu)中的[樹]的概念购撼，盡可能通俗易懂的解釋樹這種數(shù)據(jù)結(jié)構(gòu)的概念蔬将，使用javascript實現(xiàn)了樹，如有紕漏渡八，歡迎批評指正只酥。
- 原文博客地址：學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(四)——樹
- 知乎專欄&&簡書專題：前端進(jìn)擊者（知乎）&&前端進(jìn)擊者（簡書）
- 博主博客地址：Damonare的個人博客
人之所能，不能兼?zhèn)溲嚼牵瑮壠渌塘言剩∑渌L。
正文
樹簡介
在上一篇學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(三)——集合中我們說了集合這種數(shù)據(jù)結(jié)構(gòu)哥艇，在學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(一)——棧和隊列和學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(二)——鏈表說了棧和隊列以及鏈表這類線性表數(shù)據(jù)結(jié)構(gòu)绝编。接下來這一篇說的是樹這種數(shù)據(jù)結(jié)構(gòu)。首先想讓大家明白的是數(shù)據(jù)結(jié)構(gòu)是個什么玩意兒貌踏，數(shù)據(jù)結(jié)構(gòu)可以分為數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)十饥，所謂的數(shù)據(jù)邏輯結(jié)構(gòu)在我理解就是計算機(jī)對于數(shù)據(jù)的組織方式的研究。也就是說研究的是數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系祖乳。而數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的具體實現(xiàn)逗堵，也就是說一種邏輯結(jié)構(gòu)可能會有多種存儲結(jié)構(gòu)與之相對應(yīng)。
那么我們這一篇所說的樹就是一種數(shù)據(jù)邏輯結(jié)構(gòu)眷昆，即研究的是數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系蜒秤。之前所說的棧汁咏、隊列、鏈表都是一種線性結(jié)構(gòu)作媚，相信大家也能發(fā)現(xiàn)這種線性結(jié)構(gòu)的數(shù)據(jù)關(guān)系有一個共同點(diǎn)攘滩，就是數(shù)據(jù)都是一對一的，而上一篇說到的集合這種數(shù)據(jù)結(jié)構(gòu)纸泡，數(shù)據(jù)是散亂的漂问，他們之間的關(guān)系就是隸屬于同一個集合，如上一篇例子所說女揭，這些小孩子都是同一個幼兒園的蚤假，但是這些小孩子之間的關(guān)系我們并不知道。線性表(棧吧兔、隊列磷仰、鏈表)就是對這些小孩子關(guān)系的一種表達(dá)(一對一)。而集合也是對于這些小孩子關(guān)系的一種表達(dá)掩驱。和線性表不同的是，樹這種數(shù)據(jù)結(jié)構(gòu)是一對多的冬竟，也就是說他所描述的是某個小孩子和其它小孩子之間的關(guān)系欧穴。
樹這種結(jié)構(gòu)實際上我們平時也有見到，比如下圖這種簡單的思維導(dǎo)圖：
如下也是一棵樹：
關(guān)于樹概念總結(jié)如下:
1）樹形結(jié)構(gòu)是一對多的非線性結(jié)構(gòu)泵殴。
2）樹形結(jié)構(gòu)有樹和二叉樹兩種涮帘，樹的操作實現(xiàn)比較復(fù)雜，但樹可以轉(zhuǎn)換為二叉樹進(jìn)行處理笑诅。
3）樹的定義：樹(Tree)是 n(n≥0)個相同類型的數(shù)據(jù)元素的有限集合调缨。
4）樹中的數(shù)據(jù)元素叫節(jié)點(diǎn)(Node)。
5）n=0 的樹稱為空樹(Empty Tree)吆你；
6）對于 n＞0 的任意非空樹 T 有：
（1）有且僅有一個特殊的節(jié)點(diǎn)稱為樹的根(Root)節(jié)點(diǎn)弦叶，根沒有前驅(qū)節(jié)點(diǎn)；
（2）若n＞1妇多，則除根節(jié)點(diǎn)外伤哺，其余節(jié)點(diǎn)被分成了m(m＞0)個互不相交的集合
T1，T2者祖，立莉。。七问。蜓耻，Tm，其中每一個集合Ti(1≤i≤m)本身又是一棵樹械巡。樹T1刹淌，T2饶氏，。芦鳍。嚷往。，Tm稱為這棵樹的子樹(Subtree)柠衅。
7）樹的定義是遞歸的皮仁，用樹來定義樹。因此菲宴，樹（以及二叉樹）的許多算法都使用了遞歸贷祈。
參看維基百科對于樹的定義：
在計算機(jī)科學(xué)中，樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)喝峦，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合势誊。它是由n（n>=1）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹谣蠢，也就是說它是根朝上粟耻，而葉朝下的。它具有以下的特點(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)可以分為多個不相交的子樹册烈；
樹的種類：
- 無序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹婿禽，也稱為自由樹赏僧；
- 有序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹扭倾；
- 二叉樹：每個節(jié)點(diǎn)最多含有兩個子樹的樹稱為二叉樹淀零；完全二叉樹：對于一顆二叉樹，假設(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樹：一種對讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹占调，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個子樹移剪。
有關(guān)樹的術(shù)語:
- 節(jié)點(diǎn)的度：一個節(jié)點(diǎn)含有的子樹的個數(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)：若一個節(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)的子節(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）是每個節(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)访雪。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）详瑞。二叉樹常被用于實現(xiàn)二叉查找樹和二元堆積。
我們主要研究的就是二叉樹臣缀，也就是數(shù)據(jù)為一對二的關(guān)系坝橡。那么在二叉樹中又有些分類；
二叉樹分類：
- 一棵深度為k精置，且有個節(jié)點(diǎn)稱之為滿二叉樹计寇；{\displaystyle 2^{\begin{aligned}k+1\end{aligned}}-1}
- 深度為k，有n個節(jié)點(diǎn)的二叉樹脂倦，當(dāng)且僅當(dāng)其每一個節(jié)點(diǎn)都與深度為k的滿二叉樹中番宁，序號為1至n的節(jié)點(diǎn)對應(yīng)時，稱之為完全二叉樹赖阻。
- 平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法）蝶押，它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1火欧，并且左右兩個子樹都是一棵平衡二叉樹棋电。
二叉樹的遍歷
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>此時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é)果牺勾；
二叉搜索樹的創(chuàng)建
二叉查找樹（BinarySearch Tree，也叫二叉搜索樹阵漏，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹驻民，或者是具有下列性質(zhì)的二叉樹：
（1）若它的左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值履怯；
（2）若它的右子樹不為空回还，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
（3）它的左叹洲、右子樹也分別為二叉查找樹柠硕。
首先我們聲明一個BinarySearchTree類：
function BinarySearchTree() {
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
};
var root=null;
}
和鏈表一樣，二叉樹也通過指針來表示節(jié)點(diǎn)之間的關(guān)系运提。在雙向鏈表中蝗柔，每一個節(jié)點(diǎn)有兩個指針，一個指向下一個節(jié)點(diǎn)民泵，一個指向上一個節(jié)點(diǎn)癣丧。對于樹，使用同樣的方式栈妆，只不過一個指向左孩子胁编，一個指向右孩子。現(xiàn)在我們給這棵樹弄一些方法：
- insert(key):向樹中插入一個新的鍵(節(jié)點(diǎn));
- search(key):在書中查找一個鍵鳞尔，如果節(jié)點(diǎn)存在嬉橙，返回true;如果不存在，返回false;
- inOrdertraverse:通過中序遍歷方式遍歷所有節(jié)點(diǎn)铅檩；
- preorderTraverse:通過先序遍歷方式遍歷所有的節(jié)點(diǎn)憎夷；
- postOrdertraverse:通過后序遍歷的方式遍歷所有的節(jié)點(diǎn)莽鸿；
- min:返回樹中的最小值昧旨；
- max:返回樹中的最大值；
- remove(key):從樹中移除某個鍵祥得；
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);
//判斷是否是第一個節(jié)點(diǎn)兔沃，如果是作為根節(jié)點(diǎn)保存。不是調(diào)用inserNode方法
if (root === null){
root = newNode;
} else {
insertNode(root,newNode);
}
};
var insertNode = function(node, newNode){
//判斷兩個節(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 - 只有一個孩子的節(jié)點(diǎn)
//3 - 有兩個孩子的節(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)，不管是考試還是日常編碼或是面試都是沒法避免的一個知識點(diǎn)饮焦，此篇總結(jié)不甚完善怕吴，紕漏之處還望指出方便之后更改窍侧。敬請期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章：[學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)（五）——圖]
參考文章
- [樹（數(shù)據(jù)結(jié)構(gòu)）](https://zh.wikipedia.org/wiki/樹_(數(shù)據(jù)結(jié)構(gòu))
- 二叉樹
