這篇文章主要介紹了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-->