java 二叉树的深度优先遍历、搜索,广度优先遍历、搜索

(2017.9.5 这里要补充一点,树是图的子集,图的遍历、搜索也是同理)

深度优先需要借助栈、直接递归实现,广度优先需要借助队列实现。

在了解本文之前,需要先弄懂java中的ArrayDeque(ArrayDeque既可以作为队列使用,也可以作为栈使用),本文不另行介绍(其实直接看看ArrayDeque的Api就行了,很好懂)。

 

一、深度优先遍历

直接递归遍历:

二、深度优先搜索

深度优先搜索就是一直往下搜索,有两种实现思路:递归、栈。

使用栈实现:

三、广度优先遍历

使用队列实现:

四、广度优先搜索

广度优先搜索就是“横向”搜索(同级搜索)。

使用队列实现:

五、搜索某个元素时,应该使用深度、广度优先搜索吗?

如果我们需要搜索元素,首先应该考虑、使用二叉树的特性。个人认为:一般不会使用这两种搜索方式去搜索某个元素。

正确的搜索方式:

六、总结

个人认为所谓的“深度、广度优先遍历”确实有用,而“深度、广度优先搜索似乎没有必要”。当然具体情况需要具体分析。