关于二叉树遍历的反思(C++)
2021/11/29 9:08:21
本文主要是介绍关于二叉树遍历的反思(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 二叉树函数
- 递归序
- 递归遍历
- 非递归遍历
全文基于左程云老师的教学,感谢左程云老师!
二叉树函数
struct treenode { node* left; node* right; int val; node(int x){val=x;} }*Node;
递归序
递归序是指在递归过程中实际访问的节点顺序
例如树{1,2,3,4,5,6,7}
根据递归行为可知其递归序为:1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1
递归遍历
先序遍历(头左右):打印第一次出现的节点:1,2,4,5,3,6,7
void preorder(Node head) { if(head==NULL)return; cout << head->val; preorder(head->left); preorder(head->right); }
中序遍历(左头右):打印第二次出现的节点:4,2,5,1,6,3,7
void inorder(Node head) { if(head==NULL)return; inorder(head->left); cout << head->val; inorder(head->right); }
后序遍历(右头左):打印第三次出现的节点:4,5,2,6,7,3,1
void postorder(Node head) { if(head==NULL)return; postorder(head->left); postorder(head->right); cout << head->val; }
非递归遍历
先序遍历(头左右):1,2,4,5,3,6,7
先放右再放左,因为栈先进后出
void preorder(Node head) { if(head!=NULL) { stack<Node>stack; stack.push(head); while(!stack.empty()) { head = stack.top(); stack.pop(); cout << head->val << " "; if(head->right) { stack.push(head->right); } if(head->left) { stack.push(head->left); } } } }
后序遍历(右头左):4,5,2,6,7,3,1
准备一个辅助栈进行打印(可以直接用队列)
void postorder(Node head) { if(head!=NULL) { stack<Node>stack1; stack<Node>stack2; stack1.push(head); while(!stack1.empty()) { head = stack1.top(); stack1.pop(); stack2.pop(); cout << head->val << " "; if(head->left) { stack1.push(head->left); } if(head->right) { stack1.push(head->right); } } while(!s2.empty()) { cout << s2.top() << " "; s2.pop(); } } }
中序遍历(左头右):4,2,5,1,6,3,7
整棵树左边界进栈,依次弹出节点的过程中,打印,对弹出节点的右树重复
void postorder(Node head) { if(head!=NULL) { stack<Node>stack; while(!stack.empty() || head!=NULL) { if(head!=NULL) { stack.push(head); head=head->left; } else { head=stack.top(); stack.pop(); cout << head->val << " "; head=head->right; } } } }
层序遍历(一层一层):1,2,3,4,5,6,7
递归要压两次栈,比较复杂。
所以采取BFS(宽度优先遍历)进行遍历
void floororder(Node head) { queue<Node>q; if (head != NULL) { q.push(head); } while (!q.empty()) { cout << q.front()->val << " "; if (q.front()->left) { q.push(q.front()->left); } if (q.front()->right) { q.push(q.front()->right); } q.pop(); } }
这篇关于关于二叉树遍历的反思(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享