树结构之JavaScript

对于数据结构“树”，想必大家都熟悉，今儿，我们就再来回顾一下数据结构中的二叉树与树，并用JavaScript实现它们。

ps:树结构在前端中，很多地方体现得淋漓尽致，如Vue的虚拟DOM以及冒泡等等。

二叉树

--概念--

二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

如下，就是一棵二叉树（注：下文二叉树相关例子，都以该二叉树为例）：

且，遍历二叉树（traversing binary tree）有三种常用方式，如下：

1）、先序遍历二叉树 （根左右）  

        若二叉树为空，则空操作；否则

        --访问根结点；

        --先序遍历左子树；

        --先序遍历右子树。

例如，上述例子中的二叉树，遍历结果如下：

2）、中序遍历二叉树（左根右）

         若二叉树为空，则空操作；否则

         --中序遍历左子树；

         --访问根结点；

         --中序遍历右子树。

例如，上述例子中的二叉树，遍历结果如下：

3）、后序遍历二叉树（左右根）

        若二叉树为空，则空操作；否则

        --后序遍历左子树；

        --后序遍历右子树；

--访问根结点。

例如，上述例子中的二叉树，遍历结果如下：

好了，了解了二叉树以及遍历方式，那么，接下来我们就一起用JavaScrip来实现下吧，当然采用链式存储结构。

首先，利用JavaScript构造函数建立二叉树结点，如下：

function TreeNode(){
 this.data = null;//该节点数据
 this.lchild = null;//左子树
 this.rchild = null;//右子树 
};

然后，我们可以通过遍历二叉树的算法，构建一棵二叉树，如下，采用先序序列建立一棵二叉树方法：

/*
*method:采用先序序列建立二叉树
*@params: nodeList（Array） --树节点，以先序序列存入数组中，null代表空节点
*/
TreeNode.createBiTree = function(nodeList){
 var i = 0;
 return (function getNode(){
 var node = null,
 val = nodeList[i++];
 if(!val){
 node = null;
 }else{
 node = new TreeNode();
 node.data = val;
 node.lchild = getNode();
 node.rchild = getNode();
 }
 return node;
 })();
};

最后，就是遍历一棵二叉树咯，分别为先序遍历（PreOrderTraverse）、中序遍历（InOrderTraverse）以及后序遍历（PostOrderTraverse），如下：

TreeNode.prototype = {
 constructor: TreeNode,
 _PreOrderTraverse: function(node){
 if(node){
 console.log(node.data);
 this._PreOrderTraverse(node.lchild);
 this._PreOrderTraverse(node.rchild);
 }
 },
 PreOrderTraverse: function(){
 console.log('PreOrder:');
 this._PreOrderTraverse(this);
 },
 _InOrderTraverse: function(node){
 if(node){
 this._InOrderTraverse(node.lchild);
 console.log(node.data);
 this._InOrderTraverse(node.rchild);
 }
 },
 InOrderTraverse: function(){
 console.log('InOrder:');
 this._InOrderTraverse(this);
 },
 _PostOrderTraverse: function(node){
 if(node){
 this._PostOrderTraverse(node.lchild);
 this._PostOrderTraverse(node.rchild);
 console.log(node.data);
 }
 },
 PostOrderTraverse: function(){
 console.log('PostOrder:');
 this._PostOrderTraverse(this);
 }
};

好了，利用上述二叉树例子，我们可以自行测试下：

var treeNode = null,
 nodeList = ['A', 'B', 'C', null, null, 'D', 'E', null, 'G', null, null, 'F', null, null, null];
//getting a binary tree from nodeList
treeNode = TreeNode.createBiTree(nodeList); 
//traversing the tree of treeNode
treeNode.PreOrderTraverse();//ABCDEGF
treeNode.InOrderTraverse();//CBEGDFA
treeNode.PostOrderTraverse();//CGEFDBA

树

--概念--

树是n（n>=0）个结点的有限集。在任意一棵非空树中，有且仅有一个特定的称为根（root）的结点，当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每个集合本身又是一棵树，称为根的子树。当然，二叉树肯定属于树咯。

如下，就是一棵树（注：下文树的相关例子，都以该树为例）：

且，遍历一棵多孩子树，有两种常用遍历方式，如下：

1) 、先根遍历，和深度优先搜索（Depth_First Search）遍历类似。都是利用栈来遍历元素，如下：

2) 、按层次遍历，和广度优先搜索（Breadth_First Search）遍历类似。都是利用队列来遍历元素，如下：

好了，了解了树以及遍历方式，那么，接下来我们就一起用JavaScrip来实现下吧，当然也是采用链式存储结构。

首先，利用JavaScript建立树结点，如下：

/*
*@Params: data --节点数据
 children -- 所有孩子结点
*/
function TreeNode(data, children){
 if(!(this instanceof TreeNode)){
 return new TreeNode(data, children); 
 }
 this.data = data || null;
 this.children = children || [];
};

根据上述TreeNode构造函数，我们可以将例子中的树，表示如下：

var treeNode = TreeNode('A', [
 TreeNode('B', [TreeNode('E')]),
 TreeNode('C'),
 TreeNode('D')
 ]);

接着，就是编写遍历树方法咯，分别为先根遍历和按层次遍历，如下：

TreeNode.prototype = {
 constructor: TreeNode,
 _traverseAsDFS: function(node){//先根遍历
 var self = this;
 if(node){
 console.log(node.data);
 node.children.forEach(function(child){
 if(child.children.length){
 self._traverseAsDFS(child);
 }else{
 console.log(child.data);
 }
 });
 } 
 },
 traverseAsDFS: function(){
 console.log('Depth_First Search');
 this._traverseAsDFS(this); 
 },
 traverseAsBFS: function(){//按层次遍历
 var queue = [];
 console.log('Breadth_First Search');
 console.log(this.data);
 if(this.children.length){
 queue.push(this);
 }
 while(queue.length){
 let tempNode = queue.shift();
 tempNode.children.forEach(function(child){
 console.log(child.data);
 if(child.children.length){
 queue.push(child);
 } 
 });
 }
 }
};

好了，利用上述二叉树例子，我们可以自行测试下：

var treeNode = TreeNode('A', [
 TreeNode('B', [TreeNode('E')]),
 TreeNode('C'),
 TreeNode('D')
 ]);
treeNode.traverseAsDFS();//ABECD
treeNode.traverseAsBFS();//ABCDE

关于上述全部代码，见github。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持！

# javascript  # 树结构  # 树形结构  # JavaScript几种形式的树结构菜单  # 详解JavaScript树结构  # JAVA使用geotools读取shape格式文件的方法  # java后端把数据转换为树  # map递归生成json树  # 返回给前端(后台转换)  # js中递归函数的使用介绍  # Vue.js 递归组件实现树形菜单（实例分享）  # JavaScript的递归之递归与循环示例介绍  # JS遍历数组和对象的区别及递归遍历对象、数组、属性的方法详解  # JS中递归函数  # 优雅的使用javascript递归画一棵结构树示例代码  # 遍历  # 子树  # 二叉树  # 一棵  # 好了  # 我们可以  # 链式  # 都是  # 为空  # 数据结构  # 为例  # 来实现  # 一棵树  # 为先  # 下吧  # 以该  # 是一种  # 又是  # 大家都  # 再来 

相关文章： 如何在宝塔面板中创建新站点？  如何解决ASP生成WAP建站中文乱码问题？  如何在局域网内绑定自建网站域名？  如何在云主机上快速搭建多站点网站？  建站中国官网：模板定制+SEO优化+建站流程一站式指南  如何通过FTP空间快速搭建安全高效网站？  如何使用Golang table-driven基准测试_多组数据测量函数效率  如何用景安虚拟主机手机版绑定域名建站？  建站主机选购指南：核心配置与性价比推荐解析  导航网站建站方案与优化指南：一站式高效搭建技巧解析  如何基于云服务器快速搭建个人网站？  建站之星后台管理：高效配置与模板优化提升用户体验  如何用VPS主机快速搭建个人网站？  活动邀请函制作网站有哪些,活动邀请函文案？  如何在搬瓦工VPS快速搭建网站？  已有域名如何免费搭建网站？  建站之星伪静态规则如何正确配置？  如何快速搭建高效香港服务器网站？  如何在IIS中新建站点并配置端口与IP地址？  Python多线程使用规范_线程安全解析【教程】  C++如何编写函数模板？（泛型编程入门）  建站之星安装后如何自定义网站颜色与字体？  如何通过建站之星自助学习解决操作问题？  安云自助建站系统如何快速提升SEO排名？  小自动建站系统：AI智能生成+拖拽模板，多端适配一键搭建  沈阳制作网站公司排名,沈阳装饰协会官方网站？  ,怎么用自己头像做动态表情包？  如何快速搭建二级域名独立网站？  如何通过IIS搭建网站并配置访问权限？  大学网站设计制作软件有哪些,如何将网站制作成自己app？  非常酷的网站设计制作软件,酷培ai教育官方网站？  家庭建站与云服务器建站，如何选择更优？  如何在腾讯云服务器上快速搭建个人网站？  如何在IIS中新建站点并解决端口绑定冲突？  如何用PHP快速搭建CMS系统？  如何在景安服务器上快速搭建个人网站？  邀请函制作网站有哪些,有没有做年会邀请函的网站啊？在线制作，模板很多的那种？  建站之星展会模板：智能建站与自助搭建高效解决方案  实例解析angularjs的filter过滤器  开源网站制作软件,开源网站什么意思？  公司网站制作费用多少,为公司建立一个网站需要哪些费用？  ,如何利用word制作宣传手册？  建站上市公司网站建设方案与SEO优化服务定制指南  建站之星代理费用多少？最新价格详情介绍  山东云建站价格为何差异显著？  建站主机服务器选型指南与性能优化方案解析  淘宝制作网站有哪些,淘宝网官网主页？  如何选择香港主机高效搭建外贸独立站？  如何在Golang中引入测试模块_Golang测试包导入与使用实践  如何通过西部数码建站助手快速创建专业网站？