這篇文章主要介紹了JavaScript之樹(shù)結(jié)構(gòu)的示例分析，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專(zhuān)注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、微信小程序、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶(hù)創(chuàng)新互聯(lián)還提供了阿瓦提免費(fèi)建站歡迎大家使用！

二叉樹(shù)

--概念--

二叉樹(shù)是一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。

如下，就是一棵二叉樹(shù)（注：下文二叉樹(shù)相關(guān)例子，都以該二叉樹(shù)為例）：

且，遍歷二叉樹(shù)（traversing binary tree）有三種常用方式，如下：

1）、先序遍歷二叉樹(shù) （根左右）  

        若二叉樹(shù)為空，則空操作；否則

        --訪問(wèn)根結(jié)點(diǎn)；

        --先序遍歷左子樹(shù)；

        --先序遍歷右子樹(shù)。

例如，上述例子中的二叉樹(shù)，遍歷結(jié)果如下：

2）、中序遍歷二叉樹(shù)（左根右）

         若二叉樹(shù)為空，則空操作；否則

         --中序遍歷左子樹(shù)；

         --訪問(wèn)根結(jié)點(diǎn)；

         --中序遍歷右子樹(shù)。

例如，上述例子中的二叉樹(shù)，遍歷結(jié)果如下：

3）、后序遍歷二叉樹(shù)（左右根）

        若二叉樹(shù)為空，則空操作；否則

        --后序遍歷左子樹(shù)；

        --后序遍歷右子樹(shù)；

--訪問(wèn)根結(jié)點(diǎn)。

例如，上述例子中的二叉樹(shù)，遍歷結(jié)果如下：

好了，了解了二叉樹(shù)以及遍歷方式，那么，接下來(lái)我們就一起用JavaScrip來(lái)實(shí)現(xiàn)下吧，當(dāng)然采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

首先，利用JavaScript構(gòu)造函數(shù)建立二叉樹(shù)結(jié)點(diǎn)，如下：

function TreeNode(){
 this.data = null;//該節(jié)點(diǎn)數(shù)據(jù)
 this.lchild = null;//左子樹(shù)
 this.rchild = null;//右子樹(shù) 
};

然后，我們可以通過(guò)遍歷二叉樹(shù)的算法，構(gòu)建一棵二叉樹(shù)，如下，采用先序序列建立一棵二叉樹(shù)方法：

/*
*method:采用先序序列建立二叉樹(shù)
*@params: nodeList（Array） --樹(shù)節(jié)點(diǎn)，以先序序列存入數(shù)組中，null代表空節(jié)點(diǎn)
*/
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;
 })();
};

最后，就是遍歷一棵二叉樹(shù)咯，分別為先序遍歷（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);
 }
};

好了，利用上述二叉樹(shù)例子，我們可以自行測(cè)試下：

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

樹(shù)

--概念--

樹(shù)是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中，有且僅有一個(gè)特定的稱(chēng)為根（root）的結(jié)點(diǎn)，當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集，其中每個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)。當(dāng)然，二叉樹(shù)肯定屬于樹(shù)咯。

如下，就是一棵樹(shù)（注：下文樹(shù)的相關(guān)例子，都以該樹(shù)為例）：

且，遍歷一棵多孩子樹(shù)，有兩種常用遍歷方式，如下：

1) 、先根遍歷，和深度優(yōu)先搜索（Depth_First Search）遍歷類(lèi)似。都是利用棧來(lái)遍歷元素，如下：

2) 、按層次遍歷，和廣度優(yōu)先搜索（Breadth_First Search）遍歷類(lèi)似。都是利用隊(duì)列來(lái)遍歷元素，如下：

好了，了解了樹(shù)以及遍歷方式，那么，接下來(lái)我們就一起用JavaScrip來(lái)實(shí)現(xiàn)下吧，當(dāng)然也是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

首先，利用JavaScript建立樹(shù)結(jié)點(diǎn)，如下：

/*
*@Params: data --節(jié)點(diǎn)數(shù)據(jù)
 children -- 所有孩子結(jié)點(diǎn)
*/
function TreeNode(data, children){
 if(!(this instanceof TreeNode)){
 return new TreeNode(data, children); 
 }
 this.data = data || null;
 this.children = children || [];
};

根據(jù)上述TreeNode構(gòu)造函數(shù)，我們可以將例子中的樹(shù)，表示如下：

var treeNode = TreeNode('A', [
 TreeNode('B', [TreeNode('E')]),
 TreeNode('C'),
 TreeNode('D')
 ]);

接著，就是編寫(xiě)遍歷樹(shù)方法咯，分別為先根遍歷和按層次遍歷，如下：

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);
 } 
 });
 }
 }
};

好了，利用上述二叉樹(shù)例子，我們可以自行測(cè)試下：

var treeNode = TreeNode('A', [
 TreeNode('B', [TreeNode('E')]),
 TreeNode('C'),
 TreeNode('D')
 ]);
treeNode.traverseAsDFS();//ABECD
treeNode.traverseAsBFS();//ABCDE

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“JavaScript之樹(shù)結(jié)構(gòu)的示例分析”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!

文章題目：JavaScript之樹(shù)結(jié)構(gòu)的示例分析
本文路徑：http://chinadenli.net/article20/giosjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開(kāi)發(fā)、網(wǎng)站內(nèi)鏈、ChatGPT、面包屑導(dǎo)航、微信公眾號(hào)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)