집 >웹 프론트엔드 >JS 튜토리얼 >JS 이진 트리의 선순, 순차, 후순 순회 구현 방법

JS 이진 트리의 선순, 순차, 후순 순회 구현 방법

php中世界最好的语言원래의: 2018-04-16 15:23:302071검색

이번에는 JS 이진 트리의 선주문, 순차 및 후순 순회 구현 방법을 알려 드리겠습니다. JS 이진 트리 선주문, 순차 및 사후 순회 구현 시 주의 사항은 무엇입니까? 순서 순회? 다음은 실제 사례입니다. 한 번 살펴보겠습니다. 예전에 자료 구조를 배울 때 이진 트리의 선순, 순차, 후순 순회 방법을 배웠고, 이를 C 언어로 구현해 보면 다음과 같습니다. 이진 트리 순회를 애니메이션 프로세스 형태로 보여줍니다.

전체 순회 프로세스는 여전히 재귀적 사고를 사용합니다. 원리는 매우 거칠고 간단합니다

. 선주문 순회 기능:

function preOrder(node){
  if(!(node==null)){
    pList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}

순차 순회 기능:

function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    pList.push(node);
    inOrder(node.lastElementChild);
  }
}

후순위 순회 기능:

function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    pList.push(node);
  }
}

색상 변경 기능:

function changeColor(){
  var i=0;
  pList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<pList.length){
      pList[i-1].style.backgroundColor="#fff";
      pList[i].style.backgroundColor="blue";
    }
    else{
      pList[pList.length-1].style.backgroundColor="#fff";
    }
  },500)
}

핵심 코드는 위와 같습니다. 원래는 깊이 우선 순회와 너비 우선 순회를 작성하려고 했습니다. 나중에 이진 트리의 깊이 우선 순회가 선주문 순회와 동일하다는 것이 발견되었습니다. 나무의 BFS와 DFS에 대해서는 나중에 정리하겠습니다.

모든 코드는 다음과 같습니다:

<!DOCTYPE html>
<html>
<head lang="en">
  <meta charset="UTF-8">
  <title></title>
  <style>
    .root{
      display: flex;
      padding: 20px;
      width: 1000px;
      height: 300px;border: 1px solid #000000;
      margin: 100px auto;
      margin-bottom: 10px;
      justify-content: space-between;
    }
    .child_1{
      display: flex;
      padding: 20px;
      width: 450px;
      height: 260px;border: 1px solid red;
      justify-content: space-between;
    }
    .child_2{
      display: flex;
      padding: 20px;
      width: 170px;
      height: 220px;border: 1px solid green;
      justify-content: space-between;
    }
    .child_3{
      display: flex;
      padding: 20px;
      width: 35px;
      height: 180px;border: 1px solid blue;
      justify-content: space-between;
    }
    input{
      margin-left: 100px;
      width: 60px;
      height: 40px;
      font:20px italic;
    }
  </style>
</head>
<body>
<p class="root">
  <p class="child_1">
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
  </p>
  <p class="child_1">
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
  </p>
</p>
<input type="button" value="先序">
<input type="button" value="中序">
<input type="button" value="后序">
<script type="text/javascript" src="遍历.js"></script>
</body>
</html>

js:

/**
 * Created by hp on 2016/12/22.
 */
var btn = document.getElementsByTagName('input'),
  preBtn = btn[0],
  inBtn = btn[1],
  postBtn = btn[2],
  treeRoot = document.getElementsByClassName('root')[0],
  pList = [],
  timer = null;
window.onload=function(){
  preBtn.onclick = function () {
    reset();
    preOrder(treeRoot);
    changeColor();
  }
  inBtn.onclick = function () {
    reset();
    inOrder(treeRoot);
    changeColor();
  }
  postBtn.onclick = function () {
    reset();
    postOrder(treeRoot);
    changeColor();
  }
}
/*先序遍历*/
function preOrder(node){
  if(!(node==null)){
    pList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}
/*中序遍历*/
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    pList.push(node);
    inOrder(node.lastElementChild);
  }
}
/*后序遍历*/
function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    pList.push(node);
  }
}
/*颜色变化函数*/
function changeColor(){
  var i=0;
  pList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<pList.length){
      pList[i-1].style.backgroundColor="#fff";
      pList[i].style.backgroundColor="blue";
    }
    else{
      pList[pList.length-1].style.backgroundColor="#fff";
    }
  },500)
}
function reset(){
  pList=[];
  clearInterval(timer);
  var ps=document.getElementsByTagName("p");
  for(var i=0;i<ps.length;i++){
    ps[i].style.backgroundColor="#fff";
  }
}

이진 트리를 순회하는 아이디어도 같다고 볼 수 있다. 예전에는 JS를 다양한 특수 효과를 작성하는 언어로 간주했지만 지금은 항상 너무 순진했습니다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!