JS二叉树的先序中序及后序遍历实现方法_动视

JS二叉树的先序中序及后序遍历实现方法

2020-11-27 19:54:43 责编:小采

这次给大家带来JS二叉树的先序中序及后序遍历实现方法，JS二叉树先序中序及后序遍历实现方法的注意事项有哪些，下面就是实战案例，一起来看一下。

之前学数据结构的时候，学了二叉树的先序、中序、后序遍历的方法，并用C语言实现了，下文是用js实现二叉树的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 = '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看做是写各种特效的语言，现在向来是too naive了。

相信看了本文案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！

全部频道