二叉树的前中后序遍历(迭代法)(带动画)
发布日期:2021-06-30 19:46:02
浏览次数:2
分类:技术文章
本文共 1774 字,大约阅读时间需要 5 分钟。
友链:
前序遍历
递归思路:先树根,然后左子树,然后右子树。每棵子树递归。在迭代算法中,思路演变成,每到一个节点 A,就应该立即访问它。
因为,每棵子树都先访问其根节点。对节点的左右子树来说,也一定是先访问根。 在 A 的两棵子树中,遍历完左子树后,再遍历右子树。因此,在访问完根节点后,遍历左子树前,要将右子树压入栈。
动画演示
伪代码
栈S;p= root;while(p || S不空){ while(p){ 访问p节点; p的右子树入S; p = p的左子树; } p = S栈顶弹出;}
代码实现
vector preorderTraversal(TreeNode* root) { stackS; vector v; TreeNode* rt = root; while(rt || S.size()){ while(rt){ S.push(rt->right); v.push_back(rt->val); rt=rt->left; } rt=S.top();S.pop(); } return v; }
中序遍历
每到一个节点 A,因为根的访问在中间,将 A 入栈。然后遍历左子树,接着访问 A,最后遍历右子树。
在访问完 A 后,A 就可以出栈了。因为 A 和其左子树都已经访问完成。伪代码
栈S;p= root;while(p || S不空){ while(p){ p入S; p = p的左子树; } p = S.top 出栈; 访问p; p = p的右子树;}
动画演示
代码实现
vector inorderTraversal(TreeNode* root) { stackS; vector v; TreeNode* rt = root; while(rt || S.size()){ while(rt){ S.push(rt); rt=rt->left; } rt=S.top();S.pop(); v.push_back(rt->val); rt=rt->right; } return v; }
后序遍历
后序遍历与前序遍历相对称。
思路: 每到一个节点 A,就应该立即访问它。 然后将左子树压入栈,再次遍历右子树。遍历完整棵树后,结果序列逆序即可。
伪代码
栈S;p= root;while(p || S不空){ while(p){ 访问p节点; p的左子树入S; p = p的右子树; } p = S栈顶弹出;}结果序列逆序;
代码实现
vector postorderTraversal(TreeNode* root) { stackS; vector v; TreeNode* rt = root; while(rt || S.size()){ while(rt){ S.push(rt->left); v.push_back(rt->val); rt=rt->right; } rt=S.top();S.pop(); } reverse(v.begin(),v.end()); return v;}
转载地址:https://lion-wu.blog.csdn.net/article/details/107931169 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月26日 09时32分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Oracle 利用 UTL_SMTP 包发送邮件
2019-04-30
Oracle 自定义函数实现split功能,支持超长字符串和clob类型的分隔
2019-04-30
Oracle 的循环中的异常捕捉和处理
2019-04-30
Oracle通过pivot和unpivot配合实现行列转换
2019-04-30
给Oracle数据库换一个1522端口的监听
2019-04-30
Excel表格数据生成ECharts图表
2019-04-30
阿里云短信服务python版,pyinstaller打包运行时缺少文件
2019-04-30
Oracle的pfile和spfile的一点理解和笔记
2019-04-30
WebService的简单案例记录(Java)
2019-04-30
Html利用PHP与MySQL交互
2019-04-30
dos简单命令
2019-04-30
mysql的安装与卸载与Navicat远程连接
2019-04-30
java实现稀疏数组及将稀疏数组存入硬盘中
2019-04-30
2021-05-18
2019-04-30
Flutter 使用插件打开相册、相机
2019-04-30
libuv实现tcp代理服务器
2019-04-30
libuv使用不当导致的内存泄漏
2019-04-30
libuv实现ping包发送和接收
2019-04-30
基础架构系列篇-CENTOS7安装NGINX
2019-04-30