网络

教育改变生活

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 439|回复: 0
打印 上一主题 下一主题

【数据结构】二叉树先序遍历(递归与非递归)

[复制链接]

689

主题

696

帖子

3112

积分

版主

Rank: 7Rank: 7Rank: 7

积分
3112
跳转到指定楼层
楼主
发表于 2023-9-5 15:56:38 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 wander 于 2023-9-5 16:03 编辑

二叉树先序遍历的实现思想是:
  • 访问根节点;
  • 访问当前节点的左子树;
  • 若当前节点无左子树,则访问当前节点的右子树;

图 1 二叉树

以图  1 为例,采用先序遍历的思想遍历该二叉树的过程为:
  • 访问该二叉树的根节点,找到 1;
  • 访问节点 1 的左子树,找到节点 2;
  • 访问节点 2 的左子树,找到节点 4;
  • 由于访问节点 4 左子树失败,且也没有右子树,因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树,因此现在开始遍历,即访问节点 5;
  • 由于节点 5 无左右子树,因此节点 5 遍历完成,并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ,并开始遍历该节点的右子树,即访问节点 3;
  • 访问节点 3 左子树,找到节点 6;
  • 由于节点 6 无左右子树,因此节点 6 遍历完成,回到节点 3 并遍历其右子树,找到节点 7;
  • 节点 7 无左右子树,因此以节点 3 为根节点的子树遍历完成,同时回归节点 1。由于节点 1 的左右子树全部遍历完成,因此整个二叉树遍历完成;

因此,图 1 中二叉树采用先序遍历得到的序列为:
1 2 4 5 3 6 7

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

WEB前端

QQ|手机版|小黑屋|金桨网|助学堂  咨询请联系站长。

GMT+8, 2024-12-24 22:14 , Processed in 0.032891 second(s), 21 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表