昆明java培训
达内昆明广州春城路

18487146383

热门课程

算法试题——树的深度、广度优先遍历算法及非递归

  • 时间:2015-10-26
  • 发布:达内科技
  • 来源:达内昆明

达内昆明Java培训今天和大家分享这一道面试题的主要目的是,通过图片算法分析让你能够快速掌握这一题的解题思路。

树的遍历按遍历方式分为深度优先和广度优先遍历,并可采用递归和非递归两种遍历方式来进行。

深度优先:深度优先可分为前序遍历,中序遍历,以及后续遍历,其思想大体一致,都是先进行深层次某个节点的遍历,直到为空,然后再往上遍历其兄弟节点。深度优先一般采用递归的方式实现,递归的深度为树的高度。

具体算法表述如下:

1. 访问初始结点v,并标记结点v为已访问。

2. 查找结点v的第一个邻接结点w。

3. 若w存在,则继续执行4,否则算法结束。

4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。

5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

广度优先:广度优先是按照层次来遍历树的节点,先是根节点,然后依次遍历第二层子节点,当第二层子节点遍历完后,在依次遍历第三层子节点。广度优先 采用队列来记录当前可遍历的节点,当遍历某个节点时,将其左孩子和右孩子结点依次入队,待该层遍历完了以后,再依次遍历下一层儿子结点。

具体算法表述如下:

1. 访问初始结点v并标记结点v为已访问。

2. 结点v入队列

3. 当队列非空时,继续执行,否则算法结束。

4. 出队列,取得队头结点u。

5. 查找结点u的第一个邻接结点w。

6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:

1). 若结点w尚未被访问,则访问结点w并标记为已访问。

2). 结点w入队列

3). 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。

现在昆明Java培训根据上述的算法描述,给你一个二叉树你能正确的写出答案了嘛?

二叉树如下图

昆明Java培训

正确答案是:

深度优先遍历顺序为 1->2->4->8->5->3->6->7

广度优先算法的遍历顺序为:1->2->3->4->5->6->7->8

非递归实现:深度优先一般采用递归实现,如改用非递归,则可需要来模拟栈,当需要先遍历当前节点的儿子结点时(例如中序遍历)需要将其压入栈中,先遍历其儿子结点,然后再将其弹出栈,遍历当前节点。广度优先一般采用非递归来实现,用一个队列来保存依次需要遍历的节点。

如需了解java程序代码请点击:java实现深度、广度优先遍历。

上一篇:华为的JAVA面试题
下一篇:列表迭代器

for 循环详解及实战小项目

MyEclipse的配置(上)

Servlet,JSP配置调试及使用

多线程要慎用!

选择城市和中心
贵州省

广西省

海南省

台湾