Recorrido de orden de nivel en forma de espiral

Escriba una función para imprimir el recorrido en espiral de un árbol. Para el siguiente árbol, la función debe imprimir 1, 2, 3, 4, 5, 6, 7. 
 

spiral_order

C++

// C++ program for recursive level
// order traversal in spiral form
#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;
};
 
// Function prototypes
void printGivenLevel(struct node* root,
                     int level, int ltr);
int height(struct node* node);
struct node* newNode(int data);
 
// Function to print spiral traversal of a tree
void printSpiral(struct node* root)
{
    int h = height(root);
    int i;
 
    // ltr -> Left to Right. If this variable
    // is set,then the given level is traversed
    // from left to right.
    bool ltr = false;
    for(i = 1; i <= h; i++)
    {
        printGivenLevel(root, i, ltr);
 
        // Revert ltr to traverse next
        // level in opposite order
        ltr = !ltr;
    }
}
 
// Print nodes at a given level
void printGivenLevel(struct node* root,
                     int level, int ltr)
{
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
         
    else if (level > 1)
    {
        if (ltr)
        {
            printGivenLevel(root->left,
                            level - 1, ltr);
            printGivenLevel(root->right,
                            level - 1, ltr);
        }
        else
        {
            printGivenLevel(root->right,
                            level - 1, ltr);
            printGivenLevel(root->left,
                            level - 1, ltr);
        }
    }
}
 
// Compute the "height" of a tree -- the number of
// nodes along the longest path from the root node
// down to the farthest leaf node.
int height(struct node* node)
{
    if (node == NULL)
        return 0;
    else
    {
         
        // Compute the height of each subtree
        int lheight = height(node->left);
        int rheight = height(node->right);
 
        // Use the larger one
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}
 
// Helper function that allocates a new
// node with the given data and NULL left
// and right pointers.
struct node* newNode(int data)
{
    node* newnode = new node();
    newnode->data = data;
    newnode->left = NULL;
    newnode->right = NULL;
 
    return (newnode);
}
 
// Driver code
int main()
{
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(6);
    root->right->left = newNode(5);
    root->right->right = newNode(4);
    printf("Spiral Order traversal of "
           "binary tree is \n");
            
    printSpiral(root);
 
    return 0;
}
 
// This code is contributed by samrat2825

C

// C program for recursive level order traversal in spiral form
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
 
/* 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;
};
 
/* Function prototypes */
void printGivenLevel(struct node* root, int level, int ltr);
int height(struct node* node);
struct node* newNode(int data);
 
/* Function to print spiral traversal of a tree*/
void printSpiral(struct node* root)
{
    int h = height(root);
    int i;
 
    /*ltr -> Left to Right. If this variable is set,
      then the given level is traversed from left to right. */
    bool ltr = false;
    for (i = 1; i <= h; i++) {
        printGivenLevel(root, i, ltr);
 
        /*Revert ltr to traverse next level in opposite order*/
        ltr = !ltr;
    }
}
 
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level, int ltr)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1) {
        if (ltr) {
            printGivenLevel(root->left, level - 1, ltr);
            printGivenLevel(root->right, level - 1, ltr);
        }
        else {
            printGivenLevel(root->right, level - 1, ltr);
            printGivenLevel(root->left, level - 1, ltr);
        }
    }
}
 
/* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(struct node* node)
{
    if (node == NULL)
        return 0;
    else {
        /* compute the height of each subtree */
        int lheight = height(node->left);
        int rheight = height(node->right);
 
        /* use the larger one */
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
/* Driver program to test above functions*/
int main()
{
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(6);
    root->right->left = newNode(5);
    root->right->right = newNode(4);
    printf("Spiral Order traversal of binary tree is \n");
    printSpiral(root);
 
    return 0;
}

Java

// Java program for recursive level order traversal in spiral form
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
class Node {
    int data;
    Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    // Function to print the spiral traversal of tree
    void printSpiral(Node node)
    {
        int h = height(node);
        int i;
 
        /* ltr -> left to right. If this variable is set then the
           given label is traversed from left to right */
        boolean ltr = false;
        for (i = 1; i <= h; i++) {
            printGivenLevel(node, i, ltr);
 
            /*Revert ltr to traverse next level in opposite order*/
            ltr = !ltr;
        }
    }
 
    /* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
    int height(Node node)
    {
        if (node == null)
            return 0;
        else {
 
            /* compute the height of each subtree */
            int lheight = height(node.left);
            int rheight = height(node.right);
 
            /* use the larger one */
            if (lheight > rheight)
                return (lheight + 1);
            else
                return (rheight + 1);
        }
    }
 
    /* Print nodes at a given level */
    void printGivenLevel(Node node, int level, boolean ltr)
    {
        if (node == null)
            return;
        if (level == 1)
            System.out.print(node.data + " ");
        else if (level > 1) {
            if (ltr != false) {
                printGivenLevel(node.left, level - 1, ltr);
                printGivenLevel(node.right, level - 1, ltr);
            }
            else {
                printGivenLevel(node.right, level - 1, ltr);
                printGivenLevel(node.left, level - 1, ltr);
            }
        }
    }
    /* Driver program to test the 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(7);
        tree.root.left.right = new Node(6);
        tree.root.right.left = new Node(5);
        tree.root.right.right = new Node(4);
        System.out.println("Spiral order traversal of Binary Tree is ");
        tree.printSpiral(tree.root);
    }
}
 
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python3 program for recursive level order
# traversal in spiral form
 
class newNode:
 
    # Construct to create a newNode
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
""" Function to print spiral traversal of a tree"""
def printSpiral(root):
 
    h = height(root)
     
    """ltr Left to Right. If this variable
    is set, then the given level is traversed
    from left to right. """
    ltr = False
    for i in range(1, h + 1):
     
        printGivenLevel(root, i, ltr)
 
        """Revert ltr to traverse next level
           in opposite order"""
        ltr = not ltr
     
""" Print nodes at a given level """
def printGivenLevel(root, level, ltr):
 
    if(root == None):
        return
    if(level == 1):
        print(root.data, end = " ")
    elif (level > 1):
     
        if(ltr):
            printGivenLevel(root.left, level - 1, ltr)
            printGivenLevel(root.right, level - 1, ltr)
         
        else:
            printGivenLevel(root.right, level - 1, ltr)
            printGivenLevel(root.left, level - 1, ltr)
         
""" Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node."""
def height(node):
 
    if (node == None):
        return 0
    else:
     
        """ compute the height of each subtree """
        lheight = height(node.left)
        rheight = height(node.right)
 
        """ use the larger one """
        if (lheight > rheight):
            return(lheight + 1)
        else:
            return(rheight + 1)
     
# Driver Code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(7)
    root.left.right = newNode(6)
    root.right.left = newNode(5)
    root.right.right = newNode(4)
    print("Spiral Order traversal of binary tree is")
    printSpiral(root)
     
# This code is contributed
# by SHUBHAMSINGH10

C#

// C# program for recursive level
// order traversal in spiral form
using System;
 
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class GFG {
    public Node root;
 
    // Function to print the spiral
    // traversal of tree
    public virtual void printSpiral(Node node)
    {
        int h = height(node);
        int i;
 
        /* ltr -> left to right. If this
        variable is set then the given
        label is traversed from left to right */
        bool ltr = false;
        for (i = 1; i <= h; i++) {
            printGivenLevel(node, i, ltr);
 
            /*Revert ltr to traverse next
              level in opposite order*/
            ltr = !ltr;
        }
    }
 
    /* Compute the "height" of a tree -- the
    number of nodes along the longest path
    from the root node down to the farthest
    leaf node.*/
    public virtual int height(Node node)
    {
        if (node == null) {
            return 0;
        }
        else {
 
            /* compute the height of each subtree */
            int lheight = height(node.left);
            int rheight = height(node.right);
 
            /* use the larger one */
            if (lheight > rheight) {
                return (lheight + 1);
            }
            else {
                return (rheight + 1);
            }
        }
    }
 
    /* Print nodes at a given level */
    public virtual void printGivenLevel(Node node,
                                        int level,
                                        bool ltr)
    {
        if (node == null) {
            return;
        }
        if (level == 1) {
            Console.Write(node.data + " ");
        }
        else if (level > 1) {
            if (ltr != false) {
                printGivenLevel(node.left, level - 1, ltr);
                printGivenLevel(node.right, level - 1, ltr);
            }
            else {
                printGivenLevel(node.right, level - 1, ltr);
                printGivenLevel(node.left, level - 1, ltr);
            }
        }
    }
 
    // 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(7);
        tree.root.left.right = new Node(6);
        tree.root.right.left = new Node(5);
        tree.root.right.right = new Node(4);
        Console.WriteLine("Spiral order traversal "
                          + "of Binary Tree is ");
        tree.printSpiral(tree.root);
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
      // JavaScript program for recursive
    // level order traversal in spiral form
     
    class Node
    {
        constructor(d) {
           this.left = null;
           this.right = null;
           this.data = d;
        }
    }
     
    let root;
   
    // Function to print the spiral traversal of tree
    function printSpiral(node)
    {
        let h = height(node);
        let i;
   
        /* ltr -> left to right. If this variable is set then the
           given label is traversed from left to right */
        let ltr = false;
        for (i = 1; i <= h; i++) {
            printGivenLevel(node, i, ltr);
   
            /*Revert ltr to traverse next level in opposite order*/
            ltr = !ltr;
        }
    }
   
    /* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
    function height(node)
    {
        if (node == null)
            return 0;
        else {
   
            /* compute the height of each subtree */
            let lheight = height(node.left);
            let rheight = height(node.right);
   
            /* use the larger one */
            if (lheight > rheight)
                return (lheight + 1);
            else
                return (rheight + 1);
        }
    }
   
    /* Print nodes at a given level */
    function printGivenLevel(node, level, ltr)
    {
        if (node == null)
            return;
        if (level == 1)
            document.write(node.data + " ");
        else if (level > 1) {
            if (ltr != false) {
                printGivenLevel(node.left, level - 1, ltr);
                printGivenLevel(node.right, level - 1, ltr);
            }
            else {
                printGivenLevel(node.right, level - 1, ltr);
                printGivenLevel(node.left, level - 1, ltr);
            }
        }
    }
     
    root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(7);
    root.left.right = new Node(6);
    root.right.left = new Node(5);
    root.right.right = new Node(4);
    document.write("Spiral order traversal of Binary Tree is " +
    "</br>");
    printSpiral(root);
    
</script>

C++

// C++ implementation of a O(n) time method for spiral order traversal
#include <iostream>
#include <stack>
using namespace std;
 
// Binary Tree node
struct node {
    int data;
    struct node *left, *right;
};
 
void printSpiral(struct node* root)
{
    if (root == NULL)
        return; // NULL check
 
    // Create two stacks to store alternate levels
    stack<struct node*> s1; // For levels to be printed from right to left
    stack<struct node*> s2; // For levels to be printed from left to right
 
    // Push first level to first stack 's1'
    s1.push(root);
 
    // Keep printing while any of the stacks has some nodes
    while (!s1.empty() || !s2.empty()) {
        // Print nodes of current level from s1 and push nodes of
        // next level to s2
        while (!s1.empty()) {
            struct node* temp = s1.top();
            s1.pop();
            cout << temp->data << " ";
 
            // Note that is right is pushed before left
            if (temp->right)
                s2.push(temp->right);
            if (temp->left)
                s2.push(temp->left);
        }
 
        // Print nodes of current level from s2 and push nodes of
        // next level to s1
        while (!s2.empty()) {
            struct node* temp = s2.top();
            s2.pop();
            cout << temp->data << " ";
 
            // Note that is left is pushed before right
            if (temp->left)
                s1.push(temp->left);
            if (temp->right)
                s1.push(temp->right);
        }
    }
}
 
// A utility function to create a new node
struct node* newNode(int data)
{
    struct node* node = new struct node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
int main()
{
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(6);
    root->right->left = newNode(5);
    root->right->right = newNode(4);
    cout << "Spiral Order traversal of binary tree is \n";
    printSpiral(root);
 
    return 0;
}

Java

// Java implementation of an O(n) approach of level order
// traversal in spiral form
 
import java.util.*;
 
// A Binary Tree node
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
 
    static Node root;
 
    void printSpiral(Node node)
    {
        if (node == null)
            return; // NULL check
 
        // Create two stacks to store alternate levels
        // For levels to be printed from right to left
        Stack<Node> s1 = new Stack<Node>();
        // For levels to be printed from left to right
        Stack<Node> s2 = new Stack<Node>();
 
        // Push first level to first stack 's1'
        s1.push(node);
 
        // Keep printing while any of the stacks has some nodes
        while (!s1.empty() || !s2.empty()) {
            // Print nodes of current level from s1 and push nodes of
            // next level to s2
            while (!s1.empty()) {
                Node temp = s1.peek();
                s1.pop();
                System.out.print(temp.data + " ");
 
                // Note that is right is pushed before left
                if (temp.right != null)
                    s2.push(temp.right);
 
                if (temp.left != null)
                    s2.push(temp.left);
            }
 
            // Print nodes of current level from s2 and push nodes of
            // next level to s1
            while (!s2.empty()) {
                Node temp = s2.peek();
                s2.pop();
                System.out.print(temp.data + " ");
 
                // Note that is left is pushed before right
                if (temp.left != null)
                    s1.push(temp.left);
                if (temp.right != null)
                    s1.push(temp.right);
            }
        }
    }
 
    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(7);
        tree.root.left.right = new Node(6);
        tree.root.right.left = new Node(5);
        tree.root.right.right = new Node(4);
        System.out.println("Spiral Order traversal of Binary Tree is ");
        tree.printSpiral(root);
    }
}
 
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python3 implementation of a O(n) time
# method for spiral order traversal
 
# A class to create a new node
class newNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
def printSpiral(root):
    if (root == None):
        return # None check
 
    # Create two stacks to store
    # alternate levels
    s1 = [] # For levels to be printed
            # from right to left
    s2 = [] # For levels to be printed
            # from left to right
 
    # append first level to first stack 's1'
    s1.append(root)
 
    # Keep printing while any of the
    # stacks has some nodes
    while not len(s1) == 0 or not len(s2) == 0:
         
        # Print nodes of current level from s1
        # and append nodes of next level to s2
        while not len(s1) == 0:
            temp = s1[-1]
            s1.pop()
            print(temp.data, end = " ")
 
            # Note that is right is appended
            # before left
            if (temp.right):
                s2.append(temp.right)
            if (temp.left):
                s2.append(temp.left)
 
        # Print nodes of current level from s2
        # and append nodes of next level to s1
        while (not len(s2) == 0):
            temp = s2[-1]
            s2.pop()
            print(temp.data, end = " ")
 
            # Note that is left is appended
            # before right
            if (temp.left):
                s1.append(temp.left)
            if (temp.right):
                s1.append(temp.right)
 
# Driver Code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(7)
    root.left.right = newNode(6)
    root.right.left = newNode(5)
    root.right.right = newNode(4)
    print("Spiral Order traversal of",
                    "binary tree is ")
    printSpiral(root)
 
# This code is contributed by PranchalK

C#

// C# implementation of an O(n) approach of
// level order traversal in spiral form
using System;
using System.Collections.Generic;
 
// A Binary Tree node
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    public static Node root;
 
    public virtual void printSpiral(Node node)
    {
        if (node == null) {
            return; // NULL check
        }
 
        // Create two stacks to store alternate levels
        Stack<Node> s1 = new Stack<Node>(); // For levels to be printed
        // from right to left
        Stack<Node> s2 = new Stack<Node>(); // For levels to be printed
        // from left to right
 
        // Push first level to first stack 's1'
        s1.Push(node);
 
        // Keep printing while any of the
        // stacks has some nodes
        while (s1.Count > 0 || s2.Count > 0) {
            // Print nodes of current level from
            // s1 and push nodes of next level to s2
            while (s1.Count > 0) {
                Node temp = s1.Peek();
                s1.Pop();
                Console.Write(temp.data + " ");
 
                // Note that is right is pushed before left
                if (temp.right != null) {
                    s2.Push(temp.right);
                }
 
                if (temp.left != null) {
                    s2.Push(temp.left);
                }
            }
 
            // Print nodes of current level from s2
            // and push nodes of next level to s1
            while (s2.Count > 0) {
                Node temp = s2.Peek();
                s2.Pop();
                Console.Write(temp.data + " ");
 
                // Note that is left is pushed before right
                if (temp.left != null) {
                    s1.Push(temp.left);
                }
                if (temp.right != null) {
                    s1.Push(temp.right);
                }
            }
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        BinaryTree.root = new Node(1);
        BinaryTree.root.left = new Node(2);
        BinaryTree.root.right = new Node(3);
        BinaryTree.root.left.left = new Node(7);
        BinaryTree.root.left.right = new Node(6);
        BinaryTree.root.right.left = new Node(5);
        BinaryTree.root.right.right = new Node(4);
        Console.WriteLine("Spiral Order traversal of Binary Tree is ");
        tree.printSpiral(root);
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
    // Javascript implementation of an O(n) approach of
    // level order traversal in spiral form
     
    // A Binary Tree node
    class Node
    {
        constructor(item) {
           this.left = null;
           this.right = null;
           this.data = item;
        }
    }
     
    let root;
  
    function printSpiral(node)
    {
        if (node == null) {
            return; // NULL check
        }
  
        // Create two stacks to store alternate levels
        let s1 = []; // For levels to be printed
        // from right to left
        let s2 = []; // For levels to be printed
        // from left to right
  
        // Push first level to first stack 's1'
        s1.push(node);
  
        // Keep printing while any of the
        // stacks has some nodes
        while (s1.length > 0 || s2.length > 0) {
            // Print nodes of current level from
            // s1 and push nodes of next level to s2
            while (s1.length > 0) {
                let temp = s1[s1.length - 1];
                s1.pop();
                document.write(temp.data + " ");
  
                // Note that is right is pushed before left
                if (temp.right != null) {
                    s2.push(temp.right);
                }
  
                if (temp.left != null) {
                    s2.push(temp.left);
                }
            }
  
            // Print nodes of current level from s2
            // and push nodes of next level to s1
            while (s2.length > 0) {
                let temp = s2[s2.length - 1];
                s2.pop();
                document.write(temp.data + " ");
  
                // Note that is left is pushed before right
                if (temp.left != null) {
                    s1.push(temp.left);
                }
                if (temp.right != null) {
                    s1.push(temp.right);
                }
            }
        }
    }
     
    root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(7);
    root.left.right = new Node(6);
    root.right.left = new Node(5);
    root.right.right = new Node(4);
    document.write("Spiral Order traversal of Binary Tree is " + "</br>");
    printSpiral(root);
 
// Thiscode is contributed by decode2207.
</script>

C++

// C++ implementation of above approach
#include <iostream>
#include <stack>
using namespace std;
 
// Binary Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
void spiralPrint(struct Node* root)
{
    // Declare a deque
    deque<Node*> dq;
 
    // Insert the root of the tree into the deque
    dq.push_back(root);
 
    // Create a  variable that will switch in each iteration
    bool reverse = true;
 
    // Start iteration
    while (!dq.empty()) {
 
        // Save the size of the deque here itself, as in
        // further steps the size of deque will frequently
        // change
        int n = dq.size();
 
        // If we are printing left to right
        if (!reverse) {
 
            // Iterate from left to right
            for (int i = 0; i < n; i++) {
 
                // Insert the child from the back of the
                // deque Left child first
                if (dq.front()->left != NULL)
                    dq.push_back(dq.front()->left);
 
                if (dq.front()->right != NULL)
                    dq.push_back(dq.front()->right);
 
                // Print the current processed element
                cout << dq.front()->key << "  ";
                dq.pop_front();
            }
            // Switch reverse for next traversal
            reverse = !reverse;
        }
        else {
 
            // If we are printing right to left
            // Iterate the deque in reverse order and insert
            // the children from the front
            while (n--) {
                // Insert the child in the front of the
                // deque Right child first
                if (dq.back()->right != NULL)
                    dq.push_front(dq.back()->right);
 
                if (dq.back()->left != NULL)
                    dq.push_front(dq.back()->left);
 
                // Print the current processed element
                  cout << dq.back()->key << "  ";
                  dq.pop_back();
            }
            // Switch reverse for next traversal
            reverse = !reverse;
        }
    }
}
 
// A utility function to create a new node
struct Node* newNode(int data)
{
    struct Node* node = new struct Node;
    node->key = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(6);
    root->right->left = newNode(5);
    root->right->right = newNode(4);
    cout << "Spiral Order traversal of binary tree is :\n";
    spiralPrint(root);
 
    return 0;
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
 
class GFG {
   
  //Defining Node class
  static class Node {
 
    int key;
    Node left;
    Node right;
 
    public Node(int key) {
        this.key = key;
    }
}
   
  //Class to construct the tree
  static class MyTree {
 
    public MyTree(){};
 
    public Node root;
 
}
   
  //Function that prints the tree in spiral fashion
  public static void spiralPrint(Node root){
 
        //Declare a deque
        Deque<Node> dq = new ArrayDeque<>();
         
        //Insert the root of the tree into the deque
        dq.offer(root);
         
        //Create a  variable that will switch in each iteration
        boolean reverse = true;
 
        //Start iteration
        while (!dq.isEmpty()){
             
              //Save the size of the deque here itself, as in further steps the size
              //of deque will frequently change
            int n = dq.size();
             
              //If we are printing left to right
            if(!reverse){
               
              //Iterate from left to right
                for (int i =0; i < n; i++){
                         
                  //Insert the child from the back of the deque
                  //Left child first
                    if (dq.peekFirst().left  != null)
                        dq.offerLast(dq.peekFirst().left);
                   
                    if (dq.peekFirst().right != null)
                        dq.offerLast(dq.peekFirst().right);
                   
                  //Print the current processed element
                    System.out.print(dq.pollFirst().key + "  ");
                   
                   
                }
                //Switch reverse for next traversal
                reverse = !reverse;
               
            }else{
 
              //If we are printing right to left
              //Iterate the deque in reverse order and insert the children
              //from the front
                while (n-- >0){
                    //Insert the child in the front of the deque
                    //Right child first
                    if (dq.peekLast().right != null)
                        dq.offerFirst(dq.peekLast().right);
                   
                    if (dq.peekLast().left != null)
                        dq.offerFirst(dq.peekLast().left);
 
                  //Print the current processed element
                    System.out.print(dq.pollLast().key + "  ");
 
                }
                //Switch reverse for next traversal
                reverse = !reverse;
                 
            }
        }
    }
   
   
    public static void main (String[] args) {
        MyTree mt = new MyTree();
        mt.root = new Node(1);
        mt.root.left = new Node(2);
        mt.root.right = new Node(3);
        mt.root.left.left = new Node(7);
        mt.root.left.right = new Node(6);
        mt.root.right.left = new Node(5);
        mt.root.right.right = new Node(4);
         
 
      System.out.println("Spiral Order Traversal Of The Tree is :");
        spiralPrint(mt.root);
    }
}
 
//This code has been contributed by Abhishek Kumar Sah(kumarabhisheksah98)

Python3

# Python3 implementation of above approach
 
# A class to create a new node
from collections import deque
 
 
class newNode:
    def __init__(self, data):
        self.key = data
        self.left = None
        self.right = None
 
 
def spiralPrint(root):
    # Declare a deque
    dq = deque()
 
    # Insert the root of the tree into the deque
    dq.append(root)
 
    # Create a  variable that will switch in each iteration
    reverse = True
 
    # Start iteration
    while (len(dq)):
 
        # Save the size of the deque here itself, as in further steps the size
        # of deque will frequently change
        n = len(dq)
 
        # If we are printing left to right
        if(not reverse ):
 
            # Iterate from left to right
            for i in range(n):
 
                # Insert the child from the back of the deque
                # Left child first
                if (dq[0].left != None):
                    dq.append(dq[0].left)
 
                if (dq[0].right != None):
                    dq.append(dq[0].right)
 
                # Print the current processed element
                print(dq[0].key ,end= "  ")
                dq.popleft();
 
            # Switch reverse for next traversal
            reverse = not reverse
        else:
 
            # If we are printing right to left
            # Iterate the deque in reverse order and insert the children
            # from the front
            while (n > 0):
                n-=1
                # Insert the child in the front of the deque
                # Right child first
                if (dq[-1].right != None):
                    dq.appendleft(dq[-1].right)
 
                if (dq[-1].left != None):
                    dq.appendleft(dq[-1].left)
 
                # Print the current processed element
                print(dq[-1].key , end="  ")
                dq.pop()
             
            # Switch reverse for next traversal
            reverse = not reverse
 
# Driver Code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(7)
    root.left.right = newNode(6)
    root.right.left = newNode(5)
    root.right.right = newNode(4)
    print("Spiral Order traversal of",
          "binary tree is :")
    spiralPrint(root)
 
# This code is contributed by Abhijeet Kumar(abhijeet19403)

C#

// C# implementation of above approach
 
using System;
using System.Collections.Generic;
 
// A Binary Tree node
public class Node {
    public int key;
    public Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    public static Node root;
    // Function that prints the tree in spiral fashion
    public virtual void spiralPrint(Node root)
    {
 
        // Declare a deque
        List<Node> dq = new List<Node>();
 
        // Insert the root of the tree into the deque
        dq.Add(root);
 
        // Create a  variable that will switch in each
        // iteration
        bool reverse = true;
 
        // Start iteration
        while (dq.Count != 0) {
 
            // Save the size of the deque here itself, as in
            // further steps the size of deque will
            // frequently change
            int n = dq.Count;
 
            // If we are printing left to right
            if (!reverse) {
 
                // Iterate from left to right
                for (int i = 0; i < n; i++) {
 
                    // Insert the child from the back of the
                    // deque Left child first
                    if (dq[0].left != null)
                        dq.Add(dq[0].left);
 
                    if (dq[0].right != null)
                        dq.Add(dq[0].right);
 
                    // Print the current processed element
                    Console.Write(dq[0].key + "  ");
                    dq.RemoveAt(0);
                }
                // Switch reverse for next traversal
                reverse = !reverse;
            }
            else {
 
                // If we are printing right to left
                // Iterate the deque in reverse order and
                // insert the children from the front
                while (n-- > 0) {
                    // Insert the child in the front of the
                    // deque Right child first
                    if (dq[dq.Count - 1].right != null)
                        dq.Insert(0,
                                  dq[dq.Count - 1].right);
 
                    if (dq[dq.Count - 1].left != null)
                        dq.Insert(0, dq[dq.Count - 1].left);
                    // Print the current processed element
                    Console.Write(dq[dq.Count - 1].key
                                  + "  ");
 
                    dq.RemoveAt(dq.Count - 1);
                }
                // Switch reverse for next traversal
                reverse = !reverse;
            }
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        BinaryTree.root = new Node(1);
        BinaryTree.root.left = new Node(2);
        BinaryTree.root.right = new Node(3);
        BinaryTree.root.left.left = new Node(7);
        BinaryTree.root.left.right = new Node(6);
        BinaryTree.root.right.left = new Node(5);
        BinaryTree.root.right.right = new Node(4);
        Console.WriteLine(
            "Spiral Order traversal of Binary Tree is :");
        tree.spiralPrint(root);
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

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 *