JavaScript
搜索
分类

JavaScript实现二叉树的先序、中序及后序遍历方法详解

作者：juzipchy 时间：2024-04-29 14:07:28　

本文实例讲述了JavaScript实现二叉树的先序、中序及后序遍历方法。分享给大家供大家参考，具体如下：

之前学数据结构的时候，学了二叉树的先序、中序、后序遍历的方法，并用C语言实现了，下文是用js实现二叉树的3种遍历，并以动画的形式展现出遍历的过程。

整个遍历过程还是采用递归的思想，原理很粗暴也很简单

先序遍历的函数：


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

中序遍历的函数：


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

后序遍历的函数：


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

颜色变化函数：


function changeColor(){
 var i=0;
 divList[i].style.backgroundColor = 'blue';
 timer=setInterval(function(argument){
   i++;
   if(i<divList.length){
     divList[i-1].style.backgroundColor="#fff";
     divList[i].style.backgroundColor="blue";
   }
   else{
     divList[divList.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>
<div class="root">
 <div class="child_1">
   <div class="child_2">
     <div class="child_3"></div>
     <div class="child_3"></div>
   </div>
   <div class="child_2">
     <div class="child_3"></div>
     <div class="child_3"></div>
   </div>
 </div>
 <div class="child_1">
   <div class="child_2">
     <div class="child_3"></div>
     <div class="child_3"></div>
   </div>
   <div class="child_2">
     <div class="child_3"></div>
     <div class="child_3"></div>
   </div>
 </div>
</div>
<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],
 divList = [],
 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)){
   divList.push(node);
   preOrder(node.firstElementChild);
   preOrder(node.lastElementChild);
 }
}
/*中序遍历*/
function inOrder(node) {
 if (!(node == null)) {
   inOrder(node.firstElementChild);
   divList.push(node);
   inOrder(node.lastElementChild);
 }
}
/*后序遍历*/
function postOrder(node) {
 if (!(node == null)) {
   postOrder(node.firstElementChild);
   postOrder(node.lastElementChild);
   divList.push(node);
 }
}
/*颜色变化函数*/
function changeColor(){
 var i=0;
 divList[i].style.backgroundColor = 'blue';
 timer=setInterval(function(argument){
   i++;
   if(i<divList.length){
     divList[i-1].style.backgroundColor="#fff";
     divList[i].style.backgroundColor="blue";
   }
   else{
     divList[divList.length-1].style.backgroundColor="#fff";
   }
 },500)
}
function reset(){
 divList=[];
 clearInterval(timer);
 var divs=document.getElementsByTagName("div");
 for(var i=0;i<divs.length;i++){
   divs[i].style.backgroundColor="#fff";
 }
}

由此可见，二叉树的遍历思想是一样的。之前一直把JS看做是写各种特效的语言，现在向来是too naive了。

希望本文所述对大家JavaScript程序设计有所帮助。

来源：http://blog.csdn.net/juzipchy/article/details/53814237

标签：JavaScript,二叉树
0
投稿

猜你喜欢

  • python中defaultdict字典功能特性介绍

    2022-06-07 23:27:45

  • python中的eval函数使用实例

    2021-06-20 00:34:07

  • MySql使用mysqldump 导入与导出方法总结

    2024-01-23 13:26:32

  • 使用 Python 破解压缩文件的密码的思路详解

    2021-09-29 22:36:48

  • 巧制可全屏拖动的图片

    2008-05-09 19:34:00

  • Linux下彻底删除Mysql 8.0服务的方法

    2024-01-14 06:38:04

  • python3正则模块re的使用方法详解

    2022-10-14 17:22:16

  • Python基于SMTP协议实现发送邮件功能详解

    2022-07-17 00:31:00

  • Git在Windows中安装与使用教程

    2023-11-01 08:47:55

  • Python计算三角函数之asin()方法的使用

    2023-08-04 22:31:46

  • SqlServer服务中利用触发器对指定账户进行登录ip限制提升安全性操作

    2024-01-26 12:24:32

  • 解决MySQl查询不区分大小写的方法讲解

    2024-01-12 13:49:51

  • pandas dataframe添加表格框线输出的方法

    2021-11-28 01:34:41

  • golang 随机数的两种方式

    2024-04-28 10:46:44

  • XMLHTTPRequest的属性和方法简介

    2007-12-18 18:42:00

  • Python 异步之生成器示例详解

    2023-01-12 04:34:26

  • 详解Python list 与 NumPy.ndarry 切片之间的对比

    2023-02-16 10:25:23

  • python中requests模拟登录的三种方式(携带cookie/session进行请求网站)

    2021-11-29 10:44:29

  • PyCharm2019.3永久激活破解详细图文教程，亲测可用（不定期更新）

    2022-04-27 23:51:16

  • 使用Python的Flask框架来搭建第一个Web应用程序

    2022-12-11 21:46:10
    • asp之家 网络编程 m.aspxhome.com