每个人都必须熟悉数据结构“树”。今天，我们将回顾数据结构中的二叉树和树，并用JavaScript实现它们。

ps:的树形结构在很多地方都有体现，比如Vue的虚拟DOM和冒泡。

二叉树

-概念-

二叉树是一种树形结构，其特点是每个节点最多只有两个子树(即二叉树中没有度大于2的节点)，二叉树的子树有左右两个分支，它们的顺序不能任意颠倒。

如下，它是一个二叉树(注：以下二叉树的例子以这个二叉树为例):

此外，有三种常见的遍历二叉树的方法，如下所示：

1)首先遍历二叉树(围绕根)

如果二叉树为空，则为空；否则

-访问根节点；

-先遍历左边的子树；

-首先遍历右子树。

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

2)以中间顺序遍历二叉树(左根和右根)

如果二叉树为空，则为空；否则

-以中间顺序遍历左边的子树；

-访问根节点；

-以中间顺序遍历右子树。

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

3)依次遍历二叉树(左右根)

如果二叉树为空，则为空；否则

-按顺序遍历左边的子树；

-按顺序遍历右子树；

-访问根节点。

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

好了，我们知道了二叉树和遍历方法，那么我们就用JavaScrip一起实现吧，当然是用链式存储结构。

首先，使用JavaScript构造函数建立二叉树节点，如下所示：

函数TreeNode(){ this . data=null；//节点数据this.lchild=null//左子树this.rchild=null//右子树}；然后，我们可以通过遍历二叉树的算法来构建二叉树，如下，利用优先顺序构建二叉树的方法如下：

/**method:使用优先顺序构建二叉树* @ params 3360 modelist(array)-树节点，这些节点按照优先顺序存储在数组中，null表示空节点*/tree node . createbitree=function(nodelist){ var I=0；return(函数getNode(){ var node=null，val=nodeList[I]；if(！val){ node=null；} else { node=new TreeNode()；node.data=valnode . lchild=GetNode()；node . archild=GetNode()；}返回节点；})();};最后，遍历二叉树，包括前序遍历、中序遍历和后序遍历，如下所示：

tree node . prototype={ constructor : tree node，_PreOrderTraverse:函数(node){ if(node){ console . log(node . data)；这个。_ PreOrderTraverse(node . lchild)；这个。_ PreOrderTraverse(node . archild)；} }，PreOrderTraverse:函数(){ console . log(' preorder : ')；这个。_PreOrderTraverse(此)；}，_ InOrderTraverse:函数(节点){ if(节点){ this。_ InordTraverse(node . lchild)；console . log(node . data)；这个。_ inodertraverse(node . archild)；} }，InOrderTraverse:函数(){ console . log(' inoder: ')；这个。_ InOrderTraverse(此)；}，_PostOrderTraverse:函数(节点){ if(节点){ this。_ PostOrderTraverse(node . lchild)；这个。_ PostOrderTraverse(node . archild)；console . log(node . data)；} }，PostOrderTraverse:函数(){ console . log(' PostOrder : ')；这个。_PostOrderTraverse(此)；}};好了，使用上面的二叉树例子，我们可以自己测试一下：

var treeNode=null，nodeList=['A '，' B '，' C '，null，null，' D '，' E '，null，' G '，null，null，' F '，null，null，null，null]；//从nodeListtreeNode=treenode . createbitree(nodeList)获取二叉树；//遍历treeNodetreeNode的树。PreOrderTraverse//ABCDEGFtreeNode。inodertraverse()；//CBEGDFAtreeNode。posterordtraverse()；//CGEFDBA树

-概念-

树是n(n=0)个节点的有限集合。在任何非空树中，只有一个称为根的特定节点。当n1时，其他节点可以划分为m(m0)个不相交的有限集合，每个集合本身就是一棵树，称为根的子树。当然，二叉树必须属于树。

如下，它是一棵树(注：以下树的相关示例以此树为例):

此外，有两种常用的方法来遍历多子树，如下所示：

1)第一根遍历类似于Depth_First Search遍历。堆栈用于遍历元素，如下所示：

2)层次遍历类似于广度优先搜索遍历。它们都使用队列来遍历元素，如下所示：

好了，在了解了树和遍历方法之后，让我们一起使用JavaScrip来实现它，当然，我们也使用了链式存储结构。

首先，使用JavaScript建立树节点，如下所示：

/* * @ params 3360 data-node数据子节点-所有子节点*/function treenode(数据，子节点){if(！(TreeNode的这个实例){返回新的TreeNode(数据，子节点)；} this.data=data | | nullthis . children=children | |[]；};根据上面的TreeNode构造函数，我们可以将示例中的树表达如下：

var treeNode=TreeNode('A '，[ TreeNode('B '，[TreeNode('E')])、TreeNode('C ')、tree node(' D ')])；然后，编写遍历树的方法，这是第一次根遍历和层次遍历，如下所示：

树节点。prototype={ constructor : tree node，_ traverse asdfs:函数(node){//first traverse var self=this；if(node){ console . log(node . data)；node . children . foreach(function(child){ if(child . children . length){ self。_traverseAsDFS(子级)；} else { console . log(child . data)；} });} }，traverseAsDFS:函数(){ console . log(' Depth _ First Search ')；这个。_traverseAsDFS(此)；}，traversasbfs : function(){//travers var queue=[]分层；console . log(' width _ 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 ')、tree node(' D ')])；treenode . traverseasdfs()；//abecdtreenode . traverseasbfs()；//ABCDE有关上述所有代码，请参见github。

以上就是本文的全部内容。希望本文的内容能给大家的学习或工作带来一些帮助，也希望多多支持我们！