집 > 기사 > 웹 프론트엔드 > JS를 사용하여 DOM 트리 탐색을 구현하는 방법

JS를 사용하여 DOM 트리 탐색을 구현하는 방법

php中世界最好的语言원래의: 2018-05-23 11:59:291696검색

이번에는 JS를 사용하여 DOM 트리 탐색을 구현하는 방법을 보여 드리겠습니다. 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 중국어 관련 기사를 주목하세요!