javascript数据结构之二叉搜索树实现方法
本文实例讲述了javascript二叉搜索树实现方法。分享给大家供大家参考，具体如下：
二叉搜索树：顾名思义，树上每个节点最多只有二根分叉；而且左分叉节点的值<右分叉节点的值。
特点：插入节点、找最大/最小节点、节点值排序非常方便
二叉搜索树-javascript实现
<scripttype="text/javascript">
//<![CDATA[
//打印输出
functionprintln(msg){
document.write(msg+"");
}
//节点类
varNode=function(v){
this.data=v;//节点值
this.left=null;//左节点
this.right=null;//右节点
}
//二叉搜索树类
varBinarySearchTree=function(){
this.root=null;//初始化时,根节点为空
//插入节点
//参数：v为节点的值
this.insert=function(v){
varnewNode=newNode(v);
if(this.root==null){
//树为空时，新节点，直接成为根节点
this.root=newNode;
return;
}
varcurrentNode=this.root;//工作“指针”节点（从根开始向下找）
varparentNode=null;
while(true){
parentNode=currentNode;
if(v<currentNode.data){
//当前节点的值>目标节点的值
//应该向左插，工作节点移到左节点
currentNode=currentNode.left;
if(currentNode==null){
//没有左节点，则新节点，直接成为左节点
parentNode.left=newNode;
return;//退出循环
}
}
else{
//否则向右插，工作节点移到右节点
currentNode=currentNode.right;
if(currentNode==null){
parentNode.right=newNode;
return;
}
}
}
}
//查找最小节点
this.min=function(){
varp=this.root;//工作节点
while(p!=null&&p.left!=null){
p=p.left;
}
returnp;
}
//查找最大节点
this.max=function(){
varp=this.root;//工作节点
while(p!=null&&p.right!=null){
p=p.right;
}
returnp;
}
//中序遍历
this.inOrder=function(rootNode){
if(rootNode!=null){
this.inOrder(rootNode.left);//先左节点
println(rootNode.data);//再根节点
this.inOrder(rootNode.right);//再右节点
}
}
//先序遍历
this.preOrder=function(rootNode){
if(rootNode!=null){
println(rootNode.data);//先根
this.preOrder(rootNode.left);//再左节点
this.preOrder(rootNode.right);//再右节点
}
}
//后序遍历
this.postOrder=function(rootNode){
if(rootNode!=null){
this.postOrder(rootNode.left);//先左节点
this.postOrder(rootNode.right);//再右节点
println(rootNode.data);//再根节点
}
}
}
//以下是测试
varbTree=newBinarySearchTree();
//《沙特.算法设计技巧与分析》书上图3.9左侧的树
bTree.insert(6);
bTree.insert(3);
bTree.insert(8);
bTree.insert(1);
bTree.insert(4);
bTree.insert(9);
println('中序遍历：')
bTree.inOrder(bTree.root);
println("<br/>");
println("先序遍历：");
bTree.preOrder(bTree.root);
println("<br/>");
println("后序遍历：");
bTree.postOrder(bTree.root);
println("<br/>");
varminNode=bTree.min();
println("最小节点："+(minNode==null?"不存在":minNode.data));
println("<br/>");
varmaxNode=bTree.max();
println("最大节点："+(maxNode==null?"不存在":maxNode.data));
//]]>
</script>
<!--中序遍历：134689<br>先序遍历：631489<br>后序遍历：143986<br>最小节点：1<br>最大节点：9-->
输出结果：
中序遍历：134689 先序遍历：631489 后序遍历：143986 最小节点：1 最大节点：9
希望本文所述对大家JavaScript程序设计有所帮助。