算法——二叉树的遍历
- 算法简介
- 代码部分
- 先序遍历：
- 递归法：
- 迭代法：
- 中序遍历
- 递归法：
- 迭代法：
- 后序遍历
- 递归法：
- 迭代法：
- 层次遍历
- 迭代法1：
- 迭代法2：
- 参考资料：
讯享网 举一个例子： 先序遍历：根节点->左子树->右子树 顺序：0 1 3 7 8 4 9 2 5 6
先序遍历：
递归法：
递归法很容易理解，根节点优先放进result里，然后再遍历左子树和右子树。
迭代法：
迭代法需要用到栈：
中序遍历
递归法：
同样很容易理解，不再赘述。
迭代法：
使用与先序遍历类似的方式：
后序遍历
递归法：
同样的套路，为了完整还是写一下吧：
迭代法：
这里跟之前就不大一样了。因为在后序遍历中，决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。
这里设置一个lastVisit的游标，用于记录上一个输出的节点。当输出一个节点时要判断，其是否有右子树，若有、是否已经遍历。
当遍历完左子树后，和中序遍历一样，回到根节点，此时要进行一次判断，判断其右子树的情况：如果右子树为空或lastVisit为右子树，说明右子树已遍历完毕，输出该节点；否则进入右子树。
层次遍历
这里只给出迭代法，代码改自 C++ 二叉树的层次遍历
迭代法1：
从根节点开始，对每个节点，令其入队，同时判断其左右子节点是否为空，不为空，则依次入队。逐步输出，直到队列为空。
迭代法2：
与迭代法1相似，只是先入队，再输出。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/207758.html