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