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

本文实例讲述了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程序设计有所帮助。