JavaScriptのツリー構造の詳しい説明

今日はデータ構造のバイナリツリーとツリーを復習し、JavaScriptで実装します。

追記: ツリー構造は、Vue の仮想 DOM やバブリングなど、フロントエンドのさまざまな場所に鮮明に反映されています。

二分木

--概念--

二分木は、各ノードが最大 2 つの部分木を持つこと (つまり、二分木には次数 2 を超えるノードが存在しない) である木構造です。そして、二分木 の部分木は左右の部分木に分けることができ、その順序を任意に逆転することはできません。

以下はバイナリ ツリーです (注: 以下のバイナリ ツリーの例はすべてこのバイナリ ツリーに基づいています):

そして、バイナリ ツリーをトラバースする (トラバース バイナリ ツリー) には 3 つの一般的な方法があります。

1)、バイナリ ツリーの事前順序トラバース (ルートの左右)

バイナリ ツリーが空の場合、それ以外の場合は操作は行われません

使う 一緒に使う 使う 使う ‐‐‐ ‐‐‐‐‐ ‐‐‐ 左のサブツリーの順にトラバースします。 ‐‐ ‐ ‐ ‐ ‐ ‐

をトラバースします。たとえば、上の例のバイナリ ツリーは次のように結果をトラバースします:

2)、および中程度の順次トラバース (左ルートと右)

バイナリ ツリーが空の場合は動作します。左のサブツリー

ルートノードにアクセスします。たとえば、上の例のバイナリ ツリーは次のように結果をトラバースします。 ;

—右サブツリーの事後走査。

—ルートノードにアクセスします。

たとえば、上記の例のバイナリ ツリーのトラバーサル結果は次のとおりです:

さて、バイナリ ツリーとトラバーサル メソッドを理解したので、JavaScript を使用してそれを一緒に実装しましょう。連鎖ストレージ構造。

まず、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);
 }
};

Tree

--概念--

ツリーは、n (n>=0) 個のノードの有限集合です。空ではないツリーには、ルートと呼ばれる特定のノードが 1 つだけ存在します。n>1 の場合、残りのノードは互いに素な m (m>0) 個の有限ノード セットに分割できます。各ノードはそれ自体 1 つです。ルートのサブツリーと呼ばれるツリー。もちろん、二分木は間違いなく木に属します。

以下はツリーです (注: 以下のツリー関連の例はすべてこのツリーに基づいています):

そして、複数の子ツリーを走査するには、次の 2 つの一般的な走査方法があります:

1)、ルート優先トラバーサル。深さ優先検索 (Depth_First Search) トラバーサルに似ています。これらはすべて、次のようにスタックを使用して要素を走査します:

2)、Breadth_First Search 走査と同様のレベルによる走査。これらはすべて、次のように要素を走査するためにキューを使用します:

さて、ツリーと走査方法を理解したので、JavaScript を使用してそれを一緒に実装しましょう。もちろん、チェーン ストレージ構造を使用します。

まず、次のように 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中文网！