JS가 DOM 트리 탐색을 구현하는 방법은 무엇입니까?

이번에는 JS를 사용하여 DOM 트리 순회를 구현하는 방법과 notes를 사용하여 JS를 사용하여 DOM 트리 순회를 구현하는 방법을 소개하겠습니다. 다음은 실제 사례입니다. 함께 살펴보겠습니다.

이진 DOM 트리 순회

function Tree() {
   var Node = function(key){
      this.key = key;
      this.left = null;
      this.right = null;
   }
   root =null;
}

사전 주문 순회

먼저 루트 노드를 방문한 다음 왼쪽 하위 트리를 순회하고 마지막으로 오른쪽 하위 트리를 순회합니다

Tree.prototype.preOrderTraverse = function(callback){
  preOrder(root, callback);
}
var preOrder = function(node,callback){
  if(node !== null){
    callback(node.key);
    preOrder(node.left, callback);
    preOrder(node.right, callback);
  }
}

DOM 이진 트리로 수정:

var preOrder = function(node,callback) {
  callback(node);
  if(node.firstElementChild) {//先判断子元素节点是否存在
     this.preOrder(node.firstElementChild,callback);
  }
  if(node.lastElementChild) {
    this.preOrder(node.lastElementChild,callback);
  }
};

순차 순회

먼저 왼쪽 하위 트리를 순회한 다음 루트 노드를 방문하고 마지막으로 오른쪽 하위 트리를 순회합니다.

Tree.prototype.inOrderTraverse = function(callback){
  inOrder(root, callback);
}
var inOrder = function(node,callback){
  if(node !== null){
    inOrder(node.left,callback);
    callback(node.key);
    inOrder(node.right, calback);
  }
}

DOM 이진 트리로 수정됨:

var inOrder = function(node,callback){
  if(node.firstElementChild) {
  this.inOrder(node.firstElementChild);
  }
  callback(node);
  if(node.lastElementChild) {
  this.inOrder(node.lastElementChild);
  }
}

사후 순회

먼저 왼쪽 하위 트리를 순회한 다음 오른쪽 하위 트리를 순회하고 마지막으로 루트 노드를 방문합니다.

Tree.prototype.postOrderTraverse = function(callback){
  postOrder(root, callback);
}
var postOrder = function(node,callback){
  if(node !== null){
    postOrder(node.left,callback);
    postOrder(node.right, calback);
    callback(node.key);
  }
}

DOM 이진 트리로 수정됨:

var postOrder = function(node,callback){
  if(node.firstElementChild) {
  this.postOrder(node.firstElementChild);
  }
  if(node.lastElementChild) {
  this.postOrder(node.lastElementChild);
  }
  callback(node);
}

다중 포크 DOM 트리 순회

폭 우선 순회

먼저 루트 노드를 순회한 다음 첫 번째 수준 노드, 두 번째 수준 노드를 방문합니다. 노드,... ., 마지막 레이어에 액세스할 때까지.

큐를 사용하여 비재귀적 방식으로 다중 포크 트리를 탐색합니다.

Tree.prototype.BFSearch = function(node,callback){
  var queue=[];
  while(node!=null){
      callback(node);
    if(node.children.length!=0){
    for (var i=0;i<node.children.length;i++){
      queue.push(node.children[i]);//借助于队列,暂存当前节点的所有子节点
    }
    }
      node=queue.shift();//先入先出，借助于数据结构：队列
  }
};

깊이 우선 탐색

먼저 루트 노드를 탐색한 다음 경로를 따라 가장 깊은 수준까지 탐색하고 마지막으로 레이어를 반환합니다. 레이어별로.

스택을 사용하여 다중 포크 DOM 트리의 깊이 우선 순회를 달성합니다.

Tree.prototype.DFSearch = function(node,callback){
    var stack=[];
    while(node!=null){
    callback(node);
    if(node.children.length!=0){
    for (var i=node.children.length-1;i>=0;i--){//按照相反的子节点顺序压入栈
      stack.push(node.children[i]);//将该节点的所有子节点压入栈
    }
    }
      node = stack.pop();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)
  }
};

이진 DOM 트리의 선주문, 중간 순서 및 후순 순회는 깊이 우선 순회의 특별한 경우입니다

따라서 깊이 우선 순회를 참조하고 스택의 도움을 받아, 이진 DOM 트리는 비재귀적 방식으로 구현될 수 있습니다. 선주문, 순차 및 후순 순회

이진 DOM 트리의 선주문 순회에 대한 비재귀 구현

Tree.prototype.preOrder = function(node,callback) {
    var stack=[];
    while(node!== null || stack.length!=0){
      while(node!==null){
        stack.push(node);
        callback.push(node);
        node=node.firstElementChild;
      }
      node=stack.pop();
      node=node.lastElementChild;
    }
  };

비재귀 구현 이진 DOM 트리의 순차 순회

Tree.prototype.inOrder = function(node,callback) {
    var stack=[];
    while(node!== null || stack.length!=0){
      while(node!==null){
        stack.push(node);
        node=node.firstElementChild;
      }
      node=stack.pop();
      callback(node);
      node=node.lastElementChild;
    }
  };

이진 DOM 트리의 비재귀 구현 DOM 트리의 후순 순회

① 각 노드가 스택에 두 번 푸시됩니다.
② 루프 본문에서, 노드가 팝업되어 노드에 할당될 때마다
3 노드가 여전히 스택의 헤드 노드와 같다면 해당 노드의 자식이 아직 작동되지 않았으므로 해당 자식을 스택에 추가해야 함을 의미합니다
4 그렇지 않으면, 이는 노드가 두 번째로 팝업되어 해당 노드에 액세스했음을 의미합니다.

즉, 처음 팝업되면 노드의 자식을 스택에 푸시하고, 두 번째 팝업에서는 노드에 액세스합니다.

TreeWalker.prototype.postOrder = function(node,callback) {//非递归实现
  var stack=[];
    stack.push(node);
    stack.push(node);
  while(stack.length != 0)
  {
    node = stack.pop();
    if(stack.length != 0 && node==stack[stack.length-1])
    {
      if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);
      if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);
    }
    else
        callback(node);
  }
}

이 기사의 사례를 읽고 나면 방법을 마스터했다고 믿습니다. . 더 흥미로운 내용을 보려면 다른 PHP 중국어 관련 기사를 주목하세요!

추천 자료:

Angular를 작동하여 데이터 요청을 구현하는 방법

노드를 작동하고 비동기를 사용하여 동시성을 제어하는 ​​방법

위 내용은 JS가 DOM 트리 탐색을 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!