这里先总结一下二叉树的遍历算法,包括层次遍历、前序遍历、中序遍历和后序遍历。
完整代码(包括测试用例): (https://github.com/FergusChen/AlgoCode) 包路径:main.tree
层次遍历
层次遍历的关键就是利用队列先进先出的思想。遇到结点就入队列,在该结点出队列的时候进行处理(打印),同时将该结点的左右孩子入队列。
层次遍历的代码:
|
|
非递归实现
前序遍历的非递归算法是用栈来辅助实现“根->左->右”的遍历。先处理(打印)再入栈,在出栈的时候处理该结点的右子树。
前序遍历的非递归实现:
中序遍历
递归实现
明白前序遍历之后,中序遍历和后序遍历就顺理成章了。中序遍历是实现“左->根->右”的遍历。
中序遍历递归实现:
非递归实现
中序遍历非递归实现:
后序遍历
递归实现
实现后序遍历的“左->右->中”,递归实现也是处理时机的问题。
后序遍历递归实现: