Recorrido de árbol en orden sin recursividad

 

Usar Stack es la forma obvia de atravesar el árbol sin recurrencia. A continuación se muestra un algoritmo para atravesar un árbol binario usando stack. Vea esto para la ejecución paso a paso del algoritmo. 

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack.
     b) Print the popped item, set current = popped_item->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Consideremos el siguiente árbol, por ejemplo.  

C++

// C++ program to print inorder traversal
// using stack.
#include<bits/stdc++.h>
using namespace std;
  
/* A binary tree Node has data, pointer to left child
   and a pointer to right child */
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
    Node (int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
  
/* Iterative function for inorder tree
   traversal */
void inOrder(struct Node *root)
{
    stack<Node *> s;
    Node *curr = root;
  
    while (curr != NULL || s.empty() == false)
    {
        /* Reach the left most Node of the
           curr Node */
        while (curr !=  NULL)
        {
            /* place pointer to a tree node on
               the stack before traversing
              the node's left subtree */
            s.push(curr);
            curr = curr->left;
        }
  
        /* Current must be NULL at this point */
        curr = s.top();
        s.pop();
  
        cout << curr->data << " ";
  
        /* we have visited the node and its
           left subtree.  Now, it's right
           subtree's turn */
        curr = curr->right;
  
    } /* end of while */
}
  
/* Driver program to test above functions*/
int main()
{
  
    /* Constructed binary tree is
              1
            /   \
          2      3
        /  \
      4     5
    */
    struct Node *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);
  
    inOrder(root);
    return 0;
}

C

#include<stdio.h>
#include<stdlib.h>
#define bool int
  
/* A binary tree tNode has data, pointer to left child
   and a pointer to right child */
struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};
  
/* Structure of a stack node. Linked List implementation is used for 
   stack. A stack node contains a pointer to tree node and a pointer to 
   next stack node */
struct sNode
{
  struct tNode *t;
  struct sNode *next;
};
  
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
  
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
  /* set current to root of binary tree */
  struct tNode *current = root;
  struct sNode *s = NULL;  /* Initialize stack s */
  bool done = 0;
  
  while (!done)
  {
    /* Reach the left most tNode of the current tNode */
    if(current !=  NULL)
    {
      /* place pointer to a tree node on the stack before traversing 
        the node's left subtree */
      push(&s, current);                                               
      current = current->left;  
    }
         
    /* backtrack from the empty subtree and visit the tNode 
       at the top of the stack; however, if the stack is empty,
      you are done */
    else                                                              
    {
      if (!isEmpty(s))
      {
        current = pop(&s);
        printf("%d ", current->data);
  
        /* we have visited the node and its left subtree.
          Now, it's right subtree's turn */
        current = current->right;
      }
      else
        done = 1; 
    }
  } /* end of while */  
}     
  
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
  /* allocate tNode */
  struct sNode* new_tNode =
            (struct sNode*) malloc(sizeof(struct sNode));
  
  if(new_tNode == NULL)
  {
     printf("Stack Overflow \n");
     getchar();
     exit(0);
  }            
  
  /* put in the data  */
  new_tNode->t  = t;
  
  /* link the old list off the new tNode */
  new_tNode->next = (*top_ref);   
  
  /* move the head to point to the new tNode */
  (*top_ref)    = new_tNode;
}
  
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
   return (top == NULL)? 1 : 0;
}   
  
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
  struct tNode *res;
  struct sNode *top;
  
  /*If sNode is empty then error */
  if(isEmpty(*top_ref))
  {
     printf("Stack Underflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->t;
     *top_ref = top->next;
     free(top);
     return res;
  }
}
  
/* Helper function that allocates a new tNode with the
   given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;
  
  return(tNode);
}
  
/* 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); 
  
  inOrder(root);
  
  getchar();
  return 0;
}

Java

// non-recursive java program for inorder traversal
import java.util.Stack;
  
/* Class containing left and right child of
current node and key value*/
class Node
{
    int data;
    Node left, right;
  
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
  
/* Class to print the inorder traversal */
class BinaryTree
{
    Node root;
    void inorder()
    {
        if (root == null)
            return;
  
  
        Stack<Node> s = new Stack<Node>();
        Node curr = root;
  
        // traverse the tree
        while (curr != null || s.size() > 0)
        {
  
            /* Reach the left most Node of the
            curr Node */
            while (curr !=  null)
            {
                /* place pointer to a tree node on
                   the stack before traversing
                  the node's left subtree */
                s.push(curr);
                curr = curr.left;
            }
  
            /* Current must be NULL at this point */
            curr = s.pop();
  
            System.out.print(curr.data + " ");
  
            /* we have visited the node and its
               left subtree.  Now, it's right
               subtree's turn */
            curr = curr.right;
        }
    }
  
    public static void main(String args[])
    {
  
        /* creating a binary tree and entering
        the nodes */
        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.inorder();
    }
}

Python3

# Python program to do inorder traversal without recursion
  
# A binary tree node
class Node:
      
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data 
        self.left = None
        self.right = None
  
# Iterative function for inorder tree traversal
def inOrder(root):
      
    # Set current to root of binary tree
    current = root 
    stack = [] # initialize stack
      
    while True:
          
        # Reach the left most Node of the current Node
        if current is not None:
              
            # Place pointer to a tree node on the stack 
            # before traversing the node's left subtree
            stack.append(current)
          
            current = current.left 
  
          
        # BackTrack from the empty subtree and visit the Node
        # at the top of the stack; however, if the stack is 
        # empty you are done
        elif(stack):
            current = stack.pop()
            print(current.data, end=" ") # Python 3 printing
          
            # We have visited the node and its left 
            # subtree. Now, it's right subtree's turn
            current = current.right 
  
        else:
            break
       
    print()
  
# Driver program to test above function
  
""" Constructed binary tree is
            1
          /   \
         2     3
       /  \
      4    5   """
  
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
  
inOrder(root)
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// Non-recursive C# program for inorder traversal
using System;
using System.Collections.Generic;
  
  
/* Class containing left and right child of 
current node and key value*/
public class Node
{
    public int data;
    public Node left, right;
  
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
  
/* Class to print the inorder traversal */
public class BinaryTree
{
    public Node root;
    public virtual void inorder()
    {
        if (root == null)
        {
            return;
        }
  
  
        Stack<Node> s = new Stack<Node>();
        Node curr = root;
  
        // traverse the tree 
        while (curr != null || s.Count > 0)
        {
  
            /* Reach the left most Node of the 
            curr Node */
            while (curr != null)
            {
                /* place pointer to a tree node on 
                   the stack before traversing 
                  the node's left subtree */
                s.Push(curr);
                curr = curr.left;
            }
  
            /* Current must be NULL at this point */
            curr = s.Pop();
  
            Console.Write(curr.data + " ");
  
            /* we have visited the node and its 
               left subtree.  Now, it's right 
               subtree's turn */
            curr = curr.right;
        }
    }
  
    public static void Main(string[] args)
    {
  
        /* creating a binary tree and entering 
        the nodes */
        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.inorder();
    }
}
  
// This code is contributed by Shrikant13

Javascript

<script>
// non-recursive javascript program for inorder traversal
  
/* Class containing left and right child of
current node and key value*/
class Node {
  
     constructor(item) {
        this.data = item;
        this.left = this.right = null;
    }
}
  
/* Class to print the inorder traversal */
  
    var root;
  
    function inorder()
    {
        if (root == null)
            return;
  
        var s = [];
        var curr = root;
  
        // traverse the tree
        while (curr != null || s.length > 0)
        {
  
            /*
             * Reach the left most Node of the curr Node
             */
            while (curr != null)
            {
              
                /*
                 * place pointer to a tree node on the stack before traversing the node's left
                 * subtree
                 */
                s.push(curr);
                curr = curr.left;
            }
  
            /* Current must be NULL at this point */
            curr = s.pop();
  
            document.write(curr.data + " ");
  
            /*
             * we have visited the node and its left subtree. Now, it's right subtree's turn
             */
            curr = curr.right;
        }
    }
  
      
        /*
         * creating a binary tree and entering the nodes
         */
        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);
        inorder();
  
// This code is contributed by umadevi9616
</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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *