/**
* 树，一种非线性的数据结构。 以分层的方式存储数据。
* 一棵树最上面的节点成为根节点，如果一个节点下面有多个节点，这个节点称为父节点，下面的节点称为子节点
* 没有任何子节点的节点，陈宝国职位叶子节点。
*
* 二叉树是每个节点最多有两个子树的有序树
* 从一个节点到另外一个节点称为路径
* 树有层的概念，根节点是 0层，那它的子节点是第一层，以此类推。
* 因为二叉树中，子节点只有两个，那么数据的查找，删除，插入实现起来就速度很快（因为非节点一就是节点二~
*
* 二叉查找树 是一个特殊的二叉树，相对较小的值保存在左边子节点，较大值保存在右边子节点。
*
* 示例：
* （ 56 ）
* /
* (22) (81)
* / /
* (10) (30) (77) (92)
*
*/
code
/**
* 节点类
* @param data
* @param left
* @param right
* @constructor
*/
function Node(data,left,right){
this.data = data;
this.right = right;
this.left = left;
this.show = show;
function show(){
return this.data;
}
}
//二叉查找树
//保存值原理：相对较小的值保存在左边子节点，较大值保存在右边子节点。
//遍历： 有三种方式：中序，先序，后序。
// 中序， 中序遍历按照节点上的键值，以升序访问BST上的所有节点。
// 先序， 先序遍历先访问根节点，然后以同样方式访问左子树和右子树。
// 后序， 后序遍历先访问叶子节点，从左子树到右子树，再到根节点。
//
/**
* 二叉查找树
* @constructor
*/
function BST(){
var me = this;
me.root = null;
me.inOrder = inOrder;
me.preOrder = preOrder;
me.postOrder = postOrder;
me.insert = insert;
me.getMin = getMin;
me.getMax = getMax;
me.find = find;
me.remove = remove;
/**
* 插入 新数据。
* @param data
*/
function insert(data){
var newNode = new Node(data,null,null)
if(me.root == null){
me.root =newNode;
}else{
var cur = me.root,
parent;
while(true){
parent = cur;
//数据小于节点 ==》left
if(data<cur.data){
cur = cur.left;
//如果节点 null 说明该节点下为空。可以插入新数据
if(cur == null){
parent.left = newNode;
break;
}
} else{
//数据大于节点 ==》right
cur = cur.right;
//如果节点 null 说明5节点下为空。可以插入新数据
if(cur==null){
parent.right = newNode;
break;
}
}
}
}
}
/**
* 中序
* @param node
*/
function inOrder(node,fn){
if(!(node==null)){
me.inOrder(node.left)
//中序实现的演示 在这里 将node展示出来
console.log(node.show()+" ");
fn&&fn(node.show())
me.inOrder(node.right)
}
}
/**
* 先序
* @param node
* @param fn
*/
function preOrder(node,fn){
if(!(node==null)){
//先序实现的演示，在这里 将node展现出来
console.log(node.show()+" ");
fn&&fn(node)
me.preOrder(node.left)
me.preOrder(node.right)
}
}
/**
* 后序
* @param node
* @param fn
*/
function postOrder(node,fn){
if(!(node==null)) {
me.postOrder(node.left);
me.postOrder(node.right);
//后序实现的演示，在这里，将node展现
console.log(node.show()+" ");
fn&&fn(node.show())
}
}
/**
* 返回最小节点
* @returns {null|*}
*/
function getMin(){
var cur = me.root;
while(!(cur.left==null)){
cur = cur.left;
}
return cur;
}
/**
* 返回最大节点
* @returns {null|*}
*/
function getMax(){
var cur = me.root;
while(!(cur.right==null)){
cur = cur.right;
}
return cur;
}
/**
* 查找该节点
* @param v
* @returns {*}
*/
function find(v){
var cur = me.root;
while(cur!=null){
if(cur.data == v){
return cur;
}else if(cur.data>v){
cur = cur.left;
}else{
cur = cur.right;
}
}
return null;
}
function remove(data){
me.root = removeNode(me.root,data)
}
function removeNode(node,data){
if(node ==null)return null;
if(data == node.data){
//as
if(node.left==null&&node.right==null){
return null;
}
if(node.left==null){
return node.right;
}
if(node.right==null){
return node.left;
}
//当该节点是需要删除的值时（并且该节点下面有子节点）
//那么需要将该节点right上升到该位置 或者 right节点的left节点。
//因为 左边永远小于父节点，右边大于父节点。
var tmp = getSmallest(node.right);
node.data = tmp.data;
node.right = removeNode(node.right,tmp.data)
return node;
}else if(data<node.data){
//left
node.left = removeNode(node.left,data)
return node;
}else{
//right
node.right = removeNode(node.right,data)
return node;
}
}
function getSmallest(node){
if (node.left == null) {
return node;
}
else {
return getSmallest(node.left);
}
}
}
