Usando Morris Traversal, podemos atravesar el árbol sin usar la pila y la recursividad. El algoritmo para Preorder es casi similar al recorrido de Morris para Inorder .
1. .. Si el hijo izquierdo es nulo, imprime los datos del Node actual. Mover al niño derecho.
…. De lo contrario , hace que el hijo derecho del predecesor en orden apunte al Node actual. Se dan dos casos:
……… a) El hijo derecho del predecesor en orden ya apunta al Node actual. Establezca el hijo derecho en NULL. Mover al elemento secundario derecho del Node actual.
……… b) El hijo derecho es NULL. Establézcalo en el Node actual. Imprime los datos del Node actual y muévete al elemento secundario izquierdo del Node actual.
2. ..Iterar hasta que el Node actual no sea NULL.
C++
// C++ program for Morris Preorder traversal #include <bits/stdc++.h> using namespace std; class node { public: int data; node *left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode(int data) { node* temp = new node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // Preorder traversal without recursion and without stack void morrisTraversalPreorder(node* root) { while (root) { // If left child is null, print the current node data. Move to // right child. if (root->left == NULL) { cout<<root->data<<" "; root = root->right; } else { // Find inorder predecessor node* current = root->left; while (current->right && current->right != root) current = current->right; // If the right child of inorder predecessor already points to // this node if (current->right == root) { current->right = NULL; root = root->right; } // If right child doesn't point to this node, then print this // node and make right child point to this node else { cout<<root->data<<" "; current->right = root; root = root->left; } } } } // Function for Standard preorder traversal void preorder(node* root) { if (root) { cout<<root->data<<" "; preorder(root->left); preorder(root->right); } } /* Driver program to test above functions*/ int main() { node* root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->left->left->left = newNode(8); root->left->left->right = newNode(9); root->left->right->left = newNode(10); root->left->right->right = newNode(11); morrisTraversalPreorder(root); cout<<endl; preorder(root); return 0; } //This code is contributed by rathbhupendra
C
// C program for Morris Preorder traversal #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* temp = (struct node*) malloc(sizeof(struct node)); temp->data = data; temp->left = temp->right = NULL; return temp; } // Preorder traversal without recursion and without stack void morrisTraversalPreorder(struct node* root) { while (root) { // If left child is null, print the current node data. Move to // right child. if (root->left == NULL) { printf( "%d ", root->data ); root = root->right; } else { // Find inorder predecessor struct node* current = root->left; while (current->right && current->right != root) current = current->right; // If the right child of inorder predecessor already points to // this node if (current->right == root) { current->right = NULL; root = root->right; } // If right child doesn't point to this node, then print this // node and make right child point to this node else { printf("%d ", root->data); current->right = root; root = root->left; } } } } // Function for Standard preorder traversal void preorder(struct node* root) { if (root) { printf( "%d ", root->data); preorder(root->left); preorder(root->right); } } /* Driver program to test above functions*/ int main() { struct node* root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->left->left->left = newNode(8); root->left->left->right = newNode(9); root->left->right->left = newNode(10); root->left->right->right = newNode(11); morrisTraversalPreorder(root); printf("\n"); preorder(root); return 0; }
Java
// Java program to implement Morris preorder traversal // A binary tree node class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; void morrisTraversalPreorder() { morrisTraversalPreorder(root); } // Preorder traversal without recursion and without stack void morrisTraversalPreorder(Node node) { while (node != null) { // If left child is null, print the current node data. Move to // right child. if (node.left == null) { System.out.print(node.data + " "); node = node.right; } else { // Find inorder predecessor Node current = node.left; while (current.right != null && current.right != node) { current = current.right; } // If the right child of inorder predecessor // already points to this node if (current.right == node) { current.right = null; node = node.right; } // If right child doesn't point to this node, then print // this node and make right child point to this node else { System.out.print(node.data + " "); current.right = node; node = node.left; } } } } void preorder() { preorder(root); } // Function for Standard preorder traversal void preorder(Node node) { if (node != null) { System.out.print(node.data + " "); preorder(node.left); preorder(node.right); } } // Driver programs to test above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.left = new Node(8); tree.root.left.left.right = new Node(9); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(11); tree.morrisTraversalPreorder(); System.out.println(""); tree.preorder(); } } // this code has been contributed by Mayank Jaiswal
Python3
# Python program for Morris Preorder traversal # A binary tree Node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Preorder traversal without # recursion and without stack def MorrisTraversal(root): curr = root while curr: # If left child is null, print the # current node data. And, update # the current pointer to right child. if curr.left is None: print(curr.data, end= " ") curr = curr.right else: # Find the inorder predecessor prev = curr.left while prev.right is not None and prev.right is not curr: prev = prev.right # If the right child of inorder # predecessor already points to # the current node, update the # current with it's right child if prev.right is curr: prev.right = None curr = curr.right # else If right child doesn't point # to the current node, then print this # node's data and update the right child # pointer with the current node and update # the current with it's left child else: print (curr.data, end=" ") prev.right = curr curr = curr.left # Function for Standard preorder traversal def preorfer(root): if root : print(root.data, end = " ") preorfer(root.left) preorfer(root.right) # Driver program to test root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left= Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(10) root.left.right.right = Node(11) MorrisTraversal(root) print("\n") preorfer(root) # This code is contributed by 'Aartee'
C#
// C# program to implement Morris // preorder traversal using System; // A binary tree node public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; } } class GFG { public Node root; public virtual void morrisTraversalPreorder() { morrisTraversalPreorder(root); } // Preorder traversal without // recursion and without stack public virtual void morrisTraversalPreorder(Node node) { while (node != null) { // If left child is null, print the // current node data. Move to right child. if (node.left == null) { Console.Write(node.data + " "); node = node.right; } else { // Find inorder predecessor Node current = node.left; while (current.right != null && current.right != node) { current = current.right; } // If the right child of inorder predecessor // already points to this node if (current.right == node) { current.right = null; node = node.right; } // If right child doesn't point to // this node, then print this node // and make right child point to this node else { Console.Write(node.data + " "); current.right = node; node = node.left; } } } } public virtual void preorder() { preorder(root); } // Function for Standard preorder traversal public virtual void preorder(Node node) { if (node != null) { Console.Write(node.data + " "); preorder(node.left); preorder(node.right); } } // Driver Code public static void Main(string[] args) { GFG tree = new GFG(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.left = new Node(8); tree.root.left.left.right = new Node(9); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(11); tree.morrisTraversalPreorder(); Console.WriteLine(""); tree.preorder(); } } // This code is contributed by Shrikant13
Javascript
<script> // Javascript program to implement Morris // preorder traversal // A binary tree node class Node { constructor(item) { this.data = item; this.left = null; this.right = null; } } var root = null; // Preorder traversal without // recursion and without stack function morrisTraversalPreorder(node) { while (node != null) { // If left child is null, print the // current node data. Move to right child. if (node.left == null) { document.write(node.data + " "); node = node.right; } else { // Find inorder predecessor var current = node.left; while (current.right != null && current.right != node) { current = current.right; } // If the right child of inorder predecessor // already points to this node if (current.right == node) { current.right = null; node = node.right; } // If right child doesn't point to // this node, then print this node // and make right child point to this node else { document.write(node.data + " "); current.right = node; node = node.left; } } } } // Function for Standard preorder traversal function preorder(node) { if (node != null) { document.write(node.data + " "); preorder(node.left); preorder(node.right); } } // Driver Code root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); morrisTraversalPreorder(root); document.write("<br>"); preorder(root); </script>
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