function BinaryTree(){//二叉树构造函数
var Node=function(key){//定义二叉树节点构造函数
this.key=key;
this.left=null;
this.right=null;
}
var root=null;//定义一个根节点
this.insert=function(key){
var newNode=new Node(key);//创建一个二叉树新节点(newNode)
if(root===null){
root=newNode;
}else{
//插入新节点(newNode)
insertNode(root,newNode);
}
}
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);
}
}
}
//中序遍历二叉树 callback:回调函数
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);
}
}
//前序遍历
this.preTraverse=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.postTraverse=function(callback){
postOrderTraverseNode(root,callback);
}
//后序遍历当前节点
var postOrderTraverseNode=function(node,callback){
if(node!==null){
//访问当前节点的左子树
postOrderTraverseNode(node.left,callback);
//访问当前节点的右子树
postOrderTraverseNode(node.right,callback);
//当前节点值
callback(node.key);
}
}
//查找最小值
this.min=function(){
return minNode(root);
}
var minNode=function(node){
if(node){
while(node&&node.left!==null){
node=node.left;
}
return node.key;
}
return null;
}
//查找最大值
this.man=function(){
return manNode(root);
}
var manNode=function(node){
if(node){
while(node&&node.right!==null){
node=node.right;
}
return node.key;
}
return null;
}
//查找二叉树是否含有某个给定的值
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;
}
}
//删除二叉树中的某个值
var findMinNode=function(node){
if(node){
while(node&&node.left!==null){
node=node.left;
}
return node;
}
return null;
}
this.node=function(key){
return removeNode(root,key);
}
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;
}else 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(node.right,aux.key);
return node;
}
}
}
var nodes=[8,3,10,1,6,14,4,7,13];
//创建二叉树对象
var binaryTree=new BinaryTree();
nodes.forEach(function(value){
//二叉树对象（binaryTree）调用插入新节点函数:insert（）,生成二叉树。
binaryTree.insert(value);
});
var infixOrder=[];
var callback=function(value){
// infixOrder.push(value)
console.log(value)
}
//中序遍历出的数据是有序的（从小到大）
// //中序遍历二叉树，二叉树对象（binaryTree）调用中序遍历函数:inOrderTraverse（）
// binaryTree.inOrderTraverse(callback);
// //console.log(infixOrder)
//前序遍历二叉树可以快速复制一个二叉树，前序复制算法是插入算法的n倍
//前序遍历二叉树，二叉树对象（binaryTree）调用前序遍历函数:preTraverse（）
// binaryTree.preTraverse(callback);
// //console.log(infixOrder)
/*
后序遍历二叉树的应用：
* 1、系统遍历文件
* 2、在删除文件夹时，必须保证文件夹中无文件，有文件时需先删除文件，再删除文件夹，
*
* */
//后序遍历二叉树，二叉树对象（binaryTree）调用后序遍历函数:inOrderTraverse（）
// binaryTree.postTraverse(callback);
// //console.log(infixOrder)
// var minValue=binaryTree.min();
// console.log("最小值是："+minValue);
// var manValue=binaryTree.man();
// console.log("最大值是："+manValue);
console.log(binaryTree.search(7)?"7存在":"7不存在");
console.log(binaryTree.search(9)?"9存在":"9不存在");
binaryTree.node(3);
console.log(binaryTree.search(3)?"3存在":"3不存在");
网友评论