一. 二叉树的四种遍历

  1. 先序遍历 — 根 – 左 – 右
  2. 中序遍历 — 左 – 根 – 右
  3. 后序遍历 — 左 – 右 – 根 (前三种属于递归遍历)
  4. 层次遍历 (属于迭代遍历 )

二. 解析三种递归遍历(b23.tv/eNhhf3y )

接下来就让我们直入主题吧!!!

1.先序遍历

无脑学会二叉树的递归遍历法

我们可以看到图中的二叉树结构,首先我们从上往下看,模块一的根就是A,左就是B,右就是C,根据 根 – 左 – 右 的原则,得到的遍历顺序是 A、B、C。同理,模块二的根是B,左是D,右是E,得到的遍历顺序是B、D、E。又因为B是D和E的根所以把D、E放在B的后面,此时的遍历顺序为 A、B、D、E、C。 同理模块三的遍历顺序就是C、F、G。,整理后的顺序就为 A、B、D、E、C、F、G。

2.中序遍历

无脑学会二叉树的递归遍历法

我们可以看到图中的二叉树结构,首先我们从上往下看,模块一的根就是A,左就是B,右就是C,根据 左 – 根 – 右 的原则,得到的遍历顺序是 B、A、C。同理,模块二的根是B,左是D,右是E,得到的遍历顺序是D、B、E。又因为B是D和E的根所以此时的遍历顺序为 D、B、E、A、C 同理模块三的遍历顺序就是F、C、G。,整理后的顺序就为 D、B、E、A、F、C、G。

3.后序遍历

后序遍历结果的寻求过程就交给大家啦,方法跟上面的一样哈,如果还没有理解透彻的话,可以通过这个链接b23.tv/eNhhf3y 相信一定能帮到同鞋哦 后序遍历的结果是:D、E、B、F、G、C、A

三. 二叉树的程序遍历

整活!直接上代码吧!

1.先序遍历 代码

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }
    },
    right: {
        val: 'C',
        left: {
            val: 'F'
        },
        right: {
            val: 'G'
        }
    }
}
// 先序遍历
function preorder(root) {
    if (!root) return
    console.log('当前遍历到的节点值是:', root.val);
    preorder(root.left)
    preorder(root.right)
}
preorder(root)   // A B D E C F G

代码里的preorder(root.left) 遍历到底之后才会遍历 preorder(root.right),为什么这么说呢?对于小白来说,这里可能会卡壳。因为代码每次执行到preorder(root.left)的时候,preorder函数会再次调用,并且参数是root.left。这里用到的就是递归的方法啦。

具体解析:这里因为console.log()在preorder(root.left)的前面,所以preorder(root.left)的每次调用,console.log()都会打印val值。打印完 ‘D’ 之后,就到底了,通过 if (!root) return 终止条件,就会return 返回上一次的调用,执行 preorder(root.right),然后递归就打印处出 ‘E’ 啦。

2. 中序遍历 代码

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }
    },
    right: {
        val: 'C',
        left: {
            val: 'F'
        },
        right: {
            val: 'G'
        }
    }
}
// 中序遍历
function inorder(root) {
    if (!root) return
    inorder(root.left)      
    console.log('当前遍历到的节点值是:', root.val);
    inorder(root.right)
}
inorder(root)   // D B E A F C G

具体解析:代码中,因为 inorder(root.left) 在console.log()前面,所以这里的inorder(root.left)也会先遍历到底之后会return 返回上一次的调用,再执行console.log(),在执行了console.log()的那一刻,inorder(root.right)也能执行,所以先打印了D、B、E,打印E之后,又到底了。所以又会返回上一层就打印A,之后就立即执行了inorder(root.right)。

3. 后序遍历 代码

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }
    },
    right: {
        val: 'C',
        left: {
            val: 'F'
        },
        right: {
            val: 'G'
        }
    }
}
// 后序遍历
function postorder(root) {
    if (!root) return
    postorder(root.left)
    postorder(root.right)
    console.log('当前遍历到的节点值是:', root.val);
}
postorder(root)

这个就可以留给大家思考啦,方法都是一样的哈。 如果觉得可能还不是很熟练的话,可以练练下面的leetcode:

leetcode.cn/problems/bi… leetcode.cn/problems/bi… leetcode.cn/problems/bi…

四. 总结

因为也是刚学不久,所以文章内容可能有点浅显(尴尬),还希望能够帮到童鞋们哦。请家人们发财的小手点点赞哦