js树形结构-----二叉树增删查

function BinarySearchTree(){var cnodes = function(key){this.key = key;this.left = null;this.right = null;}var root = null;this.insert = function(key){var nodes = new cnodes(key);if(root === null){root = nodes;}else{insertNode(root,nodes);}}function insertNode(rnode,newnode){if(newnode.key ?< ?rnode.key){if(rnode.left ?=== null){rnode.left = newnode;}else{insertNode(rnode.left,newnode);}}else{if(rnode.right === null){rnode.right = newnode;}else{insertNode(rnode.right , newnode );}}}//中序遍历this.inOrderTraverse = function(callback){inOrderTraverseNode(root, callback);};function inOrderTraverseNode(cnode,callback){if(cnode !== null){inOrderTraverseNode(cnode.left,callback );callback(cnode.key);inOrderTraverseNode(cnode.right,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(callback){postOrderTraverseNode(root, callback);};function postOrderTraverseNode(cnode, callback){if(cnode !== null){postOrderTraverseNode(cnode.left, callback);postOrderTraverseNode(cnode.right, callback);callback(cnode.key);}}//搜索最小值this.min = function(){return minNode(root);};function minNode(cnode){if(cnode){while(cnode && cnode.left !== null){cnode = cnode.left;}return cnode.key;}return null;}this.max = function(){return maxNode(root);}function maxNode(cnode){if(cnode){while(cnode && cnode.right !== null){cnode = cnode.right;}return cnode.key;}return null;}this.search = function(key){return searchNode(root,key);};function searchNode(cnode,key){if(cnode === null){return false;}if(key < cnode.key){return searchNode(cnode.left,key);}else if(key > cnode.key){return searchNode(cnode.right,key);}else{return true;}}//删除this.remove = function(key){root = removeNode(root,key);};function removeNode(cnode,key){if(cnode == null){return null;}if(key < cnode.key){cnode.left = removeNode(cnode.left , key);return cnode;}else if(key ?> cnode.key){cnode.right = removeNode(cnode.right , key);return cnode;}else{//等于的时候//第一种情况，一个叶节点if(cnode.left === null && cnode.right === null){cnode = null;return cnode;}//第二种情况，一个子节点if(cnode.left === null){cnode = cnode.right;return cnode;}else if(cnode.right === null){cnode = cnode.left;return cnode;}//第三种情况,两个子节点//1找到要删除的节点//2找到该节点，右侧子树中的最小节点，替换自己//3删掉右侧子树中的最小节点var aux = findMinNode(cnode.right);cnode.key = aux.key;cnode.right = removeNode(cnode.right,aux.key);return cnode;}}var findMinNode = function(node){//右侧子树中最小节点的键去更新这个节点的值while (node && node.left !== null) {node = node.left;}return node;};}var tree ?= new BinarySearchTree();tree.insert(11);tree.insert(7);tree.insert(15);tree.insert(5);tree.insert(3);tree.insert(9);tree.insert(8);tree.insert(10);tree.insert(13);tree.insert(12);tree.insert(14);tree.insert(20);tree.insert(18);tree.insert(25);tree.insert(6);tree.inOrderTraverse(function(key){console.log(key);});tree.remove(15);console.log("-----------");tree.inOrderTraverse(function(key){console.log(key);});