之前我的博客中讲到了如何通过 JS 去实现一颗二叉树, 有兴趣的可以去我的博客中看下. 今天我们来一起实现下二叉树的遍历算法. 欢迎大家帮忙指出不当之处, 或者进行深入的挖掘. 大家一起进步.
二叉树呐, 有三种遍历算法, 1: 中序遍历, 2: 先序遍历, 3: 后序遍历. 在我们看具体实现之前, 我们想下为什么要这样做? 二叉树广泛应用于大量数据查找的业务中, 可以实现更高效率的查找.
1: 中序遍历, 即先查找左节点, 接着查找根节点, 最后查找右节点. 不论中序, 先序, 后序都是以根节点为依据的. 下面上代码
- function inOrder(node) {
- if (!node === null && node instanceof Bst)
- inOrder(node.left)
- console.log(node.data)
- inOrder(node.right)
- }
2: 先序遍历:
- function inOrder(node) {
- if (!node === null && node instanceof Bst)
- console.log(node.data)
- inOrder(node.left)
- inOrder(node.right)
- }
后序遍历类似, 相信大家也能招到一定规律了.
来源: http://www.bubuko.com/infodetail-2869434.html