JavaScript 트리 구조에 대한 자세한 설명

자료 구조 '트리'에 대해서는 누구나 잘 알고 계실 텐데요. 오늘은 데이터 구조에서 이진 트리와 트리를 살펴보고 자바스크립트로 구현해 보겠습니다.

ps: Vue의 가상 DOM, 버블링 등 프런트엔드 여러 곳에 트리 구조가 생생하게 반영되어 있습니다.

이진 트리

--개념--

이진 트리는 각 노드가 최대 2개의 하위 트리를 갖는 것이 특징인 트리 구조입니다. 아니요 2)보다 큰 차수를 갖는 노드가 있으며 이진 트리의 하위 트리는 왼쪽 하위 트리와 오른쪽 하위 트리로 나눌 수 있으며 그 순서는 임의로 바뀔 수 없습니다.

은 다음과 같으며 이는 이진 트리입니다(참고: 다음 이진 트리 예는 모두 이 이진 트리를 기반으로 합니다).

그리고, 이진 트리 순회(이진 트리 순회)에는 일반적으로 사용되는 세 가지 방법이 있습니다.

1) 이진 트리 선순 순회(루트 왼쪽 및 오른쪽)

이진 트리가 비어 있으면 작업이 수행되지 않습니다.

-- 루트 노드를 방문합니다.

- 순서대로 왼쪽 하위 트리를 탐색합니다. 순서대로.

예를 들어 위 예의 이진 트리의 경우 순회 결과는 다음과 같습니다.

2) 이진 트리의 순회 트리(왼쪽 루트 오른쪽)

이진 트리가 비어 있으면 작업이 수행되지 않습니다.

—왼쪽 하위 트리를 순서대로 순회합니다.

—루트 노드를 방문합니다. ;

—순차 순회 오른쪽 하위 트리.

예를 들어 위의 예에서 이진 트리의 순회 결과는 다음과 같습니다.

3), 이진 트리의 후순 순회 트리(왼쪽 및 오른쪽 루트)

이진 트리가 비어 있으면 작업이 수행되지 않습니다.

— 후위로 왼쪽 하위 트리를 순회합니다.

— 오른쪽으로 순회합니다. 사후 순서의 하위 트리

--루트 노드를 방문합니다.

예를 들어 위 예의 이진 트리의 경우 순회 결과는 다음과 같습니다.

자, 이제 이진 트리를 이해하고 어떻게 순회하는지, 함께 해보자 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);
 }
};

자, 위의 이진 트리 예를 사용하여 테스트할 수 있습니다. 우리 자신:

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) 노드. 비어 있지 않은 트리에는 루트라고 불리는 단 하나의 특정 노드가 있습니다. n>1일 때 나머지 노드는 서로 분리된 m(m>0)개의 유한 노드로 나눌 수 있으며, 각 노드는 그 자체입니다. 루트의 하위 트리라고 불리는 트리. 물론 이진 트리는 확실히 트리에 속합니다.

다음은 트리입니다(참고: 다음 트리 예는 모두 이 트리를 기반으로 합니다).

그리고 두 개 이상의 트리를 순회합니다. 하위 트리에 일반적으로 사용되는 두 가지 탐색 방법은 다음과 같습니다.

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中文网！