——记录下来以便将来看看现在的自己
看到掘金上@MaevynZhang有篇博文讲关于JS二叉树的，写得有点骨干，处女座表示看不下去了！ 我来自遥远的燕国，为了天下黎民，以正视听。
上面那位作者他直接把一个二叉树的结构数据生成一个二叉树实例
QQ图片20161208144159.jpg
这数据定的太绝了吧+_+这要要前端搬板凳吃瓜的节奏啊。吐槽截止，开始讲二叉树！
二叉树的一个节点Node由data，left，right组成，data保存本节点的值，left指向左节点，right指向右节点。二叉树有一个<b>特殊性:相对本节点较小的值保存在左节点，相对本节点较大的值保存在右节点</b>，该特性能让查值效率提高！
创建Node实例
/*
* parameter: data:本节点的数据；left：做节点；right：右节点
*/
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function BST(){
this.root = null;
this.insert = insert;
}
/*
* parameter: data:本节点的数据；
* 创建节点示例并插入到二叉树的正确位置
*/
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function BST(){
this.root = null;
this.insert = insert;
}
function insert(data){
var node = new Node(data,null,null);
if(this.root == null){
this.root = node;
}else{
var current = this.root;
while(true){
if(current.data > data){
if(current.left === null){
current.left = node;
break;
}
current = current.left;
}else{
if(current.right === null){
current.right = node;
break;
}
current = current.right;
}
}
}
}
var bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
看代码应该能看出Node是怎么插入二叉树的，下图是代码打印出来的树状结构
Paste_Image.png
创建二叉树代码完成，现在你可能高潮了，原来创建二叉树这么简单啊，那它有什么优点或者缺点呢？二叉树的优点是查找值最快，最小值和最大值分别位于两端，查找指定值如下：
function find(data){
var current = this.root;
while(true){
if(data === current.data){
return current;
}
current = data < current.data ? current.left : current.right;
if(current === null){
return null;
}
}
}
这种查找值类似二分法，比列表查值快了很多，数据量越多，二叉树比列表查值的速度就越快！ （如果只是比查值效率，二分法肯定比二叉树快，但是应用场景不同，二分法适用在如1~100依次递增顺序列表中；二叉树可以应用在任何数字或者字符组成的数据结构中）。
删除节点中心思想：如果删除节点是叶子节点，则将父节点指向null；如果删除节点有一个子节点，则将父节点指向删除节点的子节点；如果删除节点有两个子节点，这个本文不写，因为这个有点不合适（脑补）！
function remove(data){
this.root = removeNode(this.root,data);
}
function removeNode(node,data){
if(node === null){
return null;
}
if(data === node.data){
if(node.left === null && node.right === null){
return null;
}
if(node.left === null){
return node.right;
}
if(node.right === null){
return node.left;
}
}else if(data < node.data){
node.left = removeNode(node.left,data);
return node;
}else{
node.right = removeNode(node.right,data);
return node;
}
}
删除节点的代码我摘抄自《数据结构与算法JavaScript描述》，写得确实惊艳，感叹代码魅力。
最后整合代码:
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function BST(){
this.root = null;
this.insert = insert;
this.find = find;
this.remove = remove;
}
/*
* 二叉树增加节点
*/
function insert(data){
var node = new Node(data,null,null);
if(this.root == null){
this.root = node;
}else{
var current = this.root;
while(true){
if(current.data > data){
if(current.left === null){
current.left = node;
break;
}
current = current.left;
}else{
if(current.right === null){
current.right = node;
break;
}
current = current.right;
}
}
}
}
/*
* 二叉树查节点
*/
function find(data){
var current = this.root;
while(true){
if(data === current.data){
return current;
}
current = data < current.data ? current.left : current.right;
if(current === null){
return null;
}
}
}
/*
* 二叉树删除节点 (只删除叶子节点、只有一个子节点的Node
*/
function remove(data){
this.root = removeNode(this.root,data);
}
function removeNode(node,data){
if(node === null){
return null;
}
if(data === node.data){
if(node.left === null && node.right === null){
return null;
}
if(node.left === null){
return node.right;
}
if(node.right === null){
return node.left;
}
}else if(data < node.data){
node.left = removeNode(node.left,data);
return node;
}else{
node.right = removeNode(node.right,data);
return node;
}
}
var bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.remove(2);
二叉树的缺点：如果节点要频繁删除的话，不适合使用二叉树，特别是被删除的节点有两个子节点的；
二叉树的优点：查找无规律的数字或者字母的数据结构适合二叉树的使用场景！
数据结构路路漫漫，吾将上下其手，老妹惊叫连连。有什么问题可以在评论区留言哦，共同进步+_+
网友评论