二叉树神级遍历-Moris遍历

二叉树的前序，中序，后序遍历，要求时间复杂度为O(n),空间复杂度为0(1)，空间复杂度要求很苛刻，常规递归遍历的控盒件复杂度为树的深度0(h)，对于常规的栈结构递归来说，遍历某个节点之后不能回到上一层的节点，因为没有指向父节点的指针，Morris遍历避免了使用栈结构，让下层有指向上层的指针，但并不是所有的下层结点都有指向上层的指针具体的过程如下： + 当前节点current无左子树，current向右移动 + 当前节点current有右子树，找到左子树最右节点Mostright + mostright的右孩子为空，则mostright的右孩子指向当前节点mostright->right=current,当前节点current向左移动 + mostright的右孩子为当前节点current，则mostright的右孩子指向空mostright->right=null,current向右移动完整代码：

#include <iostream>
using namespace std; 
typedef int dataType;
struct Node  //树的节点
{
	dataType val;
	struct Node *left;
	struct Node *right;
 
	Node(dataType _val):
		val(_val), left(NULL), right(NULL){}
};
 //单纯的moris遍历,不打印任何东西
void Morris(Node *head)
{
	if (head == NULL)
	{
		return;
	}
 
	Node *p1 = head;
	Node *p2 = NULL;
 
	while (p1 != NULL)  
	{
		p2 = p1->left;
		if (p2 != NULL)  //有左子树
		{
			while(p2->right != NULL && p2->right != p1) //有右子树则一直找到右子树的最右孩子
			{
				p2 = p2->right;
			}
			if (p2->right == NULL)  //mostright的右孩子为空
			{
				p2->right = p1;		// 空闲指针
				p1 = p1->left;   //当其节点向左移动
				continue;
			}
			else //mostright的右孩子为为`当前节点current
			{
				p2->right = NULL;  //mostright的右孩子指向空
			}
		}
		cout<<p1->val<<" ";
		p1 = p1->right; //向右移动
	}
}
// Morris中序遍历 (左 -> 根 -> 右)
void MorrisInOrderTraverse(Node *head)
{
	if (head == NULL)
	{
		return;
	}
 
	Node *p1 = head;
	Node *p2 = NULL;
 
	while (p1 != NULL)
	{
		p2 = p1->left;
		if (p2 != NULL)
		{
			while(p2->right != NULL && p2->right != p1)
			{
				p2 = p2->right;
			}
			if (p2->right == NULL)
			{
				p2->right = p1;		// 空闲指针
				p1 = p1->left;
				continue;
			}
			else
			{
				p2->right = NULL;
			}
		}
		cout<<p1->val<<" "; //第二次到达根节点时打印
		p1 = p1->right;
	}
}
 
// Morris前序遍历 (根 -> 左 -> 右)
void MorrisPreOrderTraverse(Node *head)
{
	if (head == NULL)
	{
		return;
	}
 
	Node *p1 = head;
	Node *p2 = NULL;
 
	while (p1 != NULL)
	{
		p2 = p1->left;
		if (p2 != NULL)
		{
			while(p2->right != NULL && p2->right != p1)
			{
				p2 = p2->right;
			}
			if (p2->right == NULL)
			{
				p2->right = p1;		// 空闲指针
				cout<<p1->val<<" ";	// 第一次到达根节点时打印
				p1 = p1->left;
				continue;
			}
			else
			{
				p2->right = NULL;
			}
		}
		else
		{
			cout<<p1->val<<" ";
		}
		p1 = p1->right;
	}
}
 
// 逆序右边界
Node* reverseEdge(Node *head) //将所有右孩子的指向反过来
{
	Node *pre = NULL;
	Node *next = NULL;
 
	while(head != NULL)
	{
		next = head->right;
		head->right = pre;
		pre = head;
		head = next;
	}
 
	return pre;
}
 
// 逆序打印左子树右边界
void printEdge(Node *head)
{
	Node *lastNode = reverseEdge(head); // 先将顺序反过来，再打印
	Node *cur = lastNode;
 
	while (cur != NULL)
	{
		cout<<cur->val<<" ";
		cur = cur->right;
	}
	reverseEdge(lastNode); //再反过来回复原来的样子
}
 
// Morris后序遍历 (左 -> 右 -> 根)
void MorrisPostOrderTraverse(Node *head)
{
	if (head == NULL)
	{
		return;
	}
 
	Node *p1 = head;
	Node *p2 = NULL;
 
	while (p1 != NULL)
	{
		p2 = p1->left;
		if (p2 != NULL)
		{
			while(p2->right != NULL && p2->right != p1)
			{
				p2 = p2->right;
			}
			if (p2->right == NULL)
			{
				p2->right = p1;		// 空闲指针
				p1 = p1->left;
				continue;
			}
			else
			{
				p2->right = NULL;
				printEdge(p1->left);
			}
		}
		p1 = p1->right;
	}
	printEdge(head); //后续遍历逆序打印右子树(可证明)
}
 
void buildBinTree(Node **head) //先序建立二叉树
{
	dataType _val;
	cin>>_val;
 
	if (_val == -1)
	{
		*head = NULL;
	}
	else
	{
		*head = (Node*)malloc(sizeof(Node));
		(*head)->val = _val;
		buildBinTree(&(*head)->left);
		buildBinTree(&(*head)->right);
	}
}
 
int main(void)
{
	Node *head;
	buildBinTree(&head);
	cout<<"前序遍历序列为:";
	MorrisPreOrderTraverse(head);
	cout<<endl;
 
	cout<<"中序遍历序列为:";
	MorrisInOrderTraverse(head);
	cout<<endl;
 
	cout<<"后序遍历序列为:";
	MorrisPostOrderTraverse(head);
	cout<<endl;
 
	return 0;
}

代码参考地址：https://blog.csdn.net/u013575812/article/details/50069991

感谢原作者分享

二叉树神级遍历-Moris遍历

Ferry