집 > 기사 > 웹 프론트엔드 > JavaScript는 이진 트리의 선순, 순차 및 후순 순회 방법을 구현합니다.

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

小云云원래의: 2018-01-02 13:17:592061검색

이 글에서는 이진 트리의 선순, 순차, 후순 순회를 구현하기 위한 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를 다양한 특수 효과를 작성하는 언어로 간주했지만 지금은 항상 너무 순진했습니다. 
관련 권장사항: 
php
Java 최소 이진 트리 힙 정렬 구현 방법
js 구현 데이터 구조: 트리 및 이진 트리, 이진 트리 탐색 그리고 기본적인 조작방법 
위 내용은 JavaScript는 이진 트리의 선순, 순차 및 후순 순회 방법을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

Java php c语言 JavaScript 递归数据结构堆 JS

성명：

이전 기사：JS 휴대폰에서 터치 이벤트를 사용하여 슬라이딩 거리를 계산하는 방법다음 기사：JS 휴대폰에서 터치 이벤트를 사용하여 슬라이딩 거리를 계산하는 방법