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

这篇文章主要介绍了javascript数据结构之二叉搜索树实现方法,较为详细的分析了二叉搜索树的概念、原理与JavaScript实现二叉搜索树的方法,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下

 

本文实例讲述了javascript二叉搜索树实现方法。分享给大家供大家参考，具体如下：

二叉搜索树：顾名思义，树上每个节点最多只有二根分叉；而且左分叉节点的值 < 右分叉节点的值 。

特点：插入节点、找最大/最小节点、节点值排序 非常方便

二叉搜索树-javascript实现
 

1. <script type="text/javascript"> 
2. // <![CDATA[ 
3.  //打印输出 
4.  function println(msg) { 
5.   document.write(msg + " "); 
6.  } 
7.  //节点类 
8.  var Node = function (v) { 
9.   this.data = v; //节点值 
10.   this.left = null; //左节点 
11.   this.right = null; //右节点 
12.  } 
13.  //二叉搜索树类 
14.  var BinarySearchTree = function () { 
15.   this.root = null; //初始化时,根节点为空 
16.   //插入节点 
17.   //参数：v 为节点的值 
18.   this.insert = function (v) { 
19.    var newNode = new Node(v); 
20.    if (this.root == null) { 
21.     //树为空时，新节点，直接成为根节点 
22.     this.root = newNode; 
23.     return; 
24.    } 
25.    var currentNode = this.root; //工作“指针”节点（从根开始向下找） 
26.    var parentNode = null; 
27.    while (true) { 
28.     parentNode = currentNode; 
29.     if (v < currentNode.data) { 
30.      //当前节点的值 > 目标节点的值      
31.      //应该向左插，工作节点移到左节点 
32.      currentNode = currentNode.left; 
33.      if (currentNode == null) { 
34.       //没有左节点，则新节点，直接成为左节点 
35.       parentNode.left = newNode; 
36.       return; //退出循环 
37.      } 
38.     } 
39.     else { 
40.      //否则向右插，工作节点移到右节点 
41.      currentNode = currentNode.right; 
42.      if (currentNode == null) { 
43.       parentNode.right = newNode; 
44.       return; 
45.      } 
46.     } 
47.    } 
48.   } 
49.   //查找最小节点 
50.   this.min = function () { 
51.    var p = this.root; //工作节点  
52.    while (p != null && p.left != null) { 
53.     p = p.left; 
54.    } 
55.    return p; 
56.   } 
57.   //查找最大节点 
58.   this.max = function () { 
59.    var p = this.root; //工作节点  
60.    while (p != null && p.right != null) { 
61.     p = p.right; 
62.    } 
63.    return p; 
64.   } 
65.   //中序遍历 
66.   this.inOrder = function (rootNode) { 
67.    if (rootNode != null) { 
68.     this.inOrder(rootNode.left); //先左节点 
69.     println(rootNode.data); //再根节点 
70.     this.inOrder(rootNode.right); //再右节点 
71.    } 
72.   } 
73.   //先序遍历 
74.   this.preOrder = function (rootNode) { 
75.    if (rootNode != null) { 
76.     println(rootNode.data); //先根 
77.     this.preOrder(rootNode.left); //再左节点 
78.     this.preOrder(rootNode.right); //再右节点 
79.    } 
80.   } 
81.   //后序遍历 
82.   this.postOrder = function (rootNode) { 
83.    if (rootNode != null) { 
84.     this.postOrder(rootNode.left); //先左节点 
85.     this.postOrder(rootNode.right); //再右节点 
86.     println(rootNode.data); //再根节点 
87.    } 
88.   } 
89.  } 
90.  //以下是测试 
91.  var bTree = new BinarySearchTree(); 
92.  //《沙特.算法设计技巧与分析》书上图3.9 左侧的树 
93.  bTree.insert(6); 
94.  bTree.insert(3); 
95.  bTree.insert(8); 
96.  bTree.insert(1); 
97.  bTree.insert(4); 
98.  bTree.insert(9); 
99.  println('中序遍历：') 
100.  bTree.inOrder(bTree.root); 
101.  println("<br/>"); 
102.  println("先序遍历："); 
103.  bTree.preOrder(bTree.root); 
104.  println("<br/>"); 
105.  println("后序遍历："); 
106.  bTree.postOrder(bTree.root); 
107.  println("<br/>"); 
108.  var minNode = bTree.min(); 
109.  println("最小节点：" + (minNode == null ? "不存在" : minNode.data)); 
110.  println("<br/>"); 
111.  var maxNode = bTree.max(); 
112.  println("最大节点：" + (maxNode == null ? "不存在" : maxNode.data)); 
113. // ]]> 
114. </script> 
115. <!--中序遍历： 1 3 4 6 8 9 <br> 先序遍历： 6 3 1 4 8 9 <br> 后序遍历： 1 4 3 9 8 6 <br> 最小节点：1 <br> 最大节点：9-->