厚德载物ddd
2019-03-26 15:10:26浏览 2017
二叉树的算法在海量数据的排序上相比于其他排序算法效率要高很多,中序遍历相当于数组的升序排列,前序遍历是对相同二叉树的赋值,但是对于重新排列一个相同结构二叉树来说,效率也要高很多,后序遍历相当于对数组的降序排列。
打印输出顺序:
中序遍历: 左-->根-->右
前序遍历: 根-->左-->右
后序遍历: 左-->右-->根
//构建一个二叉树
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){//自定义函数insert()
var newNode = new Node(key);//实例化一个Node节点对象
if(root == null){//判断根节点是否为空
root = newNode;
}else{
insertNode(root, newNode);
}
};
var inOrderTraversalNode = function(node, callBack){
if(node !== null){
inOrderTraversalNode(node.left, callBack);
callBack(node.key);
inOrderTraversalNode(node.right, callBack);
}
};
//中序遍历
this.inOrderTraversal = function(callBack){
inOrderTraversalNode(root, callBack);
}
var preOrderTraversalNode = function(node, callBack){
if(node !== null){
callBack(node.key);
inOrderTraversalNode(node.left, callBack);
inOrderTraversalNode(node.right, callBack);
}
};
//前序遍历
this.preOrderTraversal = function(callBack){
preOrderTraversalNode(root, callBack);
}
var postOrderTraversalNode = function(node, callBack){
if(node !== null){
postOrderTraversalNode(node.left, callBack);
postOrderTraversalNode(node.right, callBack);
callBack(node.key);
}
};
//后序遍历
this.postOrderTraversal = function(callBack){
postOrderTraversalNode(root, callBack);
}
}
var callBack = function(key){
console.log(key);
};
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
var binayTree = new BinaryTree(); //实例化一个二叉树
nodes.forEach(function(key){
binayTree.insert(key);
})
//binayTree.inOrderTraversal(callBack);
//
//binayTree.preOrderTraversal(callBack);
//
binayTree.postOrderTraversal(callBack);