對于數據結構“樹”，想必大家都熟悉，今兒，我們就再來回顧一下數據結構中的二叉樹與樹，并用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 nodeListtreeNode = TreeNode.createBiTree(nodeList); //traversing the tree of treeNodetreeNode.PreOrderTraverse();//ABCDEGFtreeNode.InOrderTraverse();//CBEGDFAtreeNode.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();//ABECDtreeNode.traverseAsBFS();//ABCDE關于上述全部代碼，見github。
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持武林網！
新聞熱點
疑難解答
