Morris遍历以及Morris前序中序后序遍历实现
2024-10-21 10:12:59
#include<iostream>
using namespace std; struct TreeNode{
int val;
TreeNode* right;
TreeNode* left;
TreeNode(int _val):val(_val),right(nullptr),left(nullptr){}
}; void Morris(TreeNode* root){
if(root == nullptr)
return;
TreeNode* cur=root;
TreeNode* mostRight=nullptr; //当cur为空停止，即上图中的情况3
while(cur != nullptr){
mostRight=cur->left;
//如果mostRight!=nullptr，进入情况2
if(mostRight != nullptr){
while(mostRight->right && mostRight != cur)
mostRight=mostRight->right;
//当mostRight == nullptr，即情况2.a
if(mostRight->right == nullptr){
mostRight->right=cur;
cur=cur->left;
continue;
}
else{ //当mostRight == cur，即情况2.b
mostRight->right=nullptr;
/*cur=cur->left;
continue;*/
}
}
//mostright为空进入情况1
cur=cur->left;
}
}
Morris前序遍历
有左子树就会回到cur节点两次，没有就来一次
void MorrisPre(TreeNode* root) {
if (root == nullptr)
return;
TreeNode* cur = root;
TreeNode* mostRight = nullptr;
while (cur != nullptr) {
mostRight = cur->left;
if (mostRight != nullptr) {
while (mostRight->right && mostRight->right != cur) {
mostRight = mostRight->right;
}
if (mostRight->right == nullptr) {
//第一次到达左子树的最右子树
printf("%d ", cur->val);
mostRight->right = cur;
cur = cur->left;
continue;
}
else {
//第二次到达左子树的最右子树
mostRight->right == cur;
mostRight->right = nullptr;
/*cur = cur->right;
continue;*/
}
}
else {
//当前cur只能来一次
printf("%d ", cur->val);
}
cur = cur->right;
}
}
Morris中序遍历
void MorrisIn(TreeNode* root) {
if (root == nullptr)
return;
TreeNode* cur = root;
TreeNode* mostRight = nullptr;
while (cur != nullptr) {
mostRight = cur->left;
if (mostRight != nullptr) {
while (mostRight->right && mostRight->right != cur) {
mostRight = mostRight->right;
}
if (mostRight->right == nullptr) { //第一次到达左子树的最右子树
mostRight->right = cur;
cur = cur->left;
continue;
}
else { //第二次到达左子树的最右子树 mostRight->right == cur;
mostRight->right = nullptr;
/*cur = cur->right;
continue;*/
}
}
//往右移动的时候打印
printf("%d ", cur->val);
cur = cur->right;
}
}
Morris后序遍历
//右孩子指向上一个节点
TreeNode* ReverseNode(TreeNode* node) {
TreeNode* pre = nullptr;
TreeNode* next = nullptr;
while (node) {
next = node->right;
node->right = pre;
pre = node;
node = next;
}
return pre;
} //逆序打印左孩子的右边界
void PrintNode(TreeNode* node) {
TreeNode* tail = ReverseNode(node);
TreeNode* cur = tail;
while (cur) {
printf("%d ", cur->val);
cur = cur->right;
}
ReverseNode(tail); //还原
} void MorrisPos(TreeNode* root) {
if (root == nullptr)
return;
TreeNode* cur = root;
TreeNode* mostRight = nullptr; while (cur != nullptr) {
mostRight = cur->left; if (mostRight != nullptr) {
while (mostRight->right && mostRight->right != cur) {
mostRight = mostRight->right;
} if (mostRight->right == nullptr) { //第一次到达左子树的最右子树
mostRight->right = cur;
cur = cur->left;
continue;
}
else { //第二次到达左子树的最右子树 mostRight->right == cur;
mostRight->right = nullptr; //逆序打印左子树的右边界
PrintNode(cur->left);
}
}
cur = cur->right;
} PrintNode(root);
}
最新文章
- Getting&Giving
- Sublime一键预览
- js中typeof的使用方法
- Genymotion模拟器环境搭建中的各种坑，终极解决办法
- 内存调试工具Electric Fence
- Java ：List
- Android IOS WebRTC 音视频开发总结（四二）-- webrtc开发者大会
- 用shell求两个文件的差集
- PostgreSQL中使用枚举类型
- SOAP Services for Python
- ASP 生成带日期的随机数
- 转:mysql性能优化的19个要点
- Qt之QTemporaryFile（文件名唯一，且可以自动删除）
- JavaWeb总结(九)—过滤器
- UNIX网络编程——TCP长连接与短连接的区别
- 由一条sql语句想到的子查询优化
- 写一篇博文介绍JSP
- 纯CSS3冒泡动画按钮实现教程
- 第二阶段——个人工作总结DAY01
- MySQL修改root密码的3种方法