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.
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