记得一开始学习数据结构用的是c语言实现，学了这么久前端就想用JavaScript来实现一下，顺便复习下数据结构。
先来了解下什么是排序二叉树，排序二叉树是具有以下特点的二叉树
-
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值，
-
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值，
- 左、右子树也分别为二叉排序树
比如下面这图，左边的值永远小于右边的值
下面我们用代码实现一波
首先是树的结构和根节点
var Node = function(key){//节点结构 this.left = null this.right = null this.key = key }
var root = null //根节点
二叉树的插入，基本过程是比较要插入的数和当前节点的值大小，按照排序二叉树的特点，左边的值永远小于右边
var insertNode = function(node,newNode){ if(node.key > newNode.key){//要插入的值小于当前节点，左子树遍历 if(node.left === null){ node.left = newNode return }else{ insertNode(node.left,newNode) } }else if(node.key <= newNode.key){//要插入的值小于当前节点，右子树遍历 if(node.right === null){ node.right = newNode }else{ insertNode(node.right,newNode) } } }
插入成功后我们分别来实现排序二叉树的前序，中序和后序遍历
前序遍历是先访问根节点，而后是左右节点
中序遍历先访问左节点，而后是根节点和右节点
后序遍历则先访问左右节点，最后是根节点
代码如下
var inOrderTraverseNode = function(node,callback){//中序遍历 if(node !== null){ inOrderTraverseNode(node.left) console.log(node.key) inOrderTraverseNode(node.right) } }
var preOrderTraverseNode = function(node,callback){//前序遍历 if(node !== null){ console.log(node.key) preOrderTraverseNode(node.left) preOrderTraverseNode(node.right) } }
var afterOrderTraversNode = function(node,callback){//后序遍历 if(node !== null){ afterOrderTraversNode(node.left) afterOrderTraversNode(node.right) console.log(node.key) } }
寻找二叉树的最大值和最小值，这一部分根据
排序二叉树的特点很快就能知道，最大值在最右边的叶子节点，最小值处于最左边的叶子节点var Max = function(node){//最大值 if(node.right !== null){ maxNum = Max(node.right) }else{ return node.key } return maxNum }
var Min = function(node){//最小值 if(node.left !== null){ minNum = Min(node.left) }else{ return node.key } return minNum }
寻找排序二叉树中的指定值，也很简单，以根节点为界，比左边小到左边找，比右边小去右边
var Search = function(node,key){//寻找指定值 if(node.key === key){ return true }else{ if(key < node.key && node.left !=null){ return Search(node.left,key) }else if(key > node.key && node.left !=null){ return Search(node.right,key) }else{ return false } } }
最麻烦的是删除节点的操作，这里需要分三种情况，删除节点无子树，删除节点为单子树，删除节点有两个子树，
无子树最简单，直接删
if(node.left === null && node.right === null){ node = null return node }
有单子树的：比如下图（画的有点丑。。。），现在我要删掉3，
代码实现如下
else if(node.left !== null && node.right === null){ node = node.left return node }else if(node.left === null && node.right !== null){ node = node.right return node }
最后是删除有两个子树的节点，为了维持我们排序二叉树的性质，首先我们找到要删除节点的右字树的最小值，根据排序二叉树的特点，找到的最小值必定大于要删除节点的左子树的所有值，因为找到的值为右节点的最小值，所以小于要删除节点的右子树的所有值，我们将找到的最小值代替要删除的值，最后删掉一开始找到的最小值的节点，基本过程就相当于替换了要删除节点的值。
下图，我要删掉3
。
按照上面的思想，找到4代替3，然后删掉一开始找到的4所在的节点
依旧满足排序二叉树的特点
else if(node.left !== null && node.right !== null){ var minNode = finMinNode(node.right) node.key = minNode.key node.right = Remove(node.right,minNode.key) return node }
到这里排序二叉树的基本功能都实现了
完整代码在GitHub（求GitHub小星星）上，我把双向链表也用JavaScript实现了下，需要的也可以看看
原文发布时间为：2018年06月23日
原文作者：笑佛弥勒
本文来源： 掘金 如需转载请联系原作者
