本文實例講述了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程序設計有所幫助。