JavaScript二叉树深入理解

——记录下来以便将来看看现在的自己

看到掘金上@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);

二叉树的缺点：如果节点要频繁删除的话，不适合使用二叉树，特别是被删除的节点有两个子节点的；
  二叉树的优点：查找无规律的数字或者字母的数据结构适合二叉树的使用场景！

数据结构路路漫漫，吾将上下其手，老妹惊叫连连。有什么问题可以在评论区留言哦，共同进步+_+