当前位置:Gxlcms > JavaScript > JS二叉树的先序中序及后序遍历实现方法

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

时间:2021-07-01 10:21:17 帮助过:4人阅读

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

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

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

先序遍历的函数:

  1. function preOrder(node){
  2. if(!(node==null)){
  3. pList.push(node);
  4. preOrder(node.firstElementChild);
  5. preOrder(node.lastElementChild);
  6. }
  7. }

中序遍历的函数:

  1. function inOrder(node) {
  2. if (!(node == null)) {
  3. inOrder(node.firstElementChild);
  4. pList.push(node);
  5. inOrder(node.lastElementChild);
  6. }
  7. }

后序遍历的函数:

  1. function postOrder(node) {
  2. if (!(node == null)) {
  3. postOrder(node.firstElementChild);
  4. postOrder(node.lastElementChild);
  5. pList.push(node);
  6. }
  7. }

颜色变化函数:

  1. function changeColor(){
  2. var i=0;
  3. pList[i].style.backgroundColor = 'blue';
  4. timer=setInterval(function(argument){
  5. i++;
  6. if(i<pList.length){
  7. pList[i-1].style.backgroundColor="#fff";
  8. pList[i].style.backgroundColor="blue";
  9. }
  10. else{
  11. pList[pList.length-1].style.backgroundColor="#fff";
  12. }
  13. },500)
  14. }

核心代码如上,本来想写深度优先遍历和广度优先遍历。后来发现二叉树深度优先遍历和先序遍历相同。改日总结一下树的BFS和DFS。

全部代码如下:

  1. <!DOCTYPE html>
  2. <html>
  3. <head lang="en">
  4. <meta charset="UTF-8">
  5. <title></title>
  6. <style>
  7. .root{
  8. display: flex;
  9. padding: 20px;
  10. width: 1000px;
  11. height: 300px;border: 1px solid #000000;
  12. margin: 100px auto;
  13. margin-bottom: 10px;
  14. justify-content: space-between;
  15. }
  16. .child_1{
  17. display: flex;
  18. padding: 20px;
  19. width: 450px;
  20. height: 260px;border: 1px solid red;
  21. justify-content: space-between;
  22. }
  23. .child_2{
  24. display: flex;
  25. padding: 20px;
  26. width: 170px;
  27. height: 220px;border: 1px solid green;
  28. justify-content: space-between;
  29. }
  30. .child_3{
  31. display: flex;
  32. padding: 20px;
  33. width: 35px;
  34. height: 180px;border: 1px solid blue;
  35. justify-content: space-between;
  36. }
  37. input{
  38. margin-left: 100px;
  39. width: 60px;
  40. height: 40px;
  41. font:20px italic;
  42. }
  43. </style>
  44. </head>
  45. <body>
  46. <p class="root">
  47. <p class="child_1">
  48. <p class="child_2">
  49. <p class="child_3"></p>
  50. <p class="child_3"></p>
  51. </p>
  52. <p class="child_2">
  53. <p class="child_3"></p>
  54. <p class="child_3"></p>
  55. </p>
  56. </p>
  57. <p class="child_1">
  58. <p class="child_2">
  59. <p class="child_3"></p>
  60. <p class="child_3"></p>
  61. </p>
  62. <p class="child_2">
  63. <p class="child_3"></p>
  64. <p class="child_3"></p>
  65. </p>
  66. </p>
  67. </p>
  68. <input type="button" value="先序">
  69. <input type="button" value="中序">
  70. <input type="button" value="后序">
  71. <script type="text/javascript" src="遍历.js"></script>
  72. </body>
  73. </html>

js:

  1. /**
  2. * Created by hp on 2016/12/22.
  3. */
  4. var btn = document.getElementsByTagName('input'),
  5. preBtn = btn[0],
  6. inBtn = btn[1],
  7. postBtn = btn[2],
  8. treeRoot = document.getElementsByClassName('root')[0],
  9. pList = [],
  10. timer = null;
  11. window.onload=function(){
  12. preBtn.onclick = function () {
  13. reset();
  14. preOrder(treeRoot);
  15. changeColor();
  16. }
  17. inBtn.onclick = function () {
  18. reset();
  19. inOrder(treeRoot);
  20. changeColor();
  21. }
  22. postBtn.onclick = function () {
  23. reset();
  24. postOrder(treeRoot);
  25. changeColor();
  26. }
  27. }
  28. /*先序遍历*/
  29. function preOrder(node){
  30. if(!(node==null)){
  31. pList.push(node);
  32. preOrder(node.firstElementChild);
  33. preOrder(node.lastElementChild);
  34. }
  35. }
  36. /*中序遍历*/
  37. function inOrder(node) {
  38. if (!(node == null)) {
  39. inOrder(node.firstElementChild);
  40. pList.push(node);
  41. inOrder(node.lastElementChild);
  42. }
  43. }
  44. /*后序遍历*/
  45. function postOrder(node) {
  46. if (!(node == null)) {
  47. postOrder(node.firstElementChild);
  48. postOrder(node.lastElementChild);
  49. pList.push(node);
  50. }
  51. }
  52. /*颜色变化函数*/
  53. function changeColor(){
  54. var i=0;
  55. pList[i].style.backgroundColor = 'blue';
  56. timer=setInterval(function(argument){
  57. i++;
  58. if(i<pList.length){
  59. pList[i-1].style.backgroundColor="#fff";
  60. pList[i].style.backgroundColor="blue";
  61. }
  62. else{
  63. pList[pList.length-1].style.backgroundColor="#fff";
  64. }
  65. },500)
  66. }
  67. function reset(){
  68. pList=[];
  69. clearInterval(timer);
  70. var ps=document.getElementsByTagName("p");
  71. for(var i=0;i<ps.length;i++){
  72. ps[i].style.backgroundColor="#fff";
  73. }
  74. }

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

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

推荐阅读:

touch事件如何获取滑动距离长度

JS+H5+C3实现弹出窗口

以上就是JS二叉树的先序中序及后序遍历实现方法的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行