JS实现的二叉树算法完整实例
程序员文章站
2024-02-08 10:01:28
本文实例讲述了js实现的二叉树算法。分享给大家供大家参考，具体如下：
本文实例讲述了js实现的二叉树算法。分享给大家供大家参考，具体如下：
<!doctype html>
<head>
<title>20130328binarytree</title>
<metahttp-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<html>
<body>
<script>
//今天学习了下二叉树算法，总结在这里
//1全局变量 binary tree =bt
//1.1 node
function node() { //bt节点
this.text = ''; //节点的文本
this.leftchild = null; //节点的左孩子引用
this.rightild = null; //节点右孩子引用
}
//1.2 二叉树装载的字符串
var strtext = "";
var charecters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];
var len = charecters.length ; //数组的长度
var nodes = new array(); //创建一个临时数组，用于存放二叉树节点
//循环创建二叉树节点存放到数组中
for (var i = 0 ; i < len ; i++) {
var node = new node();
node.text = charecters[i];
nodes.push(node);
}
var root = nodes[0];
//1.3 栈
function stack() {
var stack = new array(); //存放栈的数组
//压栈
this.push = function(o) {
stack.push(o);
};
//出栈
this.pop = function() {
var o = stack[stack.length-1];
stack.splice(stack.length-1, 1);
return o;
};
//检查栈是否为空
this.isempty = function() {
if(stack.length <= 0) {
return true;
}
else {
return false;
}
};
}
//使用方式如下
var stack = new stack();
stack.push(1); //现在栈中有一个元素
stack.isempty(); //false , 栈不为空
//alert(stack.pop()); //出栈, 打印1
stack.isempty(); //true, 此时栈为空，因为在调用了stack.pop()之后元素出栈了，所以为空
//2.1递归实现：
function buildbt1(node, i) {
var leftindex = 2*i+1, //左孩子节点的索引
rightindex = 2*i+2; //右孩子节点的索引
if(leftindex < charecters.length) { //判断索引的长度是否超过了charecters数组的大小
var childnode = new node(); //创建一个新的节点对象
childnode.text = charecters[leftindex]; //给节点赋值
node.leftchild = childnode; //给当前节点node加入左孩子节点
buildbt1(childnode, leftindex); //递归创建左孩子
}
if(rightindex < charecters.length) { //同上
var childnode = new node();
childnode.text = charecters[rightindex];
node.rightchild = childnode;
buildbt1(childnode, rightindex);
}
}
//2.2非递归实现
function buildbt2() {
index = 0; //索引从0开始
//循环建立二叉树子节点的引用
while(index < len) {
var leftindex = 2*index+1, //当前节点左孩子索引
rightindex = 2*index+2; //当前节点右孩子索引
//给当前节点添加左孩子
nodes[index].leftchild = nodes[leftindex];
//给当前节点添加右孩子
nodes[index].rightchild = nodes[rightindex];
index++;
}
}
//3遍历
//3.1.1先序递归遍历
function firstiteration(node) {
if(node.leftchild) { //判断当前节点是否有左孩子
firstiteration(node.leftchild); //递归左孩子
}
if(node.rightchild) { //判断当前节点是否有右孩子
firstiteration(node.rightchild); //递归右孩子
}
}
//递归遍历二叉树
firstiteration(root);
//3.1.2先序普通遍历
function notfirstiteration(node) {
var stack = new stack(), //开辟一个新的栈对象
resulttext = ''; //存放非递归遍历之后的字母顺序
stack.push(root); //这个root在上面非递归方式构建二叉树的时候已经构建好的
var node = root;
resulttext += node.text;
while(!stack.isempty()) {
while(node.leftchild) { //判断当前节点是否有左孩子节点
node = node.leftchild; //取当前节点的左孩子节点
resulttext += node.text; //访问当前节点
stack.push(node); //将当前节点压入栈中
}
stack.pop(); //出栈
node = stack.pop().rightchild; //访问当前节点的兄弟节点（右孩子节点）
if(node) { //当前节点的兄弟节点不为空
resulttext += node.text; //访问当前节点
stack.push(node); //将当前节点压入栈中
}
else { //当前节点的兄弟节点为空
node = stack.pop(); //在回溯到上一层
}
}
}
//非递归先序遍历
// notfirstiteration(root);
//3.2.1中序递归遍历
function btiteration21(node) {
//访问左节点
if(node.leftchild) {
if(node.leftchild.leftchild) {
btiteration21(node.leftchild);
}
else {
strtext += node.leftchild.text;
}
}
//访问根节点
strtext += node.text;
//访问右节点
if(node.rightchild) {
if(node.rightchild.leftchild) {
btiteration21(node.rightchild);
}
else {
strtext += node.rightchild.text;
}
}
}
//测试区
//2.1.1测试递归实现
var node = new node();
node.text = charecters[0];
buildbt1(node, 0); //索引i是从0开始构建
btiteration21(node);
alert(strtext);
</script>
</body>
</html>
更多关于javascript相关内容感兴趣的读者可查看本站专题：《javascript数据结构与算法技巧总结》、《javascript数学运算用法总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。