Usando Morris Traversal, podemos atravesar el árbol sin usar la pila y la recursividad. La idea de Morris Traversal se basa en Threaded Binary Tree . En este recorrido, primero creamos enlaces al sucesor Inorder e imprimimos los datos usando estos enlaces, y finalmente revertimos los cambios para restaurar el árbol original.
1. Initialize current as root
2. While current is not NULL
If the current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Find rightmost node in current left subtree OR
node whose right child == current.
If we found right child == current
a) Update the right child as NULL of that node whose right child is current
b) Print current’s data
c) Go to the right, i.e. current = current->right
Else
a) Make current as the right child of that rightmost
node we found; and
b) Go to this left child, i.e., current = current->left
Aunque el árbol se modifica a través del recorrido, vuelve a su forma original después de la finalización. A diferencia del recorrido basado en Stack , no se requiere espacio adicional para este recorrido.
C++
#include <bits/stdc++.h>
using namespace std;
/* A binary tree tNode has data, a pointer to left child
and a pointer to right child */
struct tNode {
int data;
struct tNode* left;
struct tNode* right;
};
/* Function to traverse the binary tree without recursion
and without stack */
void MorrisTraversal(struct tNode* root)
{
struct tNode *current, *pre;
if (root == NULL)
return;
current = root;
while (current != NULL) {
if (current->left == NULL) {
cout << current->data << " ";
current = current->right;
}
else {
/* Find the inorder predecessor of current */
pre = current->left;
while (pre->right != NULL
&& pre->right != current)
pre = pre->right;
/* Make current as the right child of its
inorder predecessor */
if (pre->right == NULL) {
pre->right = current;
current = current->left;
}
/* Revert the changes made in the 'if' part to
restore the original tree i.e., fix the right
child of predecessor */
else {
pre->right = NULL;
cout << current->data << " ";
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* node = new tNode;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode* root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
MorrisTraversal(root);
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
C
#include <stdio.h>
#include <stdlib.h>
/* A binary tree tNode has data, a pointer to left child
and a pointer to right child */
typedef struct tNode {
int data;
struct tNode* left;
struct tNode* right;
}tNode;
/* Function to traverse the binary tree without recursion
and without stack */
void MorrisTraversal(tNode* root)
{
tNode *current, *pre;
if (root == NULL)
return;
current = root;
while (current != NULL) {
if (current->left == NULL) {
printf("%d ", current->data);
current = current->right;
}
else {
/* Find the inorder predecessor of current */
pre = current->left;
while (pre->right != NULL
&& pre->right != current)
pre = pre->right;
/* Make current as the right child of its
inorder predecessor */
if (pre->right == NULL) {
pre->right = current;
current = current->left;
}
/* Revert the changes made in the 'if' part to
restore the original tree i.e., fix the right
child of predecessor */
else {
pre->right = NULL;
printf("%d ", current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
tNode* newtNode(int data)
{
tNode* node = (tNode *)malloc(sizeof(tNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
tNode* root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
MorrisTraversal(root);
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
Java
// Java program to print inorder
// traversal without recursion
// and stack
/* A binary tree tNode has data,
a pointer to left child
and a pointer to right child */
class tNode {
int data;
tNode left, right;
tNode(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
tNode root;
/* Function to traverse a
binary tree without recursion
and without stack */
void MorrisTraversal(tNode root)
{
tNode current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.left == null)
{
System.out.print(current.data + " ");
current = current.right;
}
else {
/* Find the inorder
predecessor of current
*/
pre = current.left;
while (pre.right != null
&& pre.right != current)
pre = pre.right;
/* Make current as right
child of its
* inorder predecessor */
if (pre.right == null) {
pre.right = current;
current = current.left;
}
/* Revert the changes made
in the 'if' part
to restore the original
tree i.e., fix
the right child of predecessor*/
else
{
pre.right = null;
System.out.print(current.data + " ");
current = current.right;
} /* End of if condition pre->right == NULL
*/
} /* End of if condition current->left == NULL*/
} /* End of while */
}
// Driver Code
public static void main(String args[])
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new tNode(1);
tree.root.left = new tNode(2);
tree.root.right = new tNode(3);
tree.root.left.left = new tNode(4);
tree.root.left.right = new tNode(5);
tree.MorrisTraversal(tree.root);
}
}
// This code has been contributed by Mayank
// Jaiswal(mayank_24)
Python 3
# Python program to do Morris inOrder Traversal: # inorder traversal without recursion and without stack class Node: """A binary tree node""" def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def morris_traversal(root): """Generator function for iterative inorder tree traversal""" current = root while current is not None: if current.left is None: yield current.data current = current.right else: # Find the inorder # predecessor of current pre = current.left while pre.right is not None and pre.right is not current: pre = pre.right if pre.right is None: # Make current as right # child of its inorder predecessor pre.right = current current = current.left else: # Revert the changes made # in the 'if' part to restore the # original tree. i.e., fix # the right child of predecessor pre.right = None yield current.data current = current.right # Driver code """ Constructed binary tree is 1 / \ 2 3 / \ 4 5 """ root = Node(1, right=Node(3), left=Node(2, left=Node(4), right=Node(5) ) ) for v in morris_traversal(root): print(v, end=' ') # This code is contributed by Naveen Aili # updated by Elazar Gershuni
C#
// C# program to print inorder traversal
// without recursion and stack
using System;
/* A binary tree tNode has data,
pointer to left child
and a pointer to right child */
class BinaryTree {
tNode root;
public class tNode {
public int data;
public tNode left, right;
public tNode(int item)
{
data = item;
left = right = null;
}
}
/* Function to traverse binary tree without
recursion and without stack */
void MorrisTraversal(tNode root)
{
tNode current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.left == null)
{
Console.Write(current.data + " ");
current = current.right;
}
else {
/* Find the inorder
predecessor of current
*/
pre = current.left;
while (pre.right != null
&& pre.right != current)
pre = pre.right;
/* Make current as right child
of its inorder predecessor */
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
/* Revert the changes made in
if part to restore the original
tree i.e., fix the right child
of predecessor*/
else
{
pre.right = null;
Console.Write(current.data + " ");
current = current.right;
} /* End of if condition pre->right == NULL
*/
} /* End of if condition current->left == NULL*/
} /* End of while */
}
// Driver code
public static void Main(String[] args)
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new tNode(1);
tree.root.left = new tNode(2);
tree.root.right = new tNode(3);
tree.root.left.left = new tNode(4);
tree.root.left.right = new tNode(5);
tree.MorrisTraversal(tree.root);
}
}
// This code has been contributed
// by Arnab Kundu
Javascript
<script>
// JavaScript program to print inorder
// traversal without recursion
// and stack
/* A binary tree tNode has data,
a pointer to left child
and a pointer to right child */
class tNode
{
constructor(item)
{
this.data = item;
this.left = this.right = null;
}
}
let root;
/* Function to traverse a
binary tree without recursion
and without stack */
function MorrisTraversal(root)
{
let current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.left == null)
{
document.write(current.data + " ");
current = current.right;
}
else {
/* Find the inorder
predecessor of current
*/
pre = current.left;
while (pre.right != null
&& pre.right != current)
pre = pre.right;
/* Make current as right
child of its
* inorder predecessor */
if (pre.right == null) {
pre.right = current;
current = current.left;
}
/* Revert the changes made
in the 'if' part
to restore the original
tree i.e., fix
the right child of predecessor*/
else
{
pre.right = null;
document.write(current.data + " ");
current = current.right;
} /* End of if condition pre->right == NULL
*/
} /* End of if condition current->left == NULL*/
} /* End of while */
}
// Driver Code
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
root = new tNode(1);
root.left = new tNode(2);
root.right = new tNode(3);
root.left.left = new tNode(4);
root.left.right = new tNode(5);
MorrisTraversal(root);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
4 2 5 1 3
Complejidad de tiempo: O(n) Si miramos más de cerca, podemos notar que cada borde del árbol se recorre como máximo tres veces. Y en el peor de los casos, se crea y elimina la misma cantidad de bordes adicionales (como el árbol de entrada).
Espacio auxiliar : O (1) ya que solo usa variables constantes
Referencias:
www.liacs.nl/~deutz/DS/september28.pdf
www.scss.tcd.ie/disciplines/software_systems/…/HughGibbonsSlides.pdf
Escriba comentarios si encuentra algún error en el código/algoritmo anterior, o desea compartir más información sobre la pila Morris Inorder Tree Traversal.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA