Flex布局+JS:实现可视化的二叉树遍历

最近在学习js和树,要求是实现一个二叉树,布局可以使用Flex,用js实现对二叉树的前中后序遍历。
没学习过Flex,因此特意去看了一下教程。有两个教程写得非常好:
1.Flex布局教程——语法篇
http://www.ruanyifeng.com/blog/2015/07/flex-grammar.html
2.Flex布局教程——实例篇
http://www.ruanyifeng.com/blog/2015/07/flex-examples.html

接下来就开始做可视化地遍历二叉树吧~


Flex布局

要求的布局是这样的:

我写的布局是这样的:

这样的布局使用Flex很简单
HTML代码如下:

<div id="tree">
    <div>
        <div>
            <div></div>
            <div></div>
        </div>
        <div>
            <div></div>
            <div></div>
        </div>  </div>
    <div>
        <div>
            <div></div>
            <div></div>
        </div>
        <div>
            <div></div>
            <div></div>
        </div>      
    </div>
</div>

CSS代码如下

#tree{
    display: flex;
    border: 1px solid black;
    width: 700px;
    height: 200px;
    justify-content: space-around;
    margin-bottom: 10px;
}
#tree div{
    //注意此处! 我就是忘记写了这个导致除了第一个div有横向排列,其他div都是纵向排列,还搞不清楚为什么
    display: flex;
    border: 1px solid red;
    width:44%;
    height: 70%;
    //垂直居中
    margin: auto 0;
    //让两个div有一定的间距
    justify-content: space-around;
}

二叉树前序、中序和后序遍历算法

因为数据结构学了好久了,对二叉树也忘了差不多了…所以又找了篇二叉树教程:
https://segmentfault.com/a/1190000000740261

二叉树的遍历有三种方式,如下:
(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。
(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。
(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。

JS代码也很简单,就是简单的递归:

//前序遍历
function preOrder(node) {
    if(node!=null) {
        nodeArr.push(node);
        preOrder(node.firstElementChild);
        preOrder(node.lastElementChild);
    }
}
//中序遍历
function inOrder(node) {
    if(node!=null) {
        inOrder(node.firstElementChild);
        nodeArr.push(node);
        inOrder(node.lastElementChild);
    }
}
//后序遍历
function postOrder(node) {
    if(node!=null) {
        postOrder(node.firstElementChild);
        postOrder(node.lastElementChild);
        nodeArr.push(node);
    }
}

可视化实现

这个我认为是本次任务的重点(我是花了不少时间,当然理解二叉树的遍历原理也很重要。
关于可视化的实现我的主要思路和上一篇文章的可视化类似——先保存遍历的结果,再通过循环内使用setTimeout(上一篇使用的是setTimeInterval)实现一段时间显示一个节点的背景颜色的改变。
主要的js代码如下:

function show() {
    for(var i = 0; i < nodeArr.length; i++) {
        setTimeout((function(num){
            return function() {
                if(num-1 >= 0) {
                    nodeArr[num-1].style.backgroundColor = "white";
                }
                nodeArr[num].style.backgroundColor = "orange";
            }
        })(i), i*1000);
    }
}

nodeArr是用来保存遍历过程的节点的
一开始因为对setTimeout不熟悉,我是这样写的

setTimeout((function(num){
    if(num-1 >= 0) {
            nodeArr[num-1].style.backgroundColor = "white";
        }
    nodeArr[num].style.backgroundColor = "orange";  
})(i), 1000);

我理所当然地认为,setTimeout会在每次循环内都等待1秒,然后执行其第一个参数的函数。
但是不对。
1.可以看到setTimeout的第一个参数是一个匿名函数,并且后面紧跟着一个i表示传入i后立即执行该函数。所以它才不会等到你1秒结束后才给你执行呢。

2.你会发现就算你改成了闭包后还是同样的结果。另外一个问题就在那个1000上。循环是一瞬间完成的,你在循环内设置的定时器也相当于同时设置的,所以1秒后大家会同时执行setTimeout内的函数。为了修改这个问题,就需要把1000改为i*1000,表示后面的定时器要等待前面的定时器执行完后的时间加上它本该等待的时间才执行。


结果图



总结

这次的任务让我学到很多:二叉树、Flex布局、可视化实现的另一种方式、setTimeout在循环内实现的原理…
除了专注在实现效果上,我想以后还是要注重运行的效率问题,简化代码什么的。

IT文库 » Flex布局+JS:实现可视化的二叉树遍历
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址