javascript二叉树基本功能实现

都是常用的功能。

删除是最复杂的。。

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>test</title> <script src="js/lib/angular.min.js"></script> <script > function BinarySearchTree(){ var Node = function(key){ this.key = key; this.left = null; this.right = null; }; var root = null; this.insert = function(key){ var newNode = new Node(key); if (root === null) { root = newNode; } else { insertNode(root, newNode); } }; var insertNode = function(node, newNode) { if (newNode.key < node.key) { 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.inOrderTraverse = function(callback) { inOrderTraverseNode(root, callback); }; var inOrderTraverseNode = function(node, callback) { if (node !== null) { inOrderTraverseNode(node.left, callback); callback(node.key); inOrderTraverseNode(node.right, callback); } }; this.preOrderTraverse = function(callback){ preOrderTraverseNode(root, callback); }; var preOrderTraverseNode = function (node, callback) { if (node !== null) { callback(node.key); //{1} preOrderTraverseNode(node.left, callback); //{2} preOrderTraverseNode(node.right, callback); //{3}  } }; this.postOrderTraverse = function(callback){ postOrderTraverseNode(root, callback); }; var postOrderTraverseNode = function (node, callback) { if (node !== null) { postOrderTraverseNode(node.left, callback); //{1} postOrderTraverseNode(node.right, callback); //{2} callback(node.key); //{3}  } }; this.min = function() { return minNode(root); }; var minNode = function(node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.key; } return null; }; this.max = function() { return maxNode(root); }; var maxNode = function (node) { if (node){ while (node && node.right !== null) { //{5} node = node.right; } return node.key; } return null; }; this.search = function(key) { return searchNode(root, key); }; var searchNode = function(node, key) { if (node === null) { return false; } if (key < node.key) { return searchNode(node.left, key); } else if (key > node.key) { return searchNode(node.right, key); }else{ return true; } }; this.remove = function(key) { root = removeNode(root, key); }; var removeNode = function(node, key){ if (node === null){ //{2} return null; } if (key < node.key){ //{3} node.left = removeNode(node.left, key); //{4} return node; //{5} } else if (key > node.key){ //{6} node.right = removeNode(node.right, key); //{7} return node; //{8} } else { //键等于node.key //第一种情况——一个叶节点 if (node.left === null && node.right === null){ //{9} node = null; //{10} return node; //{11}  } //第二种情况——一个只有一个子节点的节点 if (node.left === null){ //{12} node = node.right; //{13} return node; //{14} } else if (node.right === null){ //{15} node = node.left; //{16} return node; //{17}  } //第三种情况——一个有两个子节点的节点 var aux = findMinNode(node.right); //{18} node.key = aux.key; //{19} node.right = removeNode(node.right, aux.key); //{20} return node; //{21}  } }; } function printNode(value) { console.log(value); } 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(printNode); tree.preOrderTraverse(printNode); tree.postOrderTraverse(printNode); console.log(tree.min()); console.log(tree.max()); console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.'); console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.'); </script> </head> <body> </body> </html>