morris前序遍历

本文主要是介绍morris前序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实现原理：

记作当前节点为cur。

1. 如果cur无左孩子，cur向右移动（cur=cur.right）
2. 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
   1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
   2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

#include<iostream>
#include<vector>
#include<sstream>
using namespace std; struct Node{int value;Node* left;Node* right;Node(){value = 0,left = NULL;right = NULL;}Node(int val):value(val),left(NULL),right(NULL){}};
void morrisPre(Node* head){if(head == NULL){return;}Node* cur = head;Node* mostRight = NULL;while (cur != NULL){mostRight = cur->left;if(mostRight != NULL){while (mostRight->right !=NULL && mostRight->right != cur){mostRight = mostRight->right;}if(mostRight->right == NULL){mostRight->right = cur;cout<<cur->value << " ";cur = cur->left;continue;}else {mostRight->right = NULL;}}else {cout<<cur->value << " ";}cur = cur->right;}cout<<'\n';
}int main(){Node *head = new Node(1);head->left = new Node(2);head->right = new Node(3);head->left->left = new Node(4);head->left->right = new Node(5);head->right->left = new Node(6);head->right->right = new Node(7);morrisPre(head);return 0;
}

 

这篇关于morris前序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---