Home  >  Article  >  Web Front-end  >  Javascript data structure binary search tree implementation method_javascript skills

Javascript data structure binary search tree implementation method_javascript skills

WBOY
WBOYOriginal
2016-05-16 15:29:56962browse

The example in this article describes the implementation method of binary search tree in javascript. Share it with everyone for your reference, the details are as follows:

Binary search tree: As the name suggests, each node in the tree has at most two forks; and the value of the left fork node is < the value of the right fork node is .

Features: Inserting nodes, finding the largest/minimum nodes, and sorting node values ​​are very convenient

Binary search tree-javascript implementation

<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 &#63; "不存在" : minNode.data));
 println("<br/>");
 var maxNode = bTree.max();
 println("最大节点:" + (maxNode == null &#63; "不存在" : 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-->

Output result:

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

I hope this article will be helpful to everyone in JavaScript programming.

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn