JavaScript는 이진 트리의 선순, 순차 및 후순 순회 방법을 구현합니다.-JS 튜토리얼-php.cn

JavaScript는 이진 트리의 선순, 순차 및 후순 순회 방법을 구현합니다.

小云云

풀어 주다： 2018-01-02 13:17:59

원래의

2109명이 탐색했습니다.

이 글에서는 이진 트리의 선순, 순차, 후순 순회를 구현하기 위한 JavaScript를 주로 소개합니다. JavaScript에서 이진 트리의 선순, 순차, 후순 순회 구현 방법을 요약하고 분석합니다. 관련 운영 주의사항을 예시 형태로 올려 놓았습니다. 참고로 모든 분들께 도움이 되었으면 좋겠습니다.

이 문서의 예에서는 JavaScript를 사용하여 이진 트리의 선순, 순차 및 후순 순회를 구현하는 방법을 설명합니다. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

저는 이전에 자료 구조를 배울 때 이진 트리의 선순서, 순순서, 후순 순회 방법을 배웠고 이를 C 언어로 구현했습니다. 다음은 js Traverse를 사용하여 바이너리 트리를 구현하고 순회 과정을 애니메이션 형태로 보여주는 3가지 방법입니다.

전체 순회 프로세스는 여전히 재귀 개념을 채택합니다. 원리는 매우 조잡하고 간단합니다.

선주문 순회 기능:

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 = &#39;blue&#39;;
  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 = &#39;blue&#39;;
  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로그인 후 복사

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