Javascript二叉搜索树实现

基本知识

二叉树：二叉树的所有结点的最大度数为2； 二叉搜索树：又称为二叉排序树，根节点与其左右子结点的满足以下关系：左子结点<根结点<右子结点； 完全二叉树：除最后一层外，其它各层达到该层最大结点数；结点为n的完全二叉树深度为log2(n+1)； 第i层的最大结点数：2^(i-1); 深度为h的最大最大总节点数：2^h-1;

function BinarySearchTree() { /** * 二叉搜索树的初始化 */ var root = null; var Node = function (value) { this.value = value; this.left = null; this.right = null; } // var Node = (value) => { // this.value = value; // this.left = null; // this.right = null; // } /** * 插入键值到binarySearchTree */ this.insert = function (value) { var newNode = new Node(value); if (root === null) { root = newNode; } else { insertNode(root, newNode); } } /** * 插入子结点 * @param {Node} node * @param {Node} newNode */ var insertNode = function (node, newNode) { if (node.value > newNode.value) { if (node.left === null) { node.left = newNode; } else { insertNode(node.left, newNode); } } else { if (node.right === null) { node.right = newNode; } else { insertNode(node.right, newNode); } } } /** * 移除结点 */ this.remove = function (value) { root = removeNode(root, value); } /** * 递归寻找并移除结点 * @param {Node} node * @param {Node.value} value 需要移除的结点的值 */ var removeNode = function (node, value) { if (node === null) { return null; } if (value < node.value) { node.left = removeNode(node.left, value); } else if (value > node.value) { node.right = removeNode(node.right, value); } else { //该结点为叶子结点 if (node.left === null && node.rigth === null) { node = null; } //该结点有一个子结点 else if (node.left === null) { node = node.right; // node.right = null; } else if (node.right === null) { node = node.left; // node.left = null; } //该结点有两个子结点，此时可以取左子树中的最大值代替根结点；当然也可以取右子树中的最小值代替根结点 else if (node.left != null && node.right != null) { var temp = minRightNode(node.right); node.value = temp.value; node.right = removeNode(node.right, temp.value); } } return node; } var minRightNode = function (node) { if (node) { while (node && node.left != null) { node = node.left; } return node; } return null; } /** * 先序遍历binarySearchTree * @param {Function} callback */ this.preOrderTraverse = function (callback) { console.log("先序遍历："); preOrderTraverseNode(root, callback); } /** * 递归实现先序遍历 * @param {Node} node * @param {Fucntion} callback */ var preOrderTraverseNode = function (node, callback) { if (node != null) { callback(node); preOrderTraverseNode(node.left, callback); preOrderTraverseNode(node.right, callback); } } /** * 非递归先序遍历 */ this.preOrderTraverse2 = function (callback) { console.log('非递归先序遍历：'); if (root) { let stack = []; stack.push(root); while (stack.length > 0) { pivot = stack.pop(); console.log('pre: ', pivot.value); if (pivot.right) { stack.push(pivot.right); } if (pivot.left) { stack.push(pivot.left); } } } } /** * 中序遍历binarySearchTree * @param {Function} callback */ this.inOrderTraverse = function (callback) { console.log("中序遍历："); inOrderTraverseNode(root, callback); } /** * 递归实现中序遍历 * @param {Node} node * @param {Function} callback */ var inOrderTraverseNode = function (node, callback) { if (node != null) { inOrderTraverseNode(node.left, callback); callback(node); inOrderTraverseNode(node.right, callback); } } /** * 非递归中序遍历 * / this.inOrderTraverse2 = function (callback) { console.log('非递归中序遍历：'); if (root) { let stack = []; while (stack.length > 0 || root) { if (root) { stack.push(root); root = root.left; } else { root = stack.pop(); callback(root) root = root.right; } } } } /** * 后序遍历binarySearchTree * @param {Fucntion} callback */ this.postOrderTraverse = function (callback) { console.log("后序遍历："); postOrderTraverseNode(root, callback); } /** * 递归后续遍历 * @param {Node} node * @param {Function} callback */ var postOrderTraverseNode = function (node, callback) { if (node != null) { postOrderTraverseNode(node.left, callback); postOrderTraverseNode(node.right, callback); callback(node); } } /** * 非递归后序遍历 * / this.postOrderTraverse2 = function (callback) { console.log('非递归后序遍历：'); if (root) { let stack1 = []; let stack2 = []; stack1.push(root); while (stack1.length > 0) { pivot = stack1.pop(); stack2.push(pivot); if (pivot.left) { stack1.push(pivot.left); } if (pivot.right) { stack1.push(pivot.right); } } while (stack2.length > 0) { callback(stack2.pop()) } } } /** * 广度优先遍历 */ this.breadthTraverse = function (callback) { console.log('广度优先遍历：'); breadthTraverseNode(root, callback); } var breadthTraverseNode = function (node, callback) { let stack = []; if (node) { stack.push(node); } while(stack.length > 0) { let cur = stack.shift(); callback(cur); if (cur.left) stack.push(cur.left); if (cur.right) stack.push(cur.right); } } /** * 搜索结点 */ var isFind = false; this.search = function (value) { isFind = false; console.log(`搜索结点${value}`); searchNode(root, value); return isFind; }; /** * 递归搜索结点 * @param {Node} node * @param {Node.value} value */ var searchNode = function (node, value) { if (node != null) { if (isFind) return; if (node.value > value) { searchNode(node.left, value); } else if (node.value < value) { searchNode(node.right, value); } else { isFind = true; } } else { isFind = false; } }; /** * 搜索binarySearchTree中的最小值 */ this.min = () => { console.log("搜索最小值"); return minNode(root); } var minNode = (node) => { if (node) { while (node && node.left != null) { node = node.left; } return node.value; } return null; } /** * 搜索binarySearchTree中最大值 */ this.max = function () { console.log("搜索最大值"); return maxNode(root); } var maxNode = (node) => { if (node != null) { while (node && node.right) { node = node.right; } return node.value; } return null; } /** * 查询树的深度 */ this.depth = function () { return maxDepth(root); } var maxDepth = function (node) { if (!node) return 0; return max(maxDepth(node.left), maxDepth(node.right)) + 1; } } /** * 打印结点值 * @param {Node} node */ var printNode = function (node) { console.log(node.value); } var tree = new BinarySearchTree(); tree.insert(7) tree.insert(4) tree.insert(1) tree.insert(3) tree.insert(11) tree.insert(6) tree.insert(8) tree.insert(9) tree.insert(13) tree.preOrderTraverse(printNode); tree.inOrderTraverse(printNode); tree.postOrderTraverse(printNode); tree.breadthTraverse(printNode); console.log(tree.min()); console.log(tree.max()); console.log("================"); console.log(tree.search(11)); tree.remove(11); tree.preOrderTraverse(printNode); tree.inOrderTraverse(printNode); tree.postOrderTraverse(printNode); console.log(tree.min()); console.log(tree.max()); console.log("================"); console.log(tree.search(11));

结果：

先序遍历： 7 4 1 3 6 11 8 9 13 中序遍历： 1 3 4 6 7 8 9 11 13 后序遍历： 3 1 6 4 9 8 13 11 7 广度优先遍历： 7 4 11 1 6 8 13 3 9 搜索最小值 1 搜索最大值 13 ================ 搜索节点11 true 4 1 3 6 13 8 9 中序遍历： 1 3 4 6 7 8 9 13 后序遍历： 3 1 6 4 9 8 13 7 搜索最小值 1 搜索最大值 13 ================ 搜索节点11 false