<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body>
<script type="text/javascript">
function BinaryTree() {
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
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.insert = function(key){
var newNode = new Node(key);
if (root === null) {
root = newNode;
}else{
insertNode(root,newNode);
}
}
//遍历Tree
this.Traverse = function(node,callback){
inOderTraverseNode(node ,callback);
}
//中序遍历
var inOderTraverseNode = function (node ,callback){
if (node !== null) {
inOderTraverseNode(node.left,callback);
callback(node.key);
inOderTraverseNode(node.right,callback);
}
}
//
this.inOderTraverse = function(callback){
inOderTraverseNode(root ,callback);
}
//前序遍历（复制二叉树，时间复杂度最短）
var preOrderTraverseNode = function (node,callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);
}
}
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root,callback);
}
//后序遍历,(应用：遍历文件夹)
var afOrderTraverseNode = function (node,callback) {
if (node !== null) {
afOrderTraverseNode(node.left,callback);
afOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
this.afOrderTraverse = function (callback) {
afOrderTraverseNode(root,callback);
}
//Tree的最小值
var minNode = function (node){
if (node) {
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
this.min = function () {
return minNode(root);
}
//Tree的最大值
var maxNode = function(node){
if (node) {
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
}
this.max = function (){
return maxNode(root);
}
//查找
var search = function(v,node){
if (node !== null) {
if (v === node.key) {
return true;
}else if (v < node.key) {
return search(v,node.left);
}else{
return search(v,node.right);
}
}
return false;
}
this.searchV = function(v){
return search(v,root);
}
//删除
var deleteNode = function (key,node){
if (node ===null) {
return null;
}
if (key < node.key) {
node.left = deleteNode(key,node.left);
return node;
}else if (key > node.key) {
node.right = deleteNode(key,node.right);
return node;
}else{
if (node.left === null && node.right === null) {
node = null;
return node;
}
if (node.left !== null && node.right === null) {
return node.left;
}
if (node.left === null && node.right !== null) {
return node.right;
}
if (node.left !== null && node.right !== null) {
var aux = findMinNode(node.right);
node.key = aux.key; //这里不是直接删除，而是替换
node.right = deleteNode(aux.key,node.right);
return node;
}
}
}
//找到最小值节点
var findMinNode = function (node) {
if (node) {
while(node && node.left !== null){
return node.left;
}
return node;
}
return null;
}
this.delete = function (key) {
return deleteNode(key,root);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key);
});
var callback = function(key) {
console.log(key);
}
binaryTree.inOderTraverse(callback);
console.log("binaryTree's minValue = "+binaryTree.min(binaryTree.root));
console.log("binaryTree's maxValue = "+binaryTree.max(binaryTree.root));
console.log("This value is exit: "+binaryTree.searchV(7));
console.log("This Tres delete 7 ,and result is :" + binaryTree.Traverse(binaryTree.delete(7),callback));
</script>
</body>
</html>以上代码，是作者根据自己曾经看过的一个视频自己手动写下来的，现在回看起来挺值得学习，博客：www.sudo.ren。
