今天一整天系统学习了数据结构中的大头——二叉树（具体点，应该是二叉树的一种：二叉树搜索树（BST）。搜索二叉树最重要的特征：但是它只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值即左子节点的值 < 父节点的值 <= 右节点的值。基于这一点，实现了二叉树（以下均简称二叉树）的生成、三种遍历（中序遍历、前序遍历和后序遍历）、求最大值、求最小值、搜索和删除。
（一）.二叉树的生成。
主要就要抓住来一点，插入值的时候，都是从根结点开始比较，如果插入值<当前节点的值，即key<node.key，则取当前节点的left节点赋值给当前节点，即node=node.left；反之key>=node.key，则node=node.right。注意一点：传递类型的问题，可以参考我另一篇文章。代码如下：
//根据key生成节点
function Node(key) {
this.left=null;
this.key=key;
this.right=null;
}
//生成二叉树
function BinaryTree() {
this.root=null;
//插入节点
this.insert=function (key) {
let newNode=new Node(key);
if (this.root===null) { /*必须判断是否为空值，这边一共判断了3次，可以参考我另一篇文章，关于传递类型的问题。*/
this.root=newNode;
} else this.insertNode(this.root,newNode);
}
this.insertNode=function (preNode,newNode) {
let preKey=preNode.key,
newKey=newNode.key;
if (newKey<preKey) {
if (preNode.left===null) {
preNode.left=newNode;
} else this.insertNode(preNode.left,newNode);
} else {
if (preNode.right===null) {
preNode.right=newNode;
} else this.insertNode(preNode.right,newNode);
}
}
（二）二叉树的遍历
二叉树的遍历分为三种：中序遍历、前序遍历和后序遍历。实现方式为递归，既然说到递归，肯定存在调用栈过载的问题，这边后面准备出篇小节，自己总结一下。
（1）中序遍历。
遍历方式：left——>middle——>right。用途：将值按照升序输出。
function inOrderTraverseNode(node,callback) {
if (node!==null) {
inOrderTraverseNode(node.left,callback);
callback(node.key);
inOrderTraverseNode(node.right,callback);
}
}
（2）前序遍历。
遍历方式：middle——>left——>right。用途：复制一个二叉树。
function preOrderTraverseNode(node,callback) {
if (node!==null) {
callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);
}
}
（3）后序遍历。
遍历方式：left——>right——>middle。用途：文件系统的遍历。
function nextOrderTraverseNode(node,callback) {
if (node!==null) {
nextOrderTraverseNode(node.left,callback);
nextOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
（三）求最大最小值
根据二叉树的特征，最小值肯定在最左边，最大值在最右边，所以只需遍历到底，加个条件判断。
//查找最小值
function minNode(node) {
while (node && node.left!==null) {
node =node.left;
}
return node.key;
}
//查找最大值
function maxNode(node) {
if (node) {
while (node.right!==null) {
node =node.right;
}
return node.key;
}
}
（四）搜索指定值
根据二叉树的特征，一直搜到树底。
function findNode(node,key) {
if (node && key<node.key) {
return findNode(node.left,key);
} else if (node && key>node.key) {
return findNode(node.right,key)
} else if (node && key===node.key) {
return true;
} else return false;
}
（五）删除任意节点
欲删除的节点可以分为三类：第一类、叶子节点；第二类、只有left或right子节点的节点；第三类、既有left又有right子结点的节点。
（1）第一类、叶子节点
对于这类节点，处理方法很简单，遍历找到待删除的节点，直接把该结点变成空值，node=null，再返回该结点。上代码：
function removeNode(node,key) {
if (node===null) {
return null;
} else if (key<node.key) {
node.left=removeNode(node.left,key); //递归，每次接受下一个节点
return node;
} else if (key>node.key) {
node.right=removeNode(node.right,key);
return node;
} else { //递归停止的点
if (node.left===null && node.right===null) { //处理第一类节点
node=null;
return node;
}
（2）第二类、只有left或right子节点的节点
对于这类节点，只需要把该节点的node直接换成node.left或者node.right，再返回node。
function removeNode(node,key) {
if (node===null) {
return null;
} else if (key<node.key) {
node.left=removeNode(node.left,key);
return node;
} else if (key>node.key) {
node.right=removeNode(node.right,key);
return node;
} else {
if (node.left===null && node.right===null) {
node=null;
return node;
} else if (node.left===null) {
node=node.right;
return node;
} else if (node.right===null) { //对于第二类节点的处理
node=node.left;
return node;
}
（3）第三类、即有left又有right子节点的节点
关键点在于：删除后的二叉树也要满足特征。
方法：把待删除的node，换成node.right子树最小的值，或node.left子树最大的值，最后删除最小或最大值node。
else {
let minRnode=minR(node.right);
node.key=minRnode.key;
node.right=removeNode(node.right,minRnode.key); //在上段代码最后添加即可
return node;
}
参考：https://www.imooc.com/video/15752 视频讲解。
