Js排序二叉树,创建,插入,查找,删除以及多种排序

<!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

评论区