JavaScript实现二叉树定义、遍历及查找的方法详解
本文实例讲述了javascript实现二叉树定义、遍历及查找的方法。分享给大家供大家参考,具体如下:
二叉树(binary tree)
在写这篇文章之前说一下数据结构和算法这个系列,这个系列包含了很多东西,比如啥子排序,线性表,广义表,树,图这些大家都是知道的,但是这些东西我们学了之后工作中能用到的又有多少呢,据我所知绝大部分公司,一线码农,屌丝,程序猿是用不到这些东西,既然这样为啥子我还要强调这个系列呢,本人觉得算法和数据结构是程序的基本功,前提想脱离一线码农,普通程序猿行列,说得通俗一点就是让自己变的更牛逼。其次语言都是想通的,只要是掌握了一门语言学习其他语言就如同顺水推舟,不费一点力气。另外还有一点就是我会一直把这个系列写下去, 虽然网上一搜一大筐,已经写烂了,但是我写作的目的有两个,第一和大家分享, 第二可以让自己更深入的理解。好了,其他的不多说了,最近复习了一下二叉树, 就先写这个,后面会依次的加上排序, 线性表,广义表。。。。等等
二叉树
一说到二叉树我们肯定会问,什么是二叉树,二叉树是个啥子东东,拿来有啥子用嘛,我们为啥子要学习它嘛? 如果当初你在学习二叉树的时候你没有问过自己这些问题,那么你对它的了解也仅仅也只是了解。那我们现在来说说什么是二叉树,二叉树就是一种数据结构, 它的组织关系就像是自然界中的树一样。官方语言的定义是:是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。至于为啥子要学习它,妈妈总是说,孩子,等你长大了就明白了。
二叉树的性质
性质1:二叉树第i层上的节点数目最多为2i-1(i≥1);
性质2:深度为k的二叉树至多有2k-1个结点(k≥1)。
性质3: 在任意-棵二叉树中,若叶子结点(即度为0的结点)的个数为n0,度为1的结点数为n1,度为2的结点数为n2,则no=n2+1。
二叉树的存储结构与构建
二叉树的存储方式有两种,一种顺序存储,比如:var binarytree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i'];
这就是一颗二叉树,假设binarytree[i]是二叉树的一个节点,那么它的左孩子节点 leftchild = binarytree[i*2+1]那么相应的右孩子节点 rightchild = binarytree[i*2+2]; 一般情况下顺序存储的这种结构用的较少,另外一种存储方式就是链式存储,下面我会用代码来详细描述二叉树式结构的构建与存储方式,构建二叉树也有两种方式一种是递归方式构建,这种很简单,另一种是非递归方法构建,这种呢相对于前一种复杂一点点,不过也不用担心,我在代码中加上详细的注释,一步一步的走下去。我们现在就以26个英文字母来构建二叉树
在构建二叉树之前我们会用到一个节点对象,节点对象如下:(注意:关于javascript的面向对象,原型,语法特点我会放在javascript语言知识点这个系列)
/* *二叉树的节点对象 */ function node() { this.text = ''; //节点的文本 this.leftchild = null; //节点的左孩子引用 this.rightchild = null; //节点右孩子引用 }
递归构建二叉树
在构建好二叉树节点之后我们紧接着用递归来构建二叉树
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']; function buildtree(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加入左孩子节点 buildtree(childnode, leftindex); //递归创建左孩子 } if(rightindex < charecters.length) { //下面注释参照上面的构建左孩子的节点 var childnode = new node(); childnode.text = charecters[rightindex]; node.rightchild = childnode; buildtree(childnode, rightindex); } } //下面构造二叉树 var node = new node(); node.text = charecters[0]; buildtree(node, 0); //索引i是从0开始构建
非递归构建二叉树
下面是以非递归方式构建二叉树:
var root; function createbinarytree() { var len = charecters.length, //数组的长度 index = 0, //索引从0开始 nodes = new array(); //创建一个临时数组,用于存放二叉树节点 //循环创建二叉树节点存放到数组中 for (var i = 0 ; i < charecters.length ; i++) { var node = new node(); node.text = charecters[i]; nodes.push(node); } //循环建立二叉树子节点的引用 while(index < len) { var leftindex = 2*index+1, //当前节点左孩子索引 rightindex = 2*index+2; //当前节点右孩子索引 //给当前节点添加左孩子 nodes[index].leftchild = nodes[leftindex]; //给当前节点添加右孩子 nodes[index].rightchild = nodes[rightindex]; index++; } root = nodes[0]; }
二叉树的三种遍历
好了,现在我们已经成功构建了二叉树的链式结构,在构建了二叉树的链式结构后我们进入二叉树的最基本的遍历了,遍历有三种最基本的遍历,我不说想必大家都知道,先序遍历,中序遍历和后续遍历。虽然这三种遍历递归方式都比较简单,但非递归方式就不是那么容易了,当时我在实现的时候都卡了半天,真的是说起来容易做起来难啊,在实现遍历前我们首先要来实现的是栈,因为在非递归遍历的时候会用到栈,那到底什么是栈呢,这里我就简单介绍下吧,有兴趣的朋友可以去*有权威的定义,栈和队列也是一种数据结构,栈存放数据的时候是先进先出,而队列是先进后出。
实现栈的对象
下面用javascript来实现栈的对象
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()之后元素出栈了,所以为空
1. 先序遍历
在实现了栈对象以后我们首先来进行先序遍历的递归方式
function firstiteration(node) { if(node.leftchild) { //判断当前节点是否有左孩子 firstiteration(node.leftchild); //递归左孩子 } if(node.rightchild) { //判断当前节点是否有右孩子 firstiteration(node.rightchild); //递归右孩子 } } //递归遍历二叉树 firstiteration(root);
先序遍历的非递归方式
上面的代码大家可以在firstiteration()方法中加个alert()函数来验证是否正确。那么下面就要说说先序遍历的非递归方式,遍历思想是这样的:先访问根节点在访问左节点, 最后访问右节点。从根节点一直往下访问找左孩子节点,直到最后一个左孩子节点(将这条路径保存到栈中),然后再访问最后一个左孩子的兄弟节点(右孩子节点),之后回溯到上一层(将栈中的元素取出 就是出栈),又开始从该节点(回溯到上一层的节点)一直往下访问找左孩子节点... 直到栈中的元素为空,循环结束。
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);
2. 中序遍历
只要把思路理清楚了现实起来其实还是挺容易的,只要我们熟悉了一种二叉树的非递归遍历方式,其他几种非递归方式就容易多了,照着葫芦画瓢,下面是中序遍历的递归方式,中序遍历的思想是:先访问左孩子节点,在访问根节点,最后访问右节点
var strtext = ""; function seconditeration(node) { //访问左节点 if(node.leftchild) { if(node.leftchild.leftchild) { seconditeration(node.leftchild); } else { strtext += node.leftchild.text; } } //访问根节点 strtext += node.text; //访问右节点 if(node.rightchild) { if(node.rightchild.leftchild) { seconditeration(node.rightchild); } else { strtext += node.rightchild.text; } } } seconditeration(root); alert(strtext);
中序遍历的非递归方式
思想是:1. 从根节点一直往下找左孩子节点,直到找到最后一个左孩子节点(用栈将此路径保存,但不访问)2.访问最后一个左孩子节点,然后再访问根节点(要先弹出栈,就是在栈中取上一层节点)3.在访问当前节点(最后一个左孩子节点)的兄弟节点(右孩子节点),这里要注意如果兄弟节点是一个叶节点就直接访问,否则是兄弟节点是一颗子树的话不能马*问,要先来重复 1, 2,3步骤, 直到栈为空,循环结束
function notseconditeration() { var resulttext = '', stack = new stack(), node = root; stack.push(node); while(!stack.isempty()) { //从根节点一直往下找左孩子节点直到最后一个左孩子节点,然后保存在栈中 while(node.leftchild) { node = node.leftchild; stack.push(node); } //弹出栈 var tempnode = stack.pop(); //访问临时节点 resulttext += tempnode.text; if(tempnode.rightchild) { node = tempnode.rightchild; stack.push(node); } } alert(resulttext); }
3. 后续遍历
最后就还剩下一种遍历方式,二叉树的后续遍历,后续遍历的思想是:先访问左孩子节点,然后在访问右孩子节点,最后访问根节点
后续遍历的递归方式
var strtext = ''; function lastiteration(node) { //首先访问左孩子节点 if(node.leftchild) { if(node.leftchild.leftchild) { lastiteration(node.leftchild); } else { strtext += node.leftchild.text; } } //然后再访问右孩子节点 if(node.rightchild) { if(node.rightchild.rightchild) { lastiteration(node.rightchild); } else { strtext += node.rightchild.text; } } //最后访问根节点 strtext += node.text; } //中序递归遍历 lastiteration(root); alert(strtext);
后续非递归遍历
后续非递归遍历的思想是:1.从根节点一直往下找左孩子节点,直到最后一个左孩子节点(将路径保存到栈中,但不访问)2.弹出栈访问最后一个左孩子节点 3.进入最后一个左孩子节点的兄弟节点,如果兄弟节点是叶节点就访问它,否则将该节点重复 1, 2步骤, 直到栈中的元素为空,循环结束。3.访问根节点
function notlastiteration() { var strtext = '', stack = new stack(); nodo = root; stack.push(node); while(!stack.isempty()) { while(node.leftchild) { node = node.leftchild; stack.push(node); } //弹出栈 var tempnode = stack.pop(); //访问左孩子节点 strtext += tempnode.text; //访问右孩子节点 if(tempnode.rightchild) { if(tempnode.rightchild.leftchild || tempnode.rightchild.rightchild) { //判断最后一个左孩子节点的兄弟节点是否为页节点 stack.push(tempnode.rightchild); } else { strtext += tempnode.rightchild.text; } } } alert(strtext); }
更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数据结构与算法技巧总结》、《javascript数学运算用法总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
推荐阅读
-
Python实现二叉树结构与进行二叉树遍历的方法详解
-
JavaScript实现二叉树定义、遍历及查找的方法详解
-
JavaScript实现二叉树的先序、中序及后序遍历方法详解
-
JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】
-
JavaScript定义及输出螺旋矩阵的方法详解
-
Python定义二叉树及4种遍历方法实例详解
-
PHP实现的线索二叉树及二叉树遍历方法详解,二叉树详解
-
PHP实现的线索二叉树及二叉树遍历方法详解 线索化二叉树 前序线索化二叉树 先序线索化二叉
-
PHP实现的线索二叉树及二叉树遍历方法详解 线索化二叉树 前序线索化二叉树 先序线索化二叉
-
AngularJS实现自定义指令及指令配置项的方法详解