上篇文章也提到了二叉树的劣势以及重要性，那么就让咱们来着手封装一个二叉树吧。咱们先来看看它有哪些常见的操作方法。
二叉搜寻树常见的操作
insert(key):向树中插入一个新的键
search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false
preOrderTraverse：通过先序遍历形式遍历所有节点
inOrderTraverse:通过中序遍历形式遍历所有节点
postorderTraverse:通过后序遍历形式遍历所有节点
min：返回树中最小的值
max:返回树中最大的值
remove(key)：从树中移除某个键
insert（插入）办法
封装代码前咱们先来捋一下insert的逻辑
要向树中插入一个新的节点或键要经验三个步骤。
1 第一步是验证插入操作树是否为一个空树。如果是,咱们要做的就是创立一个Node 类的实例并将它赋值给 root(根节点) 属性。
2 如果树非空须要找到插入新节点的地位，寻找对应节点的办法：
如下图，如果咱们须要在下图插入一个键为6的节点，那么就先拿6和11做比拟，发现6<11，就向左移，再而后6和7做比拟，6<7那么持续向下，和5做比拟，6>5，那就让6插入到5的右节点
插入6的过程
封装代码
首先每个节点都须要left(左指针),right(右指针)和key(键)组成，所以咱们须要先实现一个Node类
class CreateNode { constructor(key) { this.key = key; this.left = null; this.right = null; }}insert封装
// 插入新节点insert(key) { let newNode = new CreateNode(key); //判断是否为空树 if (!this.root) { this.root = newNode } else { let parent = null; let current = this.root; // isLeftChild来判断是左侧还是右侧 let isLeftChild = false; while (current) { parent = current if (key < current.key) { current = current.left; isLeftChild = true } else { current = current.right; isLeftChild = false; } } isLeftChild ? parent.left = newNode : parent.right = newNode }}先序遍历（preOrderTraverse）
先序遍历是以优先于后辈节点的程序拜访每个节点的。先序遍历的一种利用是打印一个结构化的文档。
咱们来看实现.callBack是为了测试的一个函数，上面同理。
preOrderTraverse(callBack) { this.preOrderTraverseNode(this.root, callBack)}preOrderTraverseNode(node, callBack) { if (node) { callBack(node.key); this.preOrderTraverseNode(node.left, callBack); this.preOrderTraverseNode(node.right, callBack) }}下面代码是依据函数调用栈来实现的this.preOrderTraverseNode(node.left, callBack);走这段代码的时候将11.7.5.3相继压入栈中，当node==null的时候完结递归，栈中的函数顺次开释。因为曾经执行完了node.left，每次出栈的时候会执行上面的node.right，顺次类推就造成了上图的执行程序
中序遍历
中序遍历是一种以上行程序拜访 BST(BinarySearchTree)所有节点的遍历形式也就是以从最小到最大的程序拜访所有节点
中序遍历的一种利用就是对树进行排序操作。咱们来看看它的实现。
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) }}后序遍历
后序遍历则是先拜访节点的后辈节点再拜访节点自身。后序遍历的一种利用是计算一个目录及其子目录中所有文件所占空间的大小。
咱们来看看它的实现。
// 后序遍历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); }}想必明确了一种其余两种就会自然而然的明确了，要联合栈内存一起了解。
min(寻找最小值)
在一棵二叉树中最左侧就是最小值
min() { let current = this.root; while (current.left) { current = current.left } return current.key}max(寻找最大值)
在一棵二叉树中最右侧就是最小值
max() { let current = this.root; while (current.right) { current = current.right } return current.key}search(依据key值寻找)
依据key值寻找只有以后的key!=要寻找的key那么就持续向深一层的寻找，如果找不到间接返回false，找到了返回true
search(key) { let current = this.root; while (current && current.key != key) { if (key < current.key) { current = current.left } else if (key > current.key) { current = current.right } } return current ? true : false}删除(remove)
删除操作能够说是二叉树中最难的一个办法了;上面会一一列举删除须要顾及的场景；
第一步
删除的第一步是先寻找要删除的key
parent：是对应节点的父节点
isLeftChild：是为了辨别是左子树还是右子树
let current = this.root;let parent = null;let isLeftChild = false;while (current && current.key != key) { parent = current; if (key < current.key) { isLeftChild = true; current = current.left; } else if (key > current.key) { isLeftChild = false; current = current.right }}if (!current) return;第二步
判断要删除的节点是不是叶子节点，也就是没有左子树(left)和右子树(right);这种状况下间接让parent的左子树或者右子树置为null即可。例如删除的是下图中6这个节点，下面寻找到的current为6，parent为5.
if (!current.left && !current.right) { isLeftChild ? parent.left = null : parent.right = null;}第三步
如果有左子树没有右子树的状况下
1 删除{5}节点，{5}节点只有左子树，删除{5}这个节点间接让{7}的左指针指向{5}的左子树 parent.left = current.left
2 删除{5}节点，如图{5}节点只有右子树，删除{5}这个节点间接让{7}的左指针指向{5}的右子树 parent.left = current.right
3 删除{20}节点，如图{20}节点只有右子树，删除{20}这个节点间接让{15}的右指针指向{20}的右子树parent.right = current.right
4 删除{20}节点，如图{20}节点只有左子树，删除{20}这个节点间接让{15}的右指针指向{20}的左子树parent.right = current.left
下面的状况都曾经列举革除，因为咱们下面曾经定义了isLeftChild的变量，能够轻松晓得parent的指针方向，至于删除以后节点的左节点还是有节点这个须要咱们判断一下
if (current.left && !current.right) { isLeftChild ? parent.left = current.left : parent.right = current.left;} else if (current.right && !current.left) { isLeftChild ? parent.left = current.right : parent.right = current.left;}第四步
删除有两个子节点的树，这一步也是删除办法中场景最多的一步。
如下图删除{15}这个节点，那么咱们须要从它的子节点中的某一个提上去而又不会影响二叉树的规定，那么该提取哪一个呢。
这里有个词叫前驱后继，其中咱们抉择前驱也好抉择后继也能够。比方上面删除{15}节点他的前驱是14，那么把14提上去又变成了一棵合乎规定的二叉树。{15}的后继为18，用18代替15也是一棵合乎规定的树。参照下面咱们能够找到寻找前驱后继的规定：
前驱：删除某节点的左子树中最大的键
后继：删除某节点的右子树中最小的键
删除15须要做的逻辑
1.找到15的后继(前驱也能够，这里我抉择后继)18
2.将18提到15的地位，让18的左指针指向13，让18的右指针指向20
3.将20的左指针指向19
删除11须要做的逻辑
间接让根 = 后继
获取前驱的代码
getSuccessor(node) { let successParent = null; while (node.left) { successParent = node; node = node.left } if (successParent) { successParent.left = node.right; } return node}删除有两个子节点的代码
let successor = this.getSuccessor(current.right);if (current == this.root) { this.root = successor} else if (isLeftChild) { parent.left = successor} else { parent.right = successor;}successor.left = current.left;if (current.right != successor) { successor.right = current.right}残缺代码
class CreateNode { constructor(key) { this.key = key; this.left = null; this.right = null; }}class BinarySearchTree { constructor() { this.root = null; } // 插入新节点 insert(key) { let newNode = new CreateNode(key); if (!this.root) { this.root = newNode } else { let parent = null; let current = this.root; let isLeftChild = false; while (current) { parent = current if (key < current.key) { current = current.left; isLeftChild = true } else { current = current.right; isLeftChild = false; } } isLeftChild ? parent.left = newNode : parent.right = newNode } } // 先序遍历 preOrderTraverse(callBack) { this.preOrderTraverseNode(this.root, callBack) } preOrderTraverseNode(node, callBack) { if (node) { callBack(node.key); this.preOrderTraverseNode(node.left, callBack); this.preOrderTraverseNode(node.right, callBack) } } // 中序遍历 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) } } // 后序遍历 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); } } // 最大值 max() { let current = this.root; while (current.right) { current = current.right } return current.key } // 最小值 min() { let current = this.root; while (current.left) { current = current.left } return current.key } // 查问值 search(key) { let current = this.root; while (current && current.key != key) { if (key < current.key) { current = current.left } else if (key > current.key) { current = current.right } } return current ? true : false } // 删除 remove(key) { let current = this.root; let parent = null; let isLeftChild = false; while (current && current.key != key) { parent = current; if (key < current.key) { isLeftChild = true; current = current.left; } else if (key > current.key) { isLeftChild = false; current = current.right } } if (!current) return; if (!current.left && !current.right) { isLeftChild ? parent.left = null : parent.right = null; } else { if (current.left && !current.right) { isLeftChild ? parent.left = current.left : parent.right = current.left; } else if (current.right && !current.left) { isLeftChild ? parent.left = current.right : parent.right = current.left; } else { let successor = this.getSuccessor(current.right); if (current == this.root) { this.root = successor } else if (isLeftChild) { parent.left = successor } else { parent.right = successor; } successor.left = current.left; if (current.right != successor) { successor.right = current.right } } } } getSuccessor(node) { let successParent = null; while (node.left) { successParent = node; node = node.left } if (successParent) { successParent.left = node.right; } return node }}let bst = new BinarySearchTree();bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(10);bst.insert(8);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(19);// 测试先序遍历 let resString = ''; bst.preOrderTraverse(function (key) { resString += key + ' '; }) alert(resString)// 测试中序遍历 let resString = ''; bst.inOrderTraverse(function (key) { resString += key + ' '; }); alert(resString)// 测试后序遍历 let resString = ''; bst.postorderTraverse(function (key) { resString += key + ' '; }); alert(resString) //最大值 alert(bst.max()); //最小值 alert(bst.min());// 查问值alert(bst.search(18))// 删除bst.remove(11)