這篇文章主要為大家展示了“如何使用JavaScript實現(xiàn)樹結(jié)構(gòu)”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“如何使用JavaScript實現(xiàn)樹結(jié)構(gòu)”這篇文章吧。

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設,龍沙企業(yè)網(wǎng)站建設,龍沙品牌網(wǎng)站建設,網(wǎng)站定制,龍沙網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,龍沙網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

對于數(shù)據(jù)結(jié)構(gòu)“樹”，想必大家都熟悉，今兒，我們就再來回顧一下數(shù)據(jù)結(jié)構(gòu)中的二叉樹與樹，并用JavaScript實現(xiàn)它們。

ps:樹結(jié)構(gòu)在前端中，很多地方體現(xiàn)得淋漓盡致，如Vue的虛擬DOM以及冒泡等等。

二叉樹

--概念--

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

如下，就是一棵二叉樹（注：下文二叉樹相關例子，都以該二叉樹為例）：

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

1）、先序遍歷二叉樹 （根左右）  

        若二叉樹為空，則空操作；否則

        --訪問根結(jié)點；

        --先序遍歷左子樹；

        --先序遍歷右子樹。

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

2）、中序遍歷二叉樹（左根右）

         若二叉樹為空，則空操作；否則

         --中序遍歷左子樹；

         --訪問根結(jié)點；

         --中序遍歷右子樹。

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

3）、后序遍歷二叉樹（左右根）

        若二叉樹為空，則空操作；否則

        --后序遍歷左子樹；

        --后序遍歷右子樹；

--訪問根結(jié)點。

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

好了，了解了二叉樹以及遍歷方式，那么，接下來我們就一起用JavaScrip來實現(xiàn)下吧，當然采用鏈式存儲結(jié)構(gòu)。

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

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

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

/*
*method:采用先序序列建立二叉樹
*@params: nodeList（Array） --樹節(jié)點，以先序序列存入數(shù)組中，null代表空節(jié)點
*/
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 nodeList
treeNode = TreeNode.createBiTree(nodeList); 
//traversing the tree of treeNode
treeNode.PreOrderTraverse();//ABCDEGF
treeNode.InOrderTraverse();//CBEGDFA
treeNode.PostOrderTraverse();//CGEFDBA

樹

--概念--

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

如下，就是一棵樹（注：下文樹的相關例子，都以該樹為例）：

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

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

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

好了，了解了樹以及遍歷方式，那么，接下來我們就一起用JavaScrip來實現(xiàn)下吧，當然也是采用鏈式存儲結(jié)構(gòu)。

首先，利用JavaScript建立樹結(jié)點，如下：

/*
*@Params: data --節(jié)點數(shù)據(jù)
   children -- 所有孩子結(jié)點
*/
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ù)，我們可以將例子中的樹，表示如下：

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

以上是“如何使用JavaScript實現(xiàn)樹結(jié)構(gòu)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

文章名稱：如何使用JavaScript實現(xiàn)樹結(jié)構(gòu)
文章網(wǎng)址：http://chinadenli.net/article22/ppdsjc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、服務器托管、網(wǎng)站策劃、企業(yè)網(wǎng)站制作、手機網(wǎng)站建設、動態(tài)網(wǎng)站

廣告

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