Morris traverse

Les méthodes traditionnelles de traversée, qu'elles soient implémentées Récursivement ou en pile,La complexité spatiale de sa traversée estO(N),EtMorrisLa traversée peut être faite avec seulementO(1)La complexité spatiale de,Et sa complexité temporelle est aussiO(N).

---

MorrisIntroduction à la traversée

MorrisLa traversée utilise un grand nombre de pointeurs libres dans l'arbre d'origine,Pour économiser de l'espace.

MorrisLa règle de traversée est：
Supposons que le noeud actuelcur,Au débutcurJusqu'à la position du noeud de tête

1. SicurPas de gauche.,curÀ droite（cur=cur->right）
2. SicurIl y a un enfant de gauche.,Trouver le noeud le plus à droite sur le Sous - arbre gauchemostRight
   1).SimostRightLe pointeur droit de,Faites - le pointer verscur,Et puiscurÀ gauche（cur=cur->left）
   2).SimostRightLe pointeur droit verscur,Faites - le pointer versnullptr,Et puiscurÀ droite(cur=cur->right)
3. curVide,Arrêter la traversée.

class Node
{
    
public:
	Node(int _value)
	{
    
		value = _value;
		left = nullptr;
		right = nullptr;
	}

	int value;
	Node* left;
	Node* right;
};
void morris(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRightPourcur Le noeud le plus à droite de l'arbre de gauche 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//SicurPas d'arbre gauche,Alorscur Va se déplacer directement à droite 
		if (mostRight != nullptr)
		{
    
			//Cherche.cur Le noeud le plus à droite de l'arbre de gauche , Quand vide ou égal à curArrêt
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//Si vide, Description première fois au noeud le plus à droite , Pointez le pointeur vers cur
			//Et puiscur Vers le Sous - arbre gauche 
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//En ce momentmostRight->right == cur
			// Description deuxième arrivée au noeud , Restaurer le pointeur pour ce noeud 
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		cur = cur->right;
	}
}

MorrisTraversée préalable

L'ordre de traversée de l'ordre précédent est à gauche et à droite de la racine ,Parce queMorris .La traversée peut atteindre un noeud deux fois , Donc nous devons imprimer la première fois que nous atteignons le noeud .

void morrisPre(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRightPourcur Le noeud le plus à droite de l'arbre de gauche 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//SicurPas d'arbre gauche,Alorscur Va se déplacer directement à droite 
		if (mostRight != nullptr)
		{
    
			//Cherche.cur Le noeud le plus à droite de l'arbre de gauche , Quand vide ou égal à curArrêt
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//Si vide, Description première fois au noeud le plus à droite , Pointez le pointeur vers cur
			//Et puiscur Vers le Sous - arbre gauche 
			if (mostRight->right == nullptr)
			{
    
				cout << cur->value << endl;
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//En ce momentmostRight->right == cur
			//DescriptionmostRight Deuxième arrivée au noeud , Restaurer le pointeur pour ce noeud 
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		//cur Il n'y a pas d'arbre gauche ,Impression directecur,Et bouge.cur Sur le Sous - arbre droit 
		else
		{
    
			cout << cur->value << endl;
		}
		cur = cur->right;
	}
}

MorrisTraversée de l'ordre moyen

La traversée du milieu suit le principe de la racine gauche et de la droite ,Pour un noeud,Imprimer à la deuxième arrivée.

void morrisIn(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRightPourcur Le noeud le plus à droite de l'arbre de gauche 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//SicurPas d'arbre gauche,Alorscur Va se déplacer directement à droite 
		if (mostRight != nullptr)
		{
    
			//Cherche.cur Le noeud le plus à droite de l'arbre de gauche , Quand vide ou égal à curArrêt
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//Si vide, Description première fois au noeud le plus à droite , Pointez le pointeur vers cur
			//Et puiscur Vers le Sous - arbre gauche 
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//En ce momentmostRight->right == cur
			//DescriptionmostRight Deuxième arrivée au noeud , Restaurer le pointeur pour ce noeud 
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		// Parce que la première fois mostRight->right = cur;
		// Donc le Sous - arbre gauche cur Ce noeud peut être atteint deux fois , Imprimer la deuxième fois 
		cout << cur->value << endl;
		
		cur = cur->right;
	}
}

MorrisTraversée postérieure

La traversée postérieure est l'ordre des racines gauche et droite , Parce que nous n'avons pas de pointeur parent , Il n'est donc pas possible d'imprimer du sous - arbre droit au noeud racine . Sauf si vous utilisez la structure de la pile dans l'ordre inverse , Mais cela va à l'encontre de la complexité spatiale de O（1）L'intention initiale.

Donc,, On doit retourner la liste , Pointez le pointeur droit vers son noeud parent , Changez - le après l'impression .

//Retourner la liste des liens
Node* reverseEdge(Node* from)
{
    
	Node* pre = nullptr;
	Node* next = nullptr;
	while (from != nullptr)
	{
    
		next = from->right;
		from->right = pre;
		pre = from;
		from = next;
	}
	return pre;
}
void printEdge(Node* head)
{
    
	// Considérez l'extrême droite du sous - arbre droit comme une liste liée 
	//Retournez la liste
	Node* tail = reverseEdge(head);
	Node* cur = tail;
	while (cur != nullptr)
	{
    
		cout << cur->value << endl;
		cur = cur->right;
	}
	// La liste est retournée 
	reverseEdge(tail);
}
void morrisPos(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRightPourcur Le noeud le plus à droite de l'arbre de gauche 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//SicurPas d'arbre gauche,Alorscur Va se déplacer directement à droite 
		if (mostRight != nullptr)
		{
    
			//Cherche.cur Le noeud le plus à droite de l'arbre de gauche , Quand vide ou égal à curArrêt
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//Si vide, Description première fois au noeud le plus à droite , Pointez le pointeur vers cur
			//Et puiscur Vers le Sous - arbre gauche 
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//En ce momentmostRight->right == cur
			// Description deuxième arrivée au noeud , Restaurer le pointeur pour ce noeud 
			else
			{
    
				mostRight->right = nullptr;
				// Imprimer la bordure droite du sous - arbre gauche d'un arbre dans l'ordre inverse 
				printEdge(cur->left);
			}
		}

		cur = cur->right;
	}
	//Imprimer la limite droite de l'arbre entier dans l'ordre inverse
	printEdge(head);
}