/*** 树，一种非线性的数据结构。 以分层的方式存储数据。* 一棵树最上面的节点成为根节点，如果一个节点下面有多个节点，这个节点称为父节点，下面的节点称为子节点* 没有任何子节点的节点，陈宝国职位叶子节点。** 二叉树是每个节点最多有两个子树的有序树* 从一个节点到另外一个节点称为路径* 树有层的概念，根节点是 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;//数据小于节点 ==》leftif(data<cur.data){cur = cur.left;//如果节点 null 说明该节点下为空。可以插入新数据if(cur == null){parent.left = newNode;break;}} else{//数据大于节点 ==》rightcur = 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){//asif(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){//leftnode.left = removeNode(node.left,data)return node;}else{//rightnode.right = removeNode(node.right,data)return node;}}function getSmallest(node){if (node.left == null) {return node;}else {return getSmallest(node.left);}}}
