二叉树的遍历
二叉树的遍历,主要有四种方式
- 先序遍历
- 中序遍历
- 后序遍历
- 层序遍历
实现方式有两种
- 递归实现
- 迭代实现
先序遍历
前序遍历的顺序是 根节点-左子树-右子树 。意思是从根节点开始,要一直访问左子树,直到没有左孩子,然后访问右子树。
中序遍历
中序遍历的过程是 左子树-根节点-右子树
后序遍历
后序遍历的过程就是 左子树-右子树-根节点
源码
准备一个二叉树
1 | 1 |
推理出,理论输出:
1 | 前序输出: 1 2 4 5 3 6 8 9 7 |
下面是源码实现,有两种实现方式
- 递归方式
- 迭代方式
1 | package main |