课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 合作企业 > 企业笔试题 > 算法试题——树的深度、广度优先遍历算法及非递归
  • 算法试题——树的深度、广度优先遍历算法及非递归

    发布:达内科技      来源:达内昆明      时间: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面试题

下一篇:列表迭代器

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:12/29

Java--零基础业余班

Java--零基础业余班

开班日期:12/29

Java--周末提升班

Java--周末提升班

开班日期:12/29

Java--零基础周末班

Java--零基础周末班

开班日期:12/29

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56