二叉树的遍历

1.二叉树的结构

节点定义如下：

2.二叉树的遍历方法

2.1 广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，也就是一层一层的遍历，上面二叉树的遍历顺序为：root  -- la --ra --lalb --larb --ralb --rarb

        可以利用队列实现广度优先搜索。代码实现如下：

注：上面用到了队列的offer和poll方法，这里简单记录下这两个方法和以前方法的区别：

（1）offer，add区别：

一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。

这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。 

（2）poll，remove区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似，

但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

（3）peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。element()与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null

2.2深度优先遍历

深度遍历使用栈数据结构，实现栈的数据结构的容器有Stack和LinkedList，此处使用LinkedList

2.2.1先序遍历：先遍历根节点，然后再遍历左节点和右节点：上面二叉树的遍历结果为

root--la--lalb--larb--ra--ralb--rarb

实现算法如下（递归）

实现算法如下（非递归）

前序遍历比较简单，步骤是先将根结点入栈，然后出栈，并再将根结点右子结点入栈，最后左子结点入栈，依次轮回达到出栈的顺序是：根-左-右

(1)

(2)

2.2.2：中序遍历：先遍历底部左节点，然后是根节点，最后是右节点，上面二叉树的遍历结果是

lalb--la--larb--root--ralb--ra--rarb

实现算法如下（递归）

实现算法如下（非递归）

(1)

(2)

2.2.3：后序遍历：先遍历底

点，上面二叉树的遍历结果是

lalb--larb--la--ralb--rarb--ra--root

实现算法如下（递归）

非递归方式实现