Рубрики

Уровень порядка обхода в спиральной форме

Напишите функцию для печати обхода дерева по спирали. Для нижестоящего дерева функция должна вывести 1, 2, 3, 4, 5, 6, 7.

Метод 1 (рекурсивный)
Эта проблема может рассматриваться как расширение поста прохождения порядка уровней .
Чтобы распечатать узлы в спиральном порядке, узлы на разных уровнях должны быть напечатаны в чередующемся порядке. Дополнительная булева переменная ltr используется для изменения порядка печати уровней. Если ltr равен 1, то printGivenLevel () печатает узлы слева направо, а справа налево. Значение ltr переключается в каждой итерации, чтобы изменить порядок.

Функция для печати уровня обхода порядка дерева


printSpiral(tree)
  bool ltr = 0;
  for d = 1 to height(tree)
     printGivenLevel(tree, d, ltr);
     ltr ~= ltr /*flip ltr*/

Функция для печати всех узлов на данном уровне

printGivenLevel(tree, level, ltr)
if tree is NULL then return;
if level is 1, then
    print(tree->data);
else if level greater than 1, then
    if(ltr)
        printGivenLevel(tree->left, level-1, ltr);
        printGivenLevel(tree->right, level-1, ltr);
    else
        printGivenLevel(tree->right, level-1, ltr);
        printGivenLevel(tree->left, level-1, ltr);

Ниже приведена реализация вышеуказанного алгоритма.

С

// C программа для рекурсивного обхода порядка уровней в спиральной форме
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node {

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Прототипы функций * /

void printGivenLevel(struct node* root, int level, int ltr);

int height(struct node* node);

struct node* newNode(int data);

  
/ * Функция для печати спирального обхода дерева * /

void printSpiral(struct node* root)

{

    int h = height(root);

    int i;

  

    / * ltr -> Слева направо. Если эта переменная установлена,

      затем данный уровень пройден слева направо. * /

    bool ltr = false;

    for (i = 1; i <= h; i++) {

        printGivenLevel(root, i, ltr);

  

        / * Вернуть букву, чтобы пройти следующий уровень в обратном порядке * /

        ltr = !ltr;

    }

}

  
/ * Печать узлов на заданном уровне * /

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);

        }

    }

}

  
/ * Вычислить «высоту» дерева - количество

    узлы вдоль самого длинного пути от корневого узла

    вплоть до самого дальнего листового узла. * /

int height(struct node* node)

{

    if (node == NULL)

        return 0;

    else {

        / * вычислить высоту каждого поддерева * /

        int lheight = height(node->left);

        int rheight = height(node->right);

  

        / * использовать больший * /

        if (lheight > rheight)

            return (lheight + 1);

        else

            return (rheight + 1);

    }

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

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);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

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-программа для рекурсивного обхода порядка уровней в спиральной форме

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

class Node {

    int data;

    Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

class BinaryTree {

    Node root;

  

    // Функция для печати спирального обхода дерева

    void printSpiral(Node node)

    {

        int h = height(node);

        int i;

  

        / * ltr -> слева направо. Если эта переменная установлена, то

           данный ярлык перемещается слева направо * /

        boolean ltr = false;

        for (i = 1; i <= h; i++) {

            printGivenLevel(node, i, ltr);

  

            / * Вернуть букву, чтобы пройти следующий уровень в обратном порядке * /

            ltr = !ltr;

        }

    }

  

    / * Вычислить «высоту» дерева - количество

    узлы вдоль самого длинного пути от корневого узла

    вплоть до самого дальнего листового узла. * /

    int height(Node node)

    {

        if (node == null)

            return 0;

        else {

  

            / * вычислить высоту каждого поддерева * /

            int lheight = height(node.left);

            int rheight = height(node.right);

  

            / * использовать больший * /

            if (lheight > rheight)

                return (lheight + 1);

            else

                return (rheight + 1);

        }

    }

  

    / * Печать узлов на заданном уровне * /

    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);

            }

        }

    }

    / * Программа драйвера для проверки вышеуказанных функций * /

    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);

    }

}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

python3

# Python3 программа для рекурсивного порядка уровней
# обход в спиральной форме

  

class newNode: 

  

    # Конструкция для создания нового узла

    def __init__(self, key): 

        self.data = key 

        self.left = None

        self.right = None

  
"" "Функция для печати спирального обхода дерева" ""

def printSpiral(root):

  

    h = height(root) 

      

    "" "Слева направо. Если эта переменная

    установлен, то данный уровень пройден

    слева направо. «»»

    ltr = False

    for i in range(1, h + 1):

      

        printGivenLevel(root, i, ltr) 

  

        "" "Вернуть букву, чтобы пройти следующий уровень

           в обратном порядке "" "

        ltr = not ltr 

      
"" "Печать узлов на заданном уровне" ""

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) 

          
"" "Вычислить" высоту "дерева - количество

    узлы вдоль самого длинного пути от корневого узла

    до самого дальнего листового узла.

def height(node):

  

    if (node == None):

        return 0

    else:

      

        "" "вычислить высоту каждого поддерева" ""

        lheight = height(node.left) 

        rheight = height(node.right) 

  

        "" "используйте больший" ""

        if (lheight > rheight):

            return(lheight + 1

        else:

            return(rheight + 1

      
Код водителя

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) 

      
# Этот код добавлен
# от SHUBHAMSINGH10

C #

// C # программа для рекурсивного уровня
// порядок обхода в спиральной форме

using System;

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

public class Node {

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

class GFG {

    public Node root;

  

    // Функция для печати спирали

    // обход дерева

    public virtual void printSpiral(Node node)

    {

        int h = height(node);

        int i;

  

        / * ltr -> слева направо. Если это

        переменная устанавливается тогда

        метка перемещается слева направо * /

        bool ltr = false;

        for (i = 1; i <= h; i++) {

            printGivenLevel(node, i, ltr);

  

            / * Вернуть букву, чтобы пройти дальше

              уровень в обратном порядке * /

            ltr = !ltr;

        }

    }

  

    / * Вычислить «высоту» дерева -

    количество узлов вдоль самого длинного пути

    от корневого узла до самого дальнего

    листовой узел. * /

    public virtual int height(Node node)

    {

        if (node == null) {

            return 0;

        }

        else {

  

            / * вычислить высоту каждого поддерева * /

            int lheight = height(node.left);

            int rheight = height(node.right);

  

            / * использовать больший * /

            if (lheight > rheight) {

                return (lheight + 1);

            }

            else {

                return (rheight + 1);

            }

        }

    }

  

    / * Печать узлов на заданном уровне * /

    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);

            }

        }

    }

  

    // Код драйвера

    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);

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

Spiral Order traversal of binary tree is
1 2 3 4 5 6 7

Сложность времени: в наихудшем случае сложность времени описанным выше методом равна O (n ^ 2) . Наихудший случай возникает в случае перекошенных деревьев.

Метод 2 (итеративный)
Мы можем вывести спиральный порядок ордеров за O (n) время и O (n) лишнее пространство. Идея состоит в том, чтобы использовать два стека. Мы можем использовать одну стопку для печати слева направо и другую стопку для печати справа налево. В каждой итерации у нас есть узлы одного уровня в одном из стеков. Мы печатаем узлы и помещаем узлы следующего уровня в другой стек.

C ++

// C ++ реализация метода времени O (n) для спирального обхода заказа
#include <iostream>
#include <stack>

using namespace std;

  
// Узел двоичного дерева

struct node {

    int data;

    struct node *left, *right;

};

  

void printSpiral(struct node* root)

{

    if (root == NULL)

        return; // проверка NULL

  

    // Создаем два стека для хранения альтернативных уровней

    stack<struct node*> s1; // Для уровней, которые будут напечатаны справа налево

    stack<struct node*> s2; // Для уровней, которые будут напечатаны слева направо

  

    // Вставить первый уровень в первый стек 's1'

    s1.push(root);

  

    // Продолжаем печать, пока любой из стеков имеет несколько узлов

    while (!s1.empty() || !s2.empty()) {

        // Вывести узлы текущего уровня из s1 и нажать узлы

        // следующий уровень до s2

        while (!s1.empty()) {

            struct node* temp = s1.top();

            s1.pop();

            cout << temp->data << " ";

  

            // Обратите внимание, что правое нажатие перед левым

            if (temp->right)

                s2.push(temp->right);

            if (temp->left)

                s2.push(temp->left);

        }

  

        // Выводим узлы текущего уровня из s2 и проталкиваем узлы

        // следующий уровень до s1

        while (!s2.empty()) {

            struct node* temp = s2.top();

            s2.pop();

            cout << temp->data << " ";

  

            // Обратите внимание, что левый толкается перед правым

            if (temp->left)

                s1.push(temp->left);

            if (temp->right)

                s1.push(temp->right);

        }

    }

}

  
// Вспомогательная функция для создания нового узла

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 реализация O (n) подхода уровня порядка
// обход по спирали

  

import java.util.*;

  
// Узел двоичного дерева

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

  

        // Создаем два стека для хранения альтернативных уровней

        // Для уровней, которые будут напечатаны справа налево

        Stack<Node> s1 = new Stack<Node>(); 

        // Для уровней, которые будут напечатаны слева направо

        Stack<Node> s2 = new Stack<Node>(); 

  

        // Вставить первый уровень в первый стек 's1'

        s1.push(node);

  

        // Продолжаем печать, пока любой из стеков имеет несколько узлов

        while (!s1.empty() || !s2.empty()) {

            // Вывести узлы текущего уровня из s1 и нажать узлы

            // следующий уровень до s2

            while (!s1.empty()) {

                Node temp = s1.peek();

                s1.pop();

                System.out.print(temp.data + " ");

  

                // Обратите внимание, что правое нажатие перед левым

                if (temp.right != null)

                    s2.push(temp.right);

  

                if (temp.left != null)

                    s2.push(temp.left);

            }

  

            // Выводим узлы текущего уровня из s2 и проталкиваем узлы

            // следующий уровень до s1

            while (!s2.empty()) {

                Node temp = s2.peek();

                s2.pop();

                System.out.print(temp.data + " ");

  

                // Обратите внимание, что левый толкается перед правым

                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);

    }

}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

python3

# Python3 реализация времени O (n)
# метод спирального обхода заказа

  
# Класс для создания нового узла

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  

def printSpiral(root):

    if (root == None):

        return # Нет проверки

  

    # Создайте два стека для хранения

    # альтернативные уровни

    s1 = [] # Для уровней, которые будут напечатаны

            # справа налево

    s2 = [] # Для уровней, которые будут напечатаны

            # слева направо

  

    # добавить первый уровень в первый стек 's1'

    s1.append(root) 

  

    # Продолжайте печатать, пока любой из

    # стеки имеет несколько узлов

    while not len(s1) == 0 or not len(s2) == 0:

          

        # Печать узлов текущего уровня из s1

        # и добавить узлы следующего уровня к s2

        while not len(s1) == 0:

            temp = s1[-1

            s1.pop() 

            print(temp.data, end = " "

  

            # Обратите внимание, что справа добавляется

            # перед уходом

            if (temp.right): 

                s2.append(temp.right) 

            if (temp.left):

                s2.append(temp.left)

  

        # Вывести узлы текущего уровня из s2

        # и добавить узлы следующего уровня к s1

        while (not len(s2) == 0):

            temp = s2[-1

            s2.pop() 

            print(temp.data, end = " "

  

            # Обратите внимание, что слева добавляется

            # перед правым

            if (temp.left):

                s1.append(temp.left) 

            if (temp.right): 

                s1.append(temp.right)

  
Код водителя

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)

  
# Этот код предоставлен PranchalK

C #

// C # реализация O (n) подхода
// уровень порядка обхода в спиральной форме

using System;

using System.Collections.Generic;

  
// Узел двоичного дерева

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

        }

  

        // Создаем два стека для хранения альтернативных уровней

        Stack<Node> s1 = new Stack<Node>(); // Для уровней, которые будут напечатаны

        // справа налево

        Stack<Node> s2 = new Stack<Node>(); // Для уровней, которые будут напечатаны

        // слева направо

  

        // Вставить первый уровень в первый стек 's1'

        s1.Push(node);

  

        // Продолжаем печатать, пока любой из

        // стеки имеет несколько узлов

        while (s1.Count > 0 || s2.Count > 0) {

            // Печатать узлы текущего уровня из

            // s1 и подтолкнуть узлы следующего уровня к s2

            while (s1.Count > 0) {

                Node temp = s1.Peek();

                s1.Pop();

                Console.Write(temp.data + " ");

  

                // Обратите внимание, что правое нажатие перед левым

                if (temp.right != null) {

                    s2.Push(temp.right);

                }

  

                if (temp.left != null) {

                    s2.Push(temp.left);

                }

            }

  

            // Выводим узлы текущего уровня из s2

            // и подтолкнуть узлы следующего уровня к s1

            while (s2.Count > 0) {

                Node temp = s2.Peek();

                s2.Pop();

                Console.Write(temp.data + " ");

  

                // Обратите внимание, что левый толкается перед правым

                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();

        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);

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

Spiral Order traversal of binary tree is
1 2 3 4 5 6 7

Пожалуйста, напишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанной программе / алгоритме; или если вы хотите поделиться дополнительной информацией о спиральном обходе.

Рекомендуемые посты:

Уровень порядка обхода в спиральной форме

0.00 (0%) 0 votes