Arbre_006-1000x783.jpg
前端以及后端开发过程中，其实大部分时间我们通过抽象将实际业务抽象为数据模型进行运算。所以感觉自己应该花一些时间和精力，这样从而提高自己搬砖的技巧和效率。
屏幕快照 2019-04-23 下午8.32.02.png
嗨！自从学了点数据结构，搬砖背也不痛了，腰也不酸了。
树这样数据是让人头痛的数据结构，树数据结构在前端常见的就是对组织架构的抽象。
树的相关术语
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个节点
- 根节点
- 子树
- 节点深度
二叉树和二叉搜索树
二叉树中的节点最多只能有两个节点：左节点和右节点。
二叉搜索树是二叉树的一种，特点是只允许在左侧节点放置(比父节点）小的值，在右节点放置（比父节点）大（或者等于）的值。
什么是二叉树以及他有哪些特点
创建树数据结构
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);
}
}
- 首先创建一个 Node 对象，给他初始值 left 和 right 都为空
- 判断 root 是否为空，如果为空则该新建 node 做为 root 否则调用内部方法来添加节点
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);
}
}
}
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(9);
tree.insert(15);
tree.insert(6);
tree.insert(9);
tree.insert(11);
tree.insert(21);
树的遍历
根据遍历时访问节点本身、右侧和左侧节点顺序不同而分类为中序遍历、先序遍历和后序遍历。
中序遍历
什么是中序遍历呢？就是一种从上行顺序地访问 BST 所有节点的遍历方式，也就是从小到大输出所有节点。
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.inOrderTraverse = function(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)
}
var minNode = function(node){
if(node){
while(node && node.left !== null){
node = node.left
}
return node.key
}
return null;
}
Learn-Javascript.jpg
