首页 / 算法 / [算法]二叉树的非递归遍历算法

[算法]二叉树的非递归遍历算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[算法]二叉树的非递归遍历算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含673字，纯文字阅读大概需要1分钟。

内容图文

1.二叉树的非递归中序遍历算法

二叉树的中序遍历方法是：左中右，因此一开始会顺着根节点的左孩子一直往下（这点和先序遍历一样，这也是二者前面部分代码很相似的原因），到最后一个左孩子时尝试把它的右孩子塞进栈内，然后顺着它的的左孩子而下，直到不能访问为止。利用的栈FILO的特性，对每个节点都进行顺左孩子而下即可。

上代码：

             1
            void inOrder(TreeNode* root,vector<int>& inOrder)
 2  {
 3     stack<TreeNode*>st;
 4     TreeNode* p = root;
 5while (p != nullptr || !st.empty())
 6    {
 7while (p != nullptr)
 8      {
 9        st.push(p);
10         p = p->left;
11      }
12if (!st.empty())
13      {
14         auto top = st.top();
15         inOrder.push_back(top->val);
16        st.pop();
17         p = top->left;
18      }
19    }
20   }

 

具体实现可以参考这篇文章：https://www.jianshu.com/p/49c8cfd07410，当然我的思(dai)路(ma)也是从这里获(chao)取(xi)的(??保命)

原文：https://www.cnblogs.com/Swetchine/p/11260926.html

内容总结

以上是互联网集市为您收集整理的[算法]二叉树的非递归遍历算法全部内容，希望文章能够帮你解决[算法]二叉树的非递归遍历算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1315419.html

来源：【匿名】