经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
C++ 非递归实现二叉树的前中后序遍历
来源:jb51  时间:2021/11/23 17:59:08  对本文有异议

二叉树的前序遍历

在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制。二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可。

具体步骤如下:

  1. 将左路结点入栈,入栈的同时访问左路结点。
  2. 取出栈顶结点top。
  3. 准备访问top结点的右子树。
  1. struct TreeNode {
  2. int val;
  3. TreeNode *left;
  4. TreeNode *right;
  5. TreeNode() : val(0), left(nullptr), right(nullptr) {}
  6. TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  7. TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  8. };
  9. class Solution {
  10. public:
  11. //前序遍历
  12. vector<int> preorderTraversal(TreeNode* root) {
  13. stack<TreeNode*> st; //辅助栈
  14. vector<int> ret; //用于存放前序遍历的结果
  15. TreeNode* cur = root;
  16. while (cur || !st.empty())
  17. {
  18. //1、将左路结点入栈,入栈的同时访问左路结点
  19. while (cur)
  20. {
  21. st.push(cur);
  22. ret.push_back(cur->val);
  23. cur = cur->left;
  24. }
  25. //2、取出栈顶结点
  26. TreeNode* top = st.top();
  27. st.pop();
  28. //3、准备访问其右子树
  29. cur = top->right;
  30. }
  31. return ret; //返回前序遍历结果
  32. }
  33. };

二叉树的中序遍历

二叉树的中序遍历顺序是:左子树 → 根 → 右子树,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再从栈顶依次取出结点,在取出结点的同时便对其进行访问,此时就相当于先访问了左子树再访问了根,之后再用同样的方式访问取出结点的右子树即可。

具体步骤如下:

  1. 将左路结点入栈。
  2. 取出栈顶结点top并访问。
  3. 准备访问top结点的右子树。
  1. struct TreeNode {
  2. int val;
  3. TreeNode *left;
  4. TreeNode *right;
  5. TreeNode() : val(0), left(nullptr), right(nullptr) {}
  6. TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  7. TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  8. };
  9. class Solution {
  10. public:
  11. //中序遍历
  12. vector<int> inorderTraversal(TreeNode* root) {
  13. stack<TreeNode*> st; //辅助栈
  14. vector<int> ret; //用于存放中序遍历的结果
  15. TreeNode* cur = root;
  16. while (cur || !st.empty())
  17. {
  18. //1、将左路结点入栈
  19. while (cur)
  20. {
  21. st.push(cur);
  22. cur = cur->left;
  23. }
  24. //2、取出栈顶结点并访问
  25. TreeNode* top = st.top();
  26. st.pop();
  27. ret.push_back(top->val);
  28. //3、准备访问其右子树
  29. cur = top->right;
  30. }
  31. return ret; //返回中序遍历结果
  32. }
  33. };

二叉树的后序遍历

二叉树的后序遍历顺序是:左子树 → 右子树 → 根,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再观察栈顶结点,若栈顶结点的右子树为空,或栈顶结点的右子树已经被访问过了,则栈顶结点可以出栈并访问,若栈顶结点的右子树还未被访问,则用同样的方式访问栈顶结点的右子树,直到其右子树被访问后再访问该结点,这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。

具体步骤如下:

  1. 将左路结点入栈。
  2. 观察栈顶结点top。
  3. 若top结点的右子树为空,或top结点的右子树已经访问过了,则访问top结点。访问top结点后将其从栈中弹出,并更新上一次访问的结点为top。
  4. 若top结点的右子树还未被访问,则准备访问其右子树。
  1. struct TreeNode {
  2. int val;
  3. TreeNode *left;
  4. TreeNode *right;
  5. TreeNode() : val(0), left(nullptr), right(nullptr) {}
  6. TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  7. TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  8. };
  9. class Solution {
  10. public:
  11. //后序遍历
  12. vector<int> postorderTraversal(TreeNode* root) {
  13. stack<TreeNode*> st; //辅助栈
  14. vector<int> ret; //用于存放后序遍历的结果
  15. TreeNode* cur = root;
  16. TreeNode* prev = nullptr; //记录上一次访问的结点
  17. while (cur || !st.empty())
  18. {
  19. //1、将左路结点入栈
  20. while (cur)
  21. {
  22. st.push(cur);
  23. cur = cur->left;
  24. }
  25. //2、取出栈顶结点
  26. TreeNode* top = st.top();
  27. //3、若取出结点的右子树为空,或右子树已经访问过了,则访问该结点
  28. if (top->right == nullptr || top->right == prev)
  29. {
  30. //访问top结点后将其从栈中弹出
  31. st.pop();
  32. ret.push_back(top->val);
  33. //更新上一次访问的结点为top
  34. prev = top;
  35. }
  36. else //4、若取出结点的右子树还未被访问,则准备访问其右子树
  37. {
  38. cur = top->right;
  39. }
  40. }
  41. return ret; //返回后序遍历结果
  42. }
  43. };

注意: 看动图演示时请结合所给代码,动图是严格按照代码的逻辑制作的。

到此这篇关于C++ 非递归实现二叉树的前中后序遍历的文章就介绍到这了,更多相关二叉树前中后序遍历内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号