JavaScript二叉树实践---排序（前序、中序、后序）
2019-06-20 本文已影响0人
小芃同学
仅仅记录一下
本文代码可直接测试
<!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>javascript数据结构</title>
</head>
<body>
<script type="text/javascript">
//生成随机数
function randomNum(iNumber,iNow){
var arrNumber = [];
var newNumber = [];
for(var i=0;i<=iNumber;i++){
arrNumber.push(i);
}
for(var i=0;i<iNow;i++){
newNumber.push(arrNumber.splice(Math.floor(Math.random()*arrNumber.length),1)); //这里注意用法Math.floor向下取整，随机数取得数【0-1）不会越界，如果使用Math.round则，后面数组的长度则-1，否则数组下标越界，会有问题
}
return newNumber;
}
/**
* 冒泡排序
* */
function maoPao(arr){
console.time("maoPao");
for(var i = 0;i<arr.length-1;i++){
for(var j = 0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
console.timeEnd("maoPao");
// console.log("maopao",arr);
return arr;
}
/**
* ****************************二叉树****************************
* 根节点
* 父子节点
* 兄弟节点
* 叶子节点
*
* 二叉树的高
*
* ***************************排序二叉树***************************
* 左孩子的值小于节点值，右孩子的值大于节点值
*
* ****************************************************************
* ***************************前序
*
* ***************************中序
* 先看左孩子，遍历左子树，遍历右子树，
*
* ***************************后序
* */
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);
}
};
//中序遍历
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);
}
}
//前序遍历
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 postOrderTracerseNode = function(node,callback){
if(node!==null){
postOrderTracerseNode(node.left,callback);
postOrderTracerseNode(node.right,callback);
callback(node.key);
}
}
/**
* /@function 后序遍历
*
*
*/
this.postOrderTracerse = function(callback){
postOrderTracerseNode(root,callback);
}
//查找最小值
var minNode = function(node){
if(node!==null){
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!==null){
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
}
this.max = function(){
return maxNode(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.search = function(key){
return searchNode(root,key);
}
//删除
var findMinNode = function(node){
if(node){
while(node && node.left!==null){
node = node.left;
}
return node;
}
}
var removeNode = function(node,key){
if(node === null){
return null;
}
if(key < node.key){
node.left = removeNode(node.left,key);
return node;
}else if(key > node.key){
node.right = removeNode(node.right,key);
return node;
}else{
if(node.left === null && node.right === null){
node = null;
return node;
}
if(node.left === null){
node = node.right;
return node;
}else if(node.right === null){
node = node.left;
return node;
}
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(nodde.right,aux.key);
}
}
this.remove = function(key){
root = removeNode(root,key);
}
}
var nodes = [8,10,1,2,19,7,6,4,3,13,];
// var nodes = randomNum(10000,100);
console.log("原数组",nodes);
console.time("binary");
//构造二叉树
var binaryTree = new BinaryTree();
nodes.forEach(element => {
binaryTree.insert(element);
});
var newNodes = [];
//回调函数
var getNode = function(key){
newNodes.push(key);
}
console.timeEnd("binary");
//排序
// console.time("in");
// binaryTree.inOrderTraverse(getNode);
// console.timeEnd("in");
//中序，，，从左到右，从根节点到叶子节点，，输出节点值
// console.log("binary",newNodes);
//测试冒泡排序
// maoPao(nodes);
console.time("pre");
binaryTree.preOrderTraverse(getNode);
console.timeEnd("pre");
console.log(newNodes);
/**
* *******************二叉树******************
*
* ****************查找算法*******************
*
*
*
* */
console.time("max");
console.log(binaryTree.max());
console.timeEnd("max");
console.time("min");
console.log(binaryTree.min());
console.timeEnd("min");
console.log(binaryTree.search(7))
console.log(binaryTree.search(9))
console.log(binaryTree.remove(7));
console.log(newNodes);
</script>
</body>
</html>
少量数据下冒泡排序能快点，但是当数据量多点得话二叉树得性能并非冒泡排序能比的。
