本文实例讲述了JavaScript实现二叉树定义,遍历及查找的方法。分享给大家供大家参考,具体如下:
在写这篇文章之前说一下数据结构和算法这个系列,这个系列包含了很多东西,比如啥子排序,线性表,广义表,树,图这些大家都是知道的,但是这些东西我们学了之后工作中能用到的又有多少呢,据我所知绝大部分公司,一线码农,屌丝,程序猿是用不到这些东西,既然这样为啥子我还要强调这个系列呢,本人觉得算法和数据结构是程序的基本功,前提想脱离一线码农,普通程序猿行列,说得通俗一点就是让自己变的更牛逼。其次语言都是想通的,只要是掌握了一门语言学习其他语言就如同顺水推舟,不费一点力气。另外还有一点就是我会一直把这个系列写下去,虽然网上一搜一大筐,已经写烂了,但是我写作的目的有两个,第一和大家分享,第二可以让自己更深入的理解。好了,其他的不多说了,最近复习了一下二叉树,就先写这个,后面会依次的加上排序,线性表,广义表....等等
<强>二叉树
一说到二叉树我们肯定会问,什么是二叉树,二叉树是个啥子东东,拿来有啥子用嘛,我们为啥子要学习它嘛?如果当初你在学习二叉树的时候你没有问过自己这些问题,那么你对它的了解也仅仅也只是了解。那我们现在来说说什么是二叉树,二叉树就是一种数据结构,它的组织关系就像是自然界中的树一样。官方语言的定义是:是一个有限元素的集合,该集合或者为空,或者由一个称为根的元素及两个不相交的,被分别称为左子树和右子树的二叉树组成。至于为啥子要学习它,妈妈总是说,孩子,等你长大了就明白了。
<强>二叉树的性质
性质1:二叉树第我层上的节点数目最多为2张(≥1);
性质2:深度为k的二叉树至多有2 k - 1个结点(k≥1)。
性质3:在任意-棵二叉树中,若叶子结点(即度为0的结点)的个数为n0,度为1的结点数为n1,度为2的结点数为n2,则没有=n2 + 1。
<强>二叉树的存储结构与构建
二叉树的存储方式有两种,一种顺序存储,比如:
<代码> var binaryTree=[a, b, c, d, e, f,“h”,“我”);这就是一颗二叉树,假设binaryTree[我]是二叉树的一个节点,那么它的左孩子节点leftChild=binaryTree[我* 2 + 1]那么相应的右孩子节点rightChild=binaryTree[我* 2 + 2];一般情况下顺序存储的这种结构用的较少,另外一种存储方式就是链式存储、下面我会用代码来详细描述二叉树式结构的构建与存储方式,构建二叉树也有两种方式一种是递归方式构建,这种很简单,另一种是非递归方法构建,这种呢相对于前一种复杂一点点,不过也不用担心,我在代码中加上详细的注释,一步一步的走下去。我们现在就以26个英文字母来构建二叉树
代码如下:var合=[A, B, C, D, E, F, G, H,‘我’,‘J’,‘K’,‘L’,‘米’,‘N’,‘O’,‘P’,‘问’,‘R’,‘S’,‘T’,‘你’,‘V’,‘W’,‘X’, ' Y ', ' Z '],
在构建二叉树之前我们会用到一个节点对象,节点对象如下:(注意:关于javascript的面向对象,原型,语法特点我会放在javascript语言知识点这个系列)
在构建好二叉树节点之后我们紧接着用递归来构建二叉树
