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个英文字母来构建二叉树
复制代码 代码如下:

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。