JavaScript
发布时间:2022-04-16 发布网站:大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了详解JavaScript树结构,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
对于数据结构“树”,想必大家都熟悉,今儿,我们就再来回顾一下数据结构中的二叉树与树,并用JavaScript实现它们。
ps:树结构在前端中,很多地方体现得淋漓尽致,如Vue的虚拟DOM以及冒泡等等。
二叉树
--概念--
二叉树是一种树形结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
如下,就是一棵二叉树(注:下文二叉树相关例子,都以该二叉树为例):
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854501.png)
且,遍历二叉树(traversing binary tree)有三种常用方式,如下:
1)、先序遍历二叉树 (根左右)
若二叉树为空,则空操作;否则
--访问根结点;
--先序遍历左子树;
--先序遍历右子树。
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854502.png)
2)、中序遍历二叉树(左根右)
若二叉树为空,则空操作;否则
--中序遍历左子树;
--访问根结点;
--中序遍历右子树。
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854513.png)
3)、后序遍历二叉树(左右根)
若二叉树为空,则空操作;否则
--后序遍历左子树;
--后序遍历右子树;
--访问根结点。
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854514.png)
好了,了解了二叉树以及遍历方式,那么,接下来我们就一起用JavaScrip来实现下吧,当然采用链式存储结构。
首先
,利用JavaScript构造函数建立二叉树结点,如下:
{
thi
s.data = null;//该节点数据
thi
s.lchild = null;//左子树
thi
s.rchild = null;//右子树
};
然后
,我们可以通过遍历二叉树的算法,构建一棵二叉树,如下,采用先序序列建立一棵二叉树方法:
{
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),如下:
{
constructor: TreeNode,_PreOrderTraverse: function(nod
E){
if(nod
E){
console.log(node.data
);
thi
s._PreOrderTraverse(node.lchild
);
thi
s._PreOrderTraverse(node.rchild
);
}
},PreOrderTraverse: function()
{
console.log('PreOrder:'
);
thi
s._PreOrderTraverse(this
);
},_InOrderTraverse: function(nod
E){
if(nod
E){
thi
s._InOrderTraverse(node.lchild
);
console.log(node.data
);
thi
s._InOrderTraverse(node.rchild
);
}
},InOrderTraverse: function()
{
console.log('InOrder:'
);
thi
s._InOrderTraverse(this
);
},_PostOrderTraverse: function(nod
E){
if(nod
E){
thi
s._PostOrderTraverse(node.lchild
);
thi
s._PostOrderTraverse(node.rchild
);
console.log(node.data
);
}
},PostOrderTraverse: function()
{
console.log('PostOrder:'
);
thi
s._PostOrderTraverse(this
);
}
};
好了,利用上述二叉树例子,我们可以自行测试下:
Ting 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)个互不相交的有限集,其中每个集合本身又是一棵树,称为根的子树。当然,二叉树肯定属于树咯。
如下,就是一棵树(注:下文树的相关例子,都以该树为例):
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854517.png)
且,遍历一棵多孩子树,有两种常用遍历方式,如下:
1) 、先根遍历
,和深度优先搜索(Depth_First Search)遍历类似。都是利用栈来遍历元素,如下:
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854518.png)
2) 、按层次遍历
,和广度优先搜索(Breadth_First Search)遍历类似。都是利用队列来遍历元素,如下:
![详解JavaScript树结构 详解JavaScript树结构](https://files.jb51.cc/file_images/article/201701/201701090854519.png)
好了,了解了树以及遍历方式,那么,接下来我们就一起用JavaScrip来实现下吧,当然也是采用链式存储结构。
首先,利用JavaScript建立树结点,如下:
{
if(!(this instanceof TreeNod
E))
{
return new TreeNode(data,children
);
}
thi
s.data = data || null;
thi
s.children = children || [];
};
根据上述TreeNode构造函数,我们可以将例子中的树,表示如下:
);
接着,就是编写遍历树方法咯,分别为先根遍历和按层次遍历,如下:
{
constructor: TreeNode,_traverseAsDFS: function(nod
E){//先根遍历
var self = this;
if(nod
E){
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'
);
thi
s._traverseAsDFS(this
);
},traverseAsBFS: function()
{//按层次遍历
var queue = [];
console.log('Breadth_First Search'
);
console.log(thi
s.data
);
if(thi
s.children.length)
{
queue.push(this
);
}
while(queue.length)
{
let t
empnode = queue.shift(
);
t
empnode.children.forEach(function(child)
{
console.log(child.data
);
if(child.children.length)
{
queue.push(child
);
}
}
);
}
}
};
好了,利用上述二叉树例子,我们可以自行测试下:
);
treeNode.traverseAsDFS(
);//ABECD
treeNode.traverseAsBFS(
);//ABCDE
关于上述全部代码,见https://github.com/jajk/JavaScript2Tree">github@H_944_167@。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持菜鸟教程!
大佬总结
以上是大佬教程为你收集整理的详解JavaScript树结构全部内容,希望文章能够帮你解决详解JavaScript树结构所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。