慕课网学习之Javascript实现二叉树算法
一、二叉树算法及代码实现
1、Javascript和数据结构
程序=算法+数据结构
单步调试:
2、二叉树定义的原理说明
排序二叉树:
左孩子的值小于父亲结点的值,右孩子的值大于父亲结点的值。
代码实现:
<script>
function BinaryTree(){
var Node=function(key){
this.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;//root为根结点
}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);
});
</script>
function BinaryTree(){
var Node=function(key){
this.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;//root为根结点
}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);
});
</script>
3、中序遍历
遍历顺序:左中右:1-3-4-6-7-8-10-13-14
//中序遍历
var inOrderTraverseNode=function(node,callback){
if(node!==null){
inOrderTraverseNode(node.left,callback);//先访问结点的左子树
callback(node.key);//传入当前结点的值
inOrderTraverseNode(node.right,callback);
}
};
//中序遍历(接口)
this.inOrderTraverse=function(callback){
inOrderTraverseNode(root,callback);
};
inOrderTraverseNode(node.left,callback);//先访问结点的左子树
callback(node.key);//传入当前结点的值
inOrderTraverseNode(node.right,callback);
}
};
//中序遍历(接口)
this.inOrderTraverse=function(callback){
inOrderTraverseNode(root,callback);
};
//遍历二叉树
console.log("中序遍历");
var callback1=function(key){
console.log(key);
};
binaryTree.inOrderTraverse(callback1);
var callback1=function(key){
console.log(key);
};
binaryTree.inOrderTraverse(callback1);
程序运行结果:
4、前序遍历
遍历顺序:中左右:8-3-1-6-4-7-10-14-13
//前序遍历
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 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);
};
//遍历二叉树(前序)
console.log("前序遍历");
var callback2=function(key){
console.log(key);
};
binaryTree.preOrderTraverse(callback2);
console.log("前序遍历");
var callback2=function(key){
console.log(key);
};
binaryTree.preOrderTraverse(callback2);
程序运行结果:
5、后序遍历
遍历顺序:中右左:8-10-14-13-3-6-7-4-1
//后序遍历
var postOrderTraverseNode=function(node,callback){
if(node!==null){
callback(node.key);
postOrderTraverseNode(node.right,callback);
postOrderTraverseNode(node.left,callback);
}
};
this.postOrderTraverse=function(callback){
postOrderTraverseNode(root,callback);
};
var postOrderTraverseNode=function(node,callback){
if(node!==null){
callback(node.key);
postOrderTraverseNode(node.right,callback);
postOrderTraverseNode(node.left,callback);
}
};
this.postOrderTraverse=function(callback){
postOrderTraverseNode(root,callback);
};
//遍历二叉树(后序)
console.log("后序遍历");
var callback3=function(key){
console.log(key);
};
binaryTree.postOrderTraverse(callback3);
console.log("后序遍历");
var callback3=function(key){
console.log(key);
};
binaryTree.postOrderTraverse(callback3);
程序运行结果:
6、二叉树结点查找
(1)查找二叉树中的最小值:8-3-1=》1
//查找最小值
var minNode=function(node){
if(node.left!==null){
return minNode(node.left);
}else{
return node.key;
}
};
this.min=function(){
return minNode(root);
};
var minNode=function(node){
if(node.left!==null){
return minNode(node.left);
}else{
return node.key;
}
};
this.min=function(){
return minNode(root);
};
//查找最小值
console.log("min node is:"+binaryTree.min());
console.log("min node is:"+binaryTree.min());
程序运行结果:
(2)查找二叉树中最大值:8-10-14
同查找最小值
程序运行结果:
(3)查找指定值
例如:a. 查找值7:8-3-6-7,查找成功
b. 查找值12:8-10-14-13,查无此值,查找失败
//查找指定值
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 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);
};
//查找指定值
console.log(binaryTree.search(7)?'key 7 is found':'key 7 is not found');
console.log(binaryTree.search(12)?'key 12 is found':'key 12 is not found');
console.log(binaryTree.search(7)?'key 7 is found':'key 7 is not found');
console.log(binaryTree.search(12)?'key 12 is found':'key 12 is not found');
程序运行结果:
7、二叉树叶子结点的删除
//删除叶子结点
var removeNode=function(node,key){
if(node===null){
return null;
}
if(key<node.key){
return removeNode(node.left,key);
}else if(key>node.key){
return removeNode(node.right,key);
}else{
return node.key;
}
};
this.remove=function(key){
return removeNode(root,key);
};
var removeNode=function(node,key){
if(node===null){
return null;
}
if(key<node.key){
return removeNode(node.left,key);
}else if(key>node.key){
return removeNode(node.right,key);
}else{
return node.key;
}
};
this.remove=function(key){
return removeNode(root,key);
};
//删除叶子结点
console.log('删除叶子结点为:'+binaryTree.remove(10));
console.log('删除叶子结点为:'+binaryTree.remove(10));
程序运行结果: