對於資料結構“樹”，想必大家都熟悉，今兒，我們就再來回顧一下資料結構中的二元樹與樹，並用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;
})();
};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）個互不相交的有限集，其中每個集合本身又是一棵樹，稱為根的子樹。當然，二元樹肯定屬於樹咯。 如下，就是一棵樹（註：下文樹的相關例子，都以此樹為例）：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。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持脚本之家PHP中文网
更多詳解JavaScript樹結構相关文章请关注PHP中文网！
