二叉树的遍历

Data structure

 2019/09/26 

对于树的遍历来说，有三种遍历方法，分别是先序遍历、中序遍历、后序遍历。三种遍历的区别在于何时访问节点。在遍历树的过程中，每个节点都会遍历三次，分别是遍历到自己，遍历左子树和遍历右子树。如果需要实现先序遍历，那么只需要第一次遍历到节点时进行操作即可

先序遍历

先序遍历可用于打印树的结构。先序遍历先访问根节点，然后访问左节点，最后访问右节点。如下图所示：

用JS实现如下：

preTraversal() {
    this._pre(this.root)
}
_pre(node) {
    if (node) {
        console.log(node.value)
        this._pre(node.left)
        this._pre(node.right)
    }
}

中序遍历

中序遍历可用于排序。对二叉搜索树来说，中序遍历可以实现一次遍历就得到有序的值。中序遍历先访问左节点，然后访问根节点，最后访问右节点。如下图所示：

用JS实现如下：

midTraversal() {
    this._mid(this.root)
}
_mid(node) {
    if (node) {
        this._mid(node.left)
        console.log(node.value)
        this._mid(node.right)
    }
}

后序遍历

后序遍历可用于先操作子节点，再操作父节点的场景。后续遍历先访问左节点，然后访问右节点，最后访问根节点。如下图所示：

用JS实现如下：

backTraversal() {
    this._back(this.root)
}
_back(node) {
    if (node) {
        this._back(node.left)
        this._back(node.right)
        console.log(node.value)
    }
}

原文作者：Jacleklm

原文链接：http://jacleklm.github.io/2019/09/26/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86/

发表日期：September 26th 2019, 8:33:46 pm

更新日期：September 17th 2023, 10:00:22 pm

Next Post

webpack之Tree Shaking

CATALOG

1. 先序遍历
2. 中序遍历
3. 后序遍历