排序-二叉树
2018-06-26 本文已影响16人
这个超人不会飞阿
二叉树的排序可以分为
中序排序 左 中 右
前序排序 中 左 右
后序排序 左 右 中
中序排序能够快速遍历出最大或者最小.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
<script>
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);
}
}
}
var inOrderTraverseNode = function(root,callback) {
if(root!=null) {
inOrderTraverseNode(root.left,callback);
callback(root.key);
inOrderTraverseNode(root.right,callback);
}
}
//中序遍历
this.inOrderTraverse = function(callback){
inOrderTraverseNode(root,callback);
}
var preOrderTraverseNode = function(root,callback) {
if(root!=null){
callback(root.key);
preOrderTraverseNode(root.left,callback);
preOrderTraverseNode(root.right,callback);
}
}
//前序遍历
this.preOrderTraverse = function(callback){
preOrderTraverseNode(root,callback);
}
var endOrderTraverseNode = function(root,callback){
if(root!=null){
endOrderTraverseNode(root.left,callback);
endOrderTraverseNode(root.right,callback);
callback(root.key);
}
}
//后序遍历
this.endOrderTraverse = function(callback) {
endOrderTraverseNode(root,callback);
}
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);
}
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 findNode = function(n,node) {
if(node==null){
return false;
}
if(node.key<n){
return findNode(n,node.right);
} else if (node.key == n){
return true;
} else {
return findNode(n,node.left);
}
}
//查找具体某一个值
this.find = function(n){
return findNode(n,root);
}
var that = this;
var deleteLeavesNode = function(n,node) {
if(node!=null){
if(node.key < n) {
node.right = deleteLeavesNode(n,node.right);
return node;
} else if(node.key > n){
node.left = deleteLeavesNode(n,node.left);
return node;
}else {
// 这个else判断的是已经找到了n,看这个n是叶子结点 还是只含有一个子树的节点
if (node.left === null && node.right === null) {
node = null;
return node;
}else if(node.left === null) {
node = node.right;
return node;
}else if(node.right === null) {
node = node.left;
return node;
}else if(node.left!=null && node.left!=null) {
//删除含有左右子树的节点 原理是:删除该节点,并将右子树的最小代替已删除的node
node.key = minNode(node.right);
node.right = deleteLeavesNode(node.key,node.right);
return node;
}
}
} else {
return null;
}
}
//删除叶子节点
this.deleteLeaves = function(n) {
root = deleteLeavesNode(n,root);
}
//删除只含有一个子树的节点
this.insert = function(key){
var newNode = new Node(key);
if(root == null) {
root = newNode;
} else {
insertNode(root,newNode);
}
}
}
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); }
console.log('中序遍历');
binaryTree.inOrderTraverse(callback);
console.log('-------');
console.log('前序遍历');
binaryTree.preOrderTraverse(callback);
console.log('后序遍历');
binaryTree.endOrderTraverse(callback);
console.log('最小值');
console.log(binaryTree.min());
console.log('最大值');
console.log(binaryTree.max());
console.log('查到存在与否');
console.log(binaryTree.find(10));
// console.log('删除一个叶子节点');
// binaryTree.deleteLeaves(13);
// console.log('删除一个只含有一个子树的节点');
// binaryTree.deleteLeaves(10);
console.log('删除一个含有左右子树的节点');
binaryTree.deleteLeaves(6);
console.log('前序遍历');
binaryTree.preOrderTraverse(callback);
</script>
</head>
<body>
</body>
</html>
