Java实现二叉树的深度优先遍历和广度优先遍历算法示例

2018/06 30 13:06

这篇文章主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下

本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法。分享给大家供大家参考,具体如下:

1. 分析

二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。

深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:

先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。

后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。

2. 举例说明

对下图所示的二叉排序树进行遍历,要求使用先序遍历(递归、非递归)、中序遍历(递归、非递归)、后序遍历(递归、非递归)和广度优先遍历。

参考代码:

 

输出结果:

 

--转载请注明: https://www.guangboyuan.cn/java%e5%ae%9e%e7%8e%b0%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e6%b7%b1%e5%ba%a6%e4%bc%98%e5%85%88%e9%81%8d%e5%8e%86%e5%92%8c%e5%b9%bf%e5%ba%a6%e4%bc%98%e5%85%88%e9%81%8d%e5%8e%86%e7%ae%97%e6%b3%95/

发表回复

(必填)