JavaScript实现二叉树的先序、中序及后序遍历方法详解
程序员文章站
2022-04-09 21:18:03
本文实例讲述了javascript实现二叉树的先序、中序及后序遍历方法。分享给大家供大家参考,具体如下:
之前学数据结构的时候,学了二叉树的先序、中序、后序遍历的方法,并...
本文实例讲述了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相关内容感兴趣的读者可查看本站专题:《javascript数据结构与算法技巧总结》、《javascript数学运算用法总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
上一篇: 微信小程序返回多级页面的实现方法
推荐阅读
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
JavaScript实现二叉树定义、遍历及查找的方法详解
-
二叉树的先序遍历、中序遍历、后序遍历
-
JavaScript实现二叉树的先序、中序及后序遍历方法详解
-
python实现二叉树的层序、前序、中序、后序、之字形遍历
-
C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法
-
左神算法:分别用递归和非递归方式实现二叉树先序、中序和后序遍历(Java版)