1回答

liuyubobobo

2020-04-28

bfs 和 dfs 本身都是非常重要的思想，他们不仅仅适用于 BST，也适用于普通的二叉树，n叉树，甚至是图结构。

是的，如果仅仅是在 BST 中查找，bfs 和 dfs 都没有意义，我们不需要遍历整棵树，使用二分搜索树的性质就能做 logn 级别的搜索。但是，bfs 和 dfs 不仅仅在二分搜索树中有效。

如果看一下 Leetcode 中关于树的问题，就会发现，大多数都不是在 BST 中的，而是在普通的二叉树中的。这是因为 BST 的性质太特殊了，所以，确实，需要遍历的机会很少。而计算机科学家发明出 BST，就是为了减少遍历。

对于 dfs 和 bfs 在图结构中的应用，尤其需要重视。尤其是 bfs，是在无权图中求最短路径的标准方式。这一点在我的图论课程中有详细介绍。如果学习完这个课程以后，有兴趣可以进一步学习：https://coding.imooc.com/class/370.html

继续加油！：）

0

0