数据结构与算法学习日志15

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

提示：这里可以添加本文要记录的大概内容：

哈喽各位晚上好呀，又到了日常汇报学习进度的时候。今天专攻二叉树遍历的迭代写法，把先序、中序、后序和层序遍历整理一遍，闲言少叙直接进入正题。

提示：以下是本篇文章正文内容，下面案例可供参考

先序遍历二叉树(迭代方法)

// 先序遍历迭代方法voidfun(TreeNode*p){if(p==nullptr)return;stack<TreeNode*>stk;stk.push(p);while(!stk.empty()){TreeNode*cur=stk.top();stk.pop();cout<<cur->val;//栈是先进后出因此先压右节点再压左节点if(cur->right)stk.push(cur->right);if(cur->left)stk.push(cur->left);}}

中序遍历二叉树(迭代方法)

//中序遍历voidfun1(TreeNode*p){if(p==nullptr)return;stack<TreeNode*>stk;TreeNode*cur=p;//如果条件只有栈不为空的话无法访问到根节点的右子树 因为当根节点输出时栈刚好为空while(cur||!stk.empty()){//一直走到左节点为空while(cur!=nullptr){stk.push(cur);cur=cur->left;}//弹出栈顶元素cur=stk.top();cout<<cur->val<<' ';stk.pop();//转向右节点cur=cur->right;}}

后序遍历二叉树(迭代方法)

//后序遍历//在先序遍历的基础上调换左右的顺序 最后反转整个数组vector<int>fun2(TreeNode*p){if(p==nullptr)return{};vector<int>ans;stack<TreeNode*>stk;stk.push(p);while(!stk.empty()){TreeNode*cur=stk.top();stk.pop();ans.push_back(cur->val);if(cur->left)stk.push(cur->left);if(cur->right)stk.push(cur->right);}reverse(ans.begin(),ans.end());returnans;}

二叉树层序遍历

voidLeveOrder(TreeNode*root){if(root==nullptr)return;TreeNode*p=root;queue<TreeNode*>que;que.push(p);while(!que.empty()){//计算每一层的元素个数intsize=que.size();for(inti=0;i<size;i++){TreeNode*cur=que.front();que.pop();cout<<cur->val<<' ';//弹出一个元素的同时压入它的左右子节点if(cur->left)que.push(cur->left);if(cur->right)que.push(cur->right);}cout<<endl;}}

总结

以上就是二叉树几种经典遍历的迭代实现了，栈和队列的用法还是得多刷题巩固。知识越学越觉得要多复盘，感谢各位阅读，我们明天见！