javascript数据结构之二叉搜索树实现方法

本文实例讲述了javascript二叉搜索树实现方法。分享给大家供大家参考，具体如下：
二叉搜索树：顾名思义，树上每个节点最多只有二根分叉；而且左分叉节点的值 < 右分叉节点的值。
特点：插入节点、找最大/最小节点、节点值排序非常方便
二叉搜索树-javascript实现

<script type="text/javascript">// <！[CDATA[ //打印输出 function println（msg） {document.write（msg + " "）; } //节点类 var Node = function （v） {this.data = v; //节点值this.left = null; //左节点this.right = null; //右节点 } //二叉搜索树类 var BinarySearchTree = function （） {this.root = null; //初始化时,根节点为空//插入节点//参数：v 为节点的值this.insert = function （v） { var newNode = new Node（v）; if （this.root == null） {//树为空时，新节点，直接成为根节点this.root = newNode;return; } var currentNode = this.root; //工作“指针”节点（从根开始向下找） var parentNode = 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 （） { var p = this.root; //工作节点while （p ！= null && p.left ！= null） {p = p.left; } return p;}//查找最大节点this.max = function （） { var p = this.root; //工作节点while （p ！= null && p.right ！= null） {p = p.right; } return p;}//中序遍历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）; //再根节点 }} } //以下是测试 var bTree = new BinarySearchTree（）; //《沙特.算法设计技巧与分析》书上图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/>"）; var minNode = bTree.min（）; println（"最小节点：" + （minNode == null ? "不存在" : minNode.data））; println（"<br/>"）; var maxNode = bTree.max（）; println（"最大节点：" + （maxNode == null ? "不存在" : maxNode.data））;// ]]></script><！--中序遍历： 1 3 4 6 8 9 <br> 先序遍历： 6 3 1 4 8 9 <br> 后序遍历： 1 4 3 9 8 6 <br> 最小节点：1 <br> 最大节点：9-->

输出结果：

中序遍历： 1 3 4 6 8 9 先序遍历： 6 3 1 4 8 9 后序遍历： 1 4 3 9 8 6 最小节点：1 最大节点：9

希望本文所述对大家JavaScript程序设计有所帮助。