前面介绍过一种非顺序数据结构是散列表，本文将详细介绍另一种非顺序数据结构——树，它对于存储需要快速查找的数据非常有用
二叉树、满二叉树、完全二叉树、堆、二叉搜索树BST/二叉查找树/二叉排序树
二叉搜索树是我们这章要研究的数据结构
1.树-创建BinarySearchTree类
function BinarySearchTree() { var Node = function(key){ //{1} 节点包括键、左侧子节点、右侧子节点 this.key = key; //键 this.left = null; //左侧子节点 this.right = null; //右侧子节点 }; var root = null; //{2} //根元素 }然后，我们需要实现一些方法。下面是将要在树类中实现的方法： insert(key)：向树中插入一个新的键。 search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回 false。 inOrderTraverse：通过中序遍历方式遍历所有节点。 preOrderTraverse：通过先序遍历方式遍历所有节点。 postOrderTraverse：通过后序遍历方式遍历所有节点。 min：返回树中最小的值/键。 max：返回树中最大的值/键。 remove(key)：从树中移除某个键。
2.insert
//插入insert this.insert = function(key){ var newNode = new Node(key); if(root === null){ root = newNode; }else{ insertNode(root,newNode); } } var insertNode = function(node,newNode){ 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); } } }3.树的遍历
//var tree = new BinarySearchTree(); //中序遍历 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); } } //回调函数callback function printNode(value){ console.log(value); } //tree调用中序遍历 tree.inOrderTraverse(printNode);4.树的搜索
//树的搜索(最小值、最大值、特定值) 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.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{ return true; } }5.树的移除
//移除一个节点 this.remove = function(key){ root = removeNode(root,key); } var removeNode = function(node,key){ if(node === null){ return null; } 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{ //键等于node.key //第一种情况——一个叶节点 if (node.left === null && node.right === null){ //{9} node = null; //{10} return node; //{11} } //第二种情况——一个只有一个子节点的节点 if (node.left === null){ //{12} node = node.right; //{13} return node; //{14} } else if (node.right === null){ //{15} node = node.left; //{16} return node; //{17} } //第三种情况——一个有两个子节点的节点 var aux = findMinNode(node.right); //{18} node.key = aux.key; //{19} node.right = removeNode(node.right, aux.key); //{20} return node; //{21} } }更多可以参考：https://www.cnblogs.com/xiaohuochai/p/8184989.html#anchor4
附注一张图： 在这里插入图片描述
