JavaScript二叉树遍历详解

二叉树概述

二叉树（Binary tree）是每个节点最多存在左右两个分支的树形数据结构。通常分支被称作“左子树”或“右子树”，节点有根节点和子节点。二叉树的分支顺序不能随意颠倒。

二叉树遍历有以下几种方式：

1、深度遍历，包括：

• 先序优先（DLR）：根结点 > 左子树 > 右子树

• 中序优先（LDR）：左子树 > 根结点 > 右子树

• 后序优先（LRD）：左子树 > 右子树 > 根结点

2、广度遍历(层级遍历)

树结构代码构建

深度遍历实现

• 先序优先遍历DLR。

• 中序优先遍历LDR。

• 后序优先遍历LRD。

广度优先(层级遍历)，构造栈来打印。

深度遍历(先序优先非递归版)。

深度遍历(后序优先非递归版)。

总结

二叉树遍历非常有用，理解起来其实非常简单。主要利用的是递归调用和栈(或队列)来完成遍历。