algorithm
应用本身就是算法和数据结构和集合，做一段时间应用开发，最近有时间总结一些有关数据结构和算法的知识，希望提供自己开发速度。
数据结构一般提供需要提供可查询，可扩展，可修改，可遍历。根据其对这些行为不同实现而又分为栈、队列、散列表。大家往往认为数据结构是偏重于数据，其实不然数据结构更多偏重于行为，是如何组织数据的的行为。我觉这段话说的很精彩。
我们可以从很多维度区划分数据
这里我们先从数据是线性还是非线性来划分数据结构为
- 线性：数组、栈、队列、链表、散列表和集合
- 非线性: 图、树
tree
树
什么是树，数据结构中的树和大自然中的树有点形似。人类喜欢通过定义方式是，用语言描述来说明一个事物的结构，说明的内容一般都是强调该事物自身的一些其特点，这些特点用来区分于您所了解的类似容易和其混淆的事物。
那么什么是树呢？
包含一系列存在父子关系的节点。这句话有点书面，不过细细品味还是怎么一回事，那么树的基本单位节点，根据其关系又分三类节点
- 根节点 : 没有父节点
- 内部节点 : 至少有一个子节点
- 外部节点(叶节点）: 没有子节点
二叉搜索树(BST)
所谓二叉就是只允许每个节点最多只能有两个子节点，而且左侧节点存储值比父节点小的值，右侧节点存储比父节点大的值。
定义二叉搜索树
function BinarySearchTree(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
}
向树中插入一个节点
this.insert = function(key){
var newNode = new Node(key);
if(root === null){
root = newNode;
}else{
insertNode(root,newNode);
}
}
我们根据树情况进行不同行为，也就是状态决定行为，树根据是否存在根节点可以划分为两种状态
- 有根节点 : 调用 insertNode 方法
- 没有根节点 : 将插入的节点作为根节点
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);
}
}
}
如何插入到一个节点下呢？
- 插入到哪个节点下面?
- 插入到该节点的左侧还是右侧呢?
这些问题答案都可以在树的定义中找到答案。对比节点值和要插入到其下节点值比较来决定是放在节点左侧还是右侧，如果该位置已经被节点占据，递归方式再次调用 insertNode 来解决。
树的遍历
什么是遍历，为什么要遍历。遍历就是访问到数据结构的每一个元素，来对每个元素进行操作。遍历顺序是从顶端还是到底端，从左开始还是从右开始，遍历分为三种方式：中序、先序和后序。
中序遍历
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)
}
}
先序遍历
this.preOrderTraverse = function(callback){
preOrderTraverseNode(root,callback)
}
var preOrderTraverseNode = function(node, callback){
if(node !== null){
callback(node.key)
preOrderTraverseNode(node.left,callback)
preOrderTraverseNode(node.right,callback)
}
}
后序遍历
this.postOrderTraverse = function(node,callback){
postOrderTraverseNode(root,callback)
}
var postOrderTraverseNode = function(node,callback){
if(node !== null){
preOrderTraverseNode(node.left,callback)
preOrderTraverseNode(node.right,callback)
callback(node.key)
}
}
最大值和最小值
/**
* 搜索最小值
*/
this.min = function(){
return minNode(root)
}
/**
*
* @param {*} node
*/
var minNode = function(node){
if(node){
while(node && node.left !== null){
node = node.left
}
return node.key
}
return null;
}
this.max = function(){
return maxNode(root)
}
var maxNode = function(node){
if(node){
while(node && node.right !== null){
node = node.right
}
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;
}
}
/**
* 根据值移除节点
* @param {any} key
*/
this.remove = function(key){
root = removeNode(root, key);
}
/**
*
* @param {any} node
* @param {any} key
*/
var removeNode = function(node, key){
if(node === null){//如果 node 为空说明节点不存在
return null;
}
//通过要删除的节点的值和当前节点的值进行对比，来确定向左侧还是右侧
//删除节点
if(key < node.key){
node.left = removeNode(node.left,key);
return node;
}else{
if(node.left === null && node.right === null){
node = null;
return node;
}
if(node.left === null){
node = node.right;
return node;
}else if(node.right === null){
node = node.left;
return node;
}
var temp = findMinNode(node.right);
node.key = temp.key;
node.right = removeNode(node.right,temp.key);
return node;
}
var findMinNode = function(node){
while(node && node.left !== null){
node = node.left;
}
return node;
}
}
第一种情况
- 要删除的第一种情况就是没有子节点的节点，那么现在节点值已经是 null，父节点指向他的指针也会接收这个值，这是为什么我们要在函数中返回节点值的原因。
第二种情况
- 要移除节点只有一个子节点，可能是左侧还是右侧，很好理解该节点被移除了，其下面的子节点就会上位，具体怎么上位也就是 node = node.right 或者 node.left。
第三种情况
-
要移除的节点有左侧还有右侧节点的情况，这种情况最为复杂
1 找到需要移除的节点后，还需要找到其右侧树中最小值的节点
2 用其右侧树中最小节点的值去更新这个节点的值。
3 如果树中有两个拥有相同值的节点，需要把右侧子树中的最小节点移除
4 最后向其父节点返回更新后节点的引用
developer
