关于javascript:前端算法系列之四数据结构树

在之前曾经介绍了数据结构：栈、队列、链表以及汇合，想理解之前的能够翻看我后期的文章，传送门如下：
前端算法系列之一：工夫复杂度、空间复杂度以及数据结构栈、队列的实现
前端算法系列之二：数据结构链表、双向链表、闭环链表、有序链表
前端算法系列之三：数据结构数据汇合
言归正传咱们通过后面的学习理解曾经理解和把握了一部分的数据结构常识，不过咱们后面所讲到的不论是栈、队列异或是汇合链表其实都是绝对比较简单的数据结构，在咱们应用 js 的时候用个数组或者原生 api 就能满足这类型的构造，所以也是绝对比拟容易了解的。明天咱们要学习的是数据结构中比较复杂的 –树；

树：

树是一种分层数据的形象模型。现实生活中最常见的树的例子是家谱，由一个根节点开始向两边延长。而在咱们理论的编程中这种数据结构也是常常被用到比方：咱们页面的 DOM 树、vue 的组件树、ast 形象语法树等等，那树都有哪些个性呢？通过下图来理解

树是由一系列存在父子关系的节点组成，每一个节点都有一个父节点 (根节点除外) 零个或者多个子节点，位于这一系列节点的顶点的是 根节点 ，根节点是树的起始他是没有父节点的，树中的每一个元素都是 节点 ；没有子节点的成为 叶节点 或者说 内部节点，一颗树的高度取决于所有节点的最大深度值（高度在均衡二叉树中会有用到）。

二叉树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。如上图就是一个二叉树，每个节点最多只有两个子节点，别离是左节点和右节点。

二叉搜寻树

二叉搜寻树（BST）是二叉树的一种，不过它严格要求左子节点要小于父节点，而右子节点要大于父节点。

实现一个二叉搜寻树类

二叉搜寻树中的每个元素都是节点，实现构建一个节点 Node 类，节点有值以及他的左子节点和右子节点

export class TreeNode {constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

和链表相似，通过指针来示意节点之间的关系。在双向链表中，每个节点蕴含两个指针，一个指向下一个节点，另一个指向上一个节点。对于树，应用同样的形式（也应用两个指针），然而一个指向左侧子节点，另一个指向右侧子节点。因而，将申明一个 Node 类来示意树中的每个节点。
接下来咱们实现一个树的类：

import {defaultCompare, COMPARE} from "../util";
import {TreeNode} from "./TreeNode";
export default class BinarySearchTree {constructor(compareFn = defaultCompare) {
   this.compareFn = compareFn;
   this.root = null;
  }
 }

类中初始化根节点 root=null，并且设置一个比拟函数，用于插入、查找键值的时候比拟大小。
先定义二叉树中的一些 api：insert(插入)、search(查找)、inOrderTraverse(中序)、prevOrderTraverse(先序)、postOrderTraverse(后序)、min(最小值)、max(最大值)、remove(删除)。接下来咱们一个一个去解说怎么实现这些 api 办法。
1、insert(key)：向树中插入一个新的键。

insert(key) {if (!this.root) {this.root = new TreeNode(key);
 } else {this.insertNode(this.root, key);
 }
}
insertNode(node, key) {if (this.compareFn(key, node.key) === COMPARE.LESS_THAN) {
  const leftNode = node.left;
 if (!leftNode) {node.left = new TreeNode(key);
 } else {this.insertNode(leftNode, key);
 }
 } else {
  const rightNode = node.right;
 if (!rightNode) {node.right = new TreeNode(key);
 } else {this.insertNode(rightNode, key);
 }
 }
}

insert(key); 向树中插入一个元素，其值大小为 key, 分步骤：
1、在插入的时候会先判断数是否有根节点，如果还没有根节点，那该插入元素就是被赋予根节点；
2、如果存在根节点，则将根节点 root 作为值和 key 一块传入 insertNode(node,key);
3、insertNode 办法首先会将 node 的 key 和传入的 key 进行比拟，如果传入的 key 较小（大），则判断 node 的左（右）子节点，如果左（右）子节点不存在则新插入的 key 节点作为该 node 的左（右）子节点。
4、否则该左（右）子节点作为 node，递归调用 insertNode 反复下面 2、3 步骤。
测试代码：实现构建一个二叉搜寻树；

const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);

测试后果如下图所示：

在这颗二叉搜寻树再插入 6，tree.insert(6), 插入的过程入下图所示;

2、search(key)：在树中查找一个键。如果节点存在，则返回 true；如果不存在，则返回 false。
在树中搜寻某一个节点元素时候也是从根节点登程开始查找遍历，找到了该元素返回 true 没有找到则返回 false；search 办法原理如下步骤：
1、search 办法传入 key 值，首先会调用 searchNode 把根节点和 key 作于参数传入，而后将根节点值和传入的 key 值进行比拟；
2、如果 key 值较小（大），则将传入的节点的左（右）节点的和 key 值传入 searchNode 进行递归调用;
3、此时 searchNode 又会将传入的 node 的值和 key 值进行比拟；
4、如果相等则 return true，并进行搜寻，否则反复 2、3 步骤直到遍历残缺颗树，最初如果还是没有找到就返回 false；

search(key) {return this.searchNode(this.root, key);
}
searchNode(node, key) {if(node){if (this.compareFn(key, node.key) === COMPARE.LESS_THAN) {return this.searchNode(node.left, key);
 } else if(this.compareFn(key, node.key) === COMPARE.BIGGER_THAN){return this.searchNode(node.right, key);
 } else {return true;}
 }
 return false;
}

测试代码：

 tree.search(5);// true
 tree.search(55);// true

小结：
从二叉树的搜寻查找中咱们能够发现如果树散布是平均（也就是均衡二叉树前面会讲到）那在查找的时候他永远都是二分的查找，这种查找形式的工夫复杂度 O(n):log2n。

二叉树的遍历

要遍历完一颗二叉树所有的元素节点，通常是有三种办法：中序遍历、先序遍历、后序遍历。上面咱们来看一下怎么实现这三种遍历形式。

1、中序遍历

中序遍历的特点是如果节点存在左子树就会先去遍历右边始终到左节点为 null 的时候，回溯拜访 node，而后再拜访 node 的右节点始终到拜访遍历完整棵树，对于二叉搜寻树，这样遍历进去的后果就是从小到大的排序(因为二叉搜寻树都是依照严格的左子节点比父节点小，右子节点比父节点大)，实现代码如下：

// 中序
inOrderTraverse(callback) {this.inOrderTraverseNode(this.root, callback);
}
inOrderTraverseNode(node, callback) {if(node) {this.inOrderTraverseNode(node.left, callback);
  callback(node.key);
  this.inOrderTraverseNode(node.right, callback);
 }
}

测试代码：

let arr = [];
tree.inOrderTraverse((key) => arr.push(key));
console.log(arr);// [3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 25]

inOrderTraverse((val) => {arr.push(val)}); 调用该办法时候会调用 inOrderTraverseNode 办法并把根节点传入，而后接着递归左子树，递归完后回溯拜访本节点 node，再接着递归 node 的右子树，始终到遍历完整棵树，过程如下图：

2、先序遍历

先序遍历和中序不同在于先序遍历是先拜访本节点的 key 值再去递归遍历左子树，而后遍历递归右子树，直到遍历残缺颗树；代码实现如下

// 先序
prevOrderTraverse(callback){this.prevOrderTraverseNode(this.root, callback);
}
prevOrderTraverseNode(node, callback){if (node) {callback(node.key);
  this.prevOrderTraverseNode(node.left, callback);
  this.prevOrderTraverseNode(node.right, callback);
 }
}

测试代码：

let arr = [];
tree.prevOrderTraverse((key) => arr.push(key));
console.log(arr);// [11, 7, 5, 3, 9, 8, 10, 15, 13, 12, 14, 20, 18, 25]

3、后序遍历

后序遍历则是先拜访节点的后辈节点，再拜访节点自身。
实现代码如下：

// 后序
postOrderTraverse(callback){this.postOrderTraverseNode(this.root, callback);
}
postOrderTraverseNode(node, callback){if (node) {this.postOrderTraverseNode(node.left, callback);
 this.postOrderTraverseNode(node.right, callback);
 callback(node.key);
 }
}

测试代码：

let arr = [];
tree.postOrderTraverse((key) => arr.push(key));
console.log(arr);//[3, 5, 8, 10, 9, 7, 12, 14, 13, 18, 25, 20, 15, 11]

后序遍历过程如下图：

4、min()、max()返回树中最小 \ 大的值

查找二叉搜寻树中最小的节点，通过二叉搜寻树的个性咱们晓得树的左 (右) 子节点比父节点小 (大)，而左(右) 子树也满足这个条件，所以整个树的最左 (右) 子节点就是最小的值了，实现代码如下：

// 最小值
min(){return this.minNode(this.root);
}
minNode(node) {while (node && node.left) {node = node.left;}
 return node;
}
// 最大值
max(){return this.maxNode(this.root);
}
maxNode(node) {while (node && node.right) {node = node.right;}
 return node;
}

5、remove(key)：从树中移除某个键。

remove(key){this.root = this.removeNode(this.root, key);
}
removeNode(node, key){if (!node) {return null;}
 if (this.compareFn(key, node.key) === COMPARE.LESS_THAN) {node.left = this.removeNode(node.left, key);
 return node;
 } else if (this.compareFn(key, node.key) === COMPARE.BIGGER_THAN) {node.right = this.removeNode(node.right, key);
 return node;
 } else {if (!node.left && !node.right) {
   node = null;
 return node;
 }
  if(!node.left) {
   node = node.right;
 return node;
 }
  if(!node.right) {
   node = node.left;
 return node;
 }
  let minNode = this.minNode(node.right);
 node.key = minNode.key;
 node.right = this.removeNode(node.right, minNode.key);
 return node;
 }
}

二叉搜寻树中删除某一个节点解决起来绝对简单一些：被删除的节点分为三种状况：1、被删除的节点是叶节点（即没有左右子节点）；2、被删除的节点有左或者有右子节点；3、被删除的子节点既有左子节点又有右子节点，针对这三种状况别离解决，上面咱们来离开探讨这三种状况；

1、被删除的节点没有左右子节点；

这种状况是最最简略的，因为没有子节点，咱们只有找到该节点而后把它父节点指向它的指针置于 null 就删除了，几乎是轻松加欢快的实现。
` if (!node.left && !node.right) {
node = null;
return node;
}`
代码中咱们把找到的这个叶节点间接赋值为 null 并将其返回，其实也是绝对于给他的父节点的指针赋值为了 null；比方 tree.remove(3); 首先是先找到 3 这个节点，而后将其置于 null 并返回给父节点；

2、被删除的节点有左或者有右子节点；

这种状况也绝对比较简单，如果被删节点不存在左子节点那就将其右子节点赋值给本人代替本人，并返回，同理如果不存在右子节点，那就将左子节点赋值给本人代替本人，并返回；

if(!node.left) {
 node = node.right;
 return node;
}
if(!node.right) {
 node = node.left;
 return node;
}

代码中实现的就是如果存在右子节点你就用右子节点代替本人，如果左子节点存在就用左子节点代替本人；例如：tree.remove(5);

从上图咱们能够看到首先在树中找到 5 这个节点，而后把 5 这个节点用它的左子节点 3 代替掉，让节点 7 的左子节点间接指向了 3 这个节点，就实现了移除 5 这个元素，独自有右子节点的状况和这种相似。

3、被删除的子节点既有左子节点又有右子节点；

这种状况比后面两种要简单一些，他也是 1、要先找到该节点，而后 2、还要去查找右子树中最小值，来代替该元素而不是间接用子节点去替换，3、同时右子树也要删掉那个最小值并作为该被删除节点的右子节点。

let minNode = this.minNode(node.right);
node.key = minNode.key;
node.right = this.removeNode(node.right, minNode.key);

比方：tree.remove(15)；

总结

到目前为止咱们比较简单的介绍了二叉搜寻树的一些个性以及他的 api, 理解了怎么去插入和删除一个节点以及 3 种遍历树的形式，看起来以及很完满，其实不然这些都只是很现实的状态，比方咱们举例用的这棵树是很理想化的，两边是均衡的，如果咱们在插入的时候一个有序的数，或者咱们刚开始插入的根节点是一个很小或者很大的数，导致后续插入的元素都被偏移到根节点的一侧那这样就不是一颗均衡树了，那他的很多特点就会被进化，比方刚刚说的如果插入的是一个有序的数，那树就会进化成一个链表，造成一条而不是一棵树了。这就引入了树的一个重要类型均衡二叉树（AVLTree），均衡二叉树是会在每次插入的时候调整树的构造，保障树的两侧深度之差绝对值小于等于 1。均衡二叉树以及红黑树将在后续补充，明天就先到这里，谢谢浏览，如有谬误请及时给与斧正。
最初：
想理解更多请看：源码
或者搜寻公众号：非驰名 bug 认证师