树结构之JavaScript

2017-01-09 07:55:20来源:作者:人点击

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

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

二叉树
--概念--

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

如下,就是一棵二叉树(注:下文二叉树相关例子,都以该二叉树为例):

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();//ABECDtreeNode.traverseAsBFS();//ABCDE


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

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台