Рубрики

Обратный уровень Порядок обхода

Мы обсудили уровень прохождения порядка поста в предыдущем посте. Идея состоит в том, чтобы сначала напечатать последний уровень, затем второй последний уровень и так далее. Как и обход уровня ордера, каждый уровень печатается слева направо.

Пример дерева

Обратный уровень порядка обхода вышеупомянутого дерева «4 5 2 3 1».

Оба метода для обхода порядка нормального уровня могут быть легко изменены для выполнения обхода порядка обратного уровня.

МЕТОД 1 (рекурсивная функция для печати заданного уровня)
Мы можем легко изменить метод 1 нормального уровня обхода порядка . В методе 1 у нас есть метод printGivenLevel (), который печатает номер заданного уровня. Единственное, что нам нужно изменить, это вместо того, чтобы вызывать printGivenLevel () с первого уровня до последнего уровня, мы вызываем его с последнего уровня до первого уровня.

C ++

// Рекурсивная программа C ++ для печати
// ОБРАТНЫЙ обход уровня
#include <bits/stdc++.h>

using namespace std;

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

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

void printGivenLevel(node* root, int level); 

int height(node* node); 

node* newNode(int data); 

  
/ * Функция для печати ОБРАТНАЯ
уровень порядка обхода дерева * /

void reverseLevelOrder(node* root) 

    int h = height(root); 

    int i; 

    for (i=h; i>=1; i--) // ЕДИНСТВЕННАЯ ЛИНИЯ, ОТЛИЧАЮЩАЯСЯ ОТ НОРМАЛЬНОГО ЗАКАЗА УРОВНЯ

        printGivenLevel(root, i); 

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

void printGivenLevel(node* root, int level) 

    if (root == NULL) 

        return

    if (level == 1) 

        cout << root->data << " "

    else if (level > 1) 

    

        printGivenLevel(root->left, level - 1); 

        printGivenLevel(root->right, level - 1); 

    

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

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

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

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

    

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

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

  

    return(Node); 

  
/ * Код водителя * /

int main() 

    node *root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

    root->left->left = newNode(4); 

    root->left->right = newNode(5); 

  

    cout << "Level Order traversal of binary tree is \n"

    reverseLevelOrder(root); 

  

    return 0; 

  

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

С

// Рекурсивная программа на C для печати обхода ордера уровня REVERSE
#include <stdio.h>
#include <stdlib.h>

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

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

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

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

int height(struct node* node);

struct node* newNode(int data);

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

void reverseLevelOrder(struct node* root)

{

    int h = height(root);

    int i;

    for (i=h; i>=1; i--) // ЕДИНСТВЕННАЯ ЛИНИЯ, ОТЛИЧАЮЩАЯСЯ ОТ НОРМАЛЬНОГО ЗАКАЗА УРОВНЯ

        printGivenLevel(root, i);

}

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

void printGivenLevel(struct node* root, int level)

{

    if (root == NULL)

        return;

    if (level == 1)

        printf("%d ", root->data);

    else if (level > 1)

    {

        printGivenLevel(root->left, level-1);

        printGivenLevel(root->right, level-1);

    }

}

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

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

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

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

    root->left->right = newNode(5);

  

    printf("Level Order traversal of binary tree is \n");

    reverseLevelOrder(root);

  

    return 0;

}

Джава

// Рекурсивная Java-программа для печати обратного порядка ордеров

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

class Node 

{

    int data;

    Node left, right;

       

    Node(int item) 

    {

        data = item;

        left = right;

    }

}

   

class BinaryTree 

{

    Node root;

   

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

    void reverseLevelOrder(Node node) 

    {

        int h = height(node);

        int i;

        for (i = h; i >= 1; i--) 

        // ЕДИНСТВЕННАЯ ЛИНИЯ, ОТЛИЧАЮЩАЯСЯ ОТ НОРМАЛЬНОГО ЗАКАЗА УРОВНЯ

        {

            printGivenLevel(node, i);

        }

    }

   

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

    void printGivenLevel(Node node, int level) 

    {

        if (node == null)

            return;

        if (level == 1)

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

        else if (level > 1

        {

            printGivenLevel(node.left, level - 1);

            printGivenLevel(node.right, level - 1);

        }

    }

   

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

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

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

    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 static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

   

        // Давайте создадим деревья, показанные на диаграмме выше

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

           

        System.out.println("Level Order traversal of binary tree is : ");

        tree.reverseLevelOrder(tree.root);

    }

}

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

питон

# Рекурсивная программа Python для печати обратного порядка ордеров уровня

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

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

def reverseLevelOrder(root):

    h = height(root)

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

        printGivenLevel(root,i)

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

def printGivenLevel(root, level):

  

    if root is None:

        return 

    if level ==1 :

        print root.data,

  

    elif level>1:

        printGivenLevel(root.left, level-1)

        printGivenLevel(root.right, level-1)

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

def height(node):

    if node is None:

        return 0 

    else:

  

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

        lheight = height(node.left)

        rheight = height(node.right)

  

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

        if lheight > rheight :

            return lheight + 1

        else:

            return rheight + 1

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

  

print "Level Order traversal of binary tree is"

reverseLevelOrder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// Рекурсивная программа C # для печати
// обратный порядок ордеров

using System;

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

class Node 

    public int data; 

    public Node left, right; 

          

    public Node(int item) 

    

        data = item; 

        left = right; 

    

      

class BinaryTree 


Node root; 

  
/ * Функция для печати ОБРАТНАЯ
уровень порядка обхода дерева * /

void reverseLevelOrder(Node node) 

    int h = height(node); 

    int i; 

    for (i = h; i >= 1; i--) 

      

    // ЕДИНСТВЕННАЯ ЛИНИЯ РАЗЛИЧНАЯ

    // ИЗ НОРМАЛЬНОГО ЗАКАЗА УРОВНЯ

    

        printGivenLevel(node, i); 

    

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

void printGivenLevel(Node node, int level) 

    if (node == null

        return

    if (level == 1) 

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

    else if (level > 1) 

    

        printGivenLevel(node.left, level - 1); 

        printGivenLevel(node.right, level - 1); 

    

  
/ * Вычислить «высоту» дерева -
количество узлов по длине
путь от корневого узла до
дальний листовой узел. * /

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

    

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

static public void Main(String []args) 

    BinaryTree tree = new BinaryTree(); 

  

    // Давайте создадим показанные деревья

    // на схеме выше

    tree.root = new Node(1); 

    tree.root.left = new Node(2); 

    tree.root.right = new Node(3); 

    tree.root.left.left = new Node(4); 

    tree.root.left.right = new Node(5); 

          

    Console.WriteLine("Level Order traversal "

                        "of binary tree is : "); 

    tree.reverseLevelOrder(tree.root); 


      
// Этот код добавлен
// Арнаб Кунду


Выход:

Level Order traversal of binary tree is
4 5 2 3 1

Сложность времени: сложность времени этого метода в наихудшем случае равна O (n ^ 2). Для перекошенного дерева printGivenLevel () занимает O (n) времени, где n — количество узлов в перекошенном дереве. Таким образом, временная сложность printLevelOrder () составляет O (n) + O (n-1) + O (n-2) + .. + O (1), что равно O (n ^ 2).

МЕТОД 2 (Использование очереди и стека)
Метод 2 нормального обхода порядка уровня также может быть легко модифицирован для печати обхода порядка уровня в обратном порядке. Идея состоит в том, чтобы использовать стек, чтобы получить обратный порядок уровней. Если мы выполняем нормальный обход порядка уровней и вместо печати узла помещаем узел в стек, а затем печатаем содержимое стека, мы получаем «5 4 3 2 1» для вышеприведенного примера дерева, но на выходе должно быть «4 5 2 3». 1” . Таким образом, чтобы получить правильную последовательность (слева направо на каждом уровне), мы обрабатываем дочерние элементы узла в обратном порядке, сначала мы помещаем правое поддерево в стек, затем левое поддерево.

C ++

// Программа на C ++ для печати обхода порядка уровня REVERSE с использованием стека и очереди
// Этот подход принят по следующей ссылке
// http://tech-queries.blogspot.in/2008/12/level-order-tree-traversal-in-reverse.html
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

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

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Для двоичного дерева вывести его узлы в порядке, обратном уровню * /

void reverseLevelOrder(node* root)

{

    stack <node *> S;

    queue <node *> Q;

    Q.push(root);

  

    // Делаем что-то вроде обычного порядка обхода порядка уровней. Ниже приведены

    // различия с обходом ордера нормального уровня

    // 1) Вместо того, чтобы печатать узел, мы помещаем узел в стек

    // 2) Правое поддерево посещается перед левым поддеревом

    while (Q.empty() == false)

    {

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

        root = Q.front();

        Q.pop();

        S.push(root);

  

        / * Поставить в очередь правого ребенка * /

        if (root->right)

            Q.push(root->right); // ПРИМЕЧАНИЕ: ПРАВИЛЬНОГО РЕБЕНКА ВЫПОЛНЯЕТСЯ ПЕРЕД ЛЕТОМ

  

        / * Поставить в очередь левого ребенка * /

        if (root->left)

            Q.push(root->left);

    }

  

    // Теперь выталкиваем все элементы из стека по очереди и печатаем их

    while (S.empty() == false)

    {

        root = S.top();

        cout << root->data << " ";

        S.pop();

    }

}

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

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

node* newNode(int data)

{

    node* temp = new node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

  

    return (temp);

}

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

int main()

{

    struct node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(3);

    root->left->left  = newNode(4);

    root->left->right = newNode(5);

    root->right->left  = newNode(6);

    root->right->right = newNode(7);

  

    cout << "Level Order traversal of binary tree is \n";

    reverseLevelOrder(root);

  

    return 0;

}

Джава

// Рекурсивная Java-программа для печати обратного порядка ордеров
// используя стек и очередь

   

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Для двоичного дерева вывести его узлы в порядке, обратном уровню * /

    void reverseLevelOrder(Node node) 

    {

        Stack<Node> S = new Stack();

        Queue<Node> Q = new LinkedList();

        Q.add(node);

   

        // Делаем что-то вроде обычного порядка обхода порядка уровней.

        // различия с нормальным уровнем прохождения порядка

        // 1) Вместо того, чтобы печатать узел, мы помещаем узел в стек

        // 2) Правое поддерево посещается перед левым поддеревом

        while (Q.isEmpty() == false

        {

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

            node = Q.peek();

            Q.remove();

            S.push(node);

   

            / * Поставить в очередь правого ребенка * /

            if (node.right != null)

                // ПРИМЕЧАНИЕ: ПРАВИЛЬНОГО РЕБЕНКА ВЫПОЛНЯЕТСЯ ПЕРЕД ЛЕТОМ

                Q.add(node.right); 

                  

            / * Поставить в очередь левого ребенка * /

            if (node.left != null)

                Q.add(node.left);

        }

   

        // Теперь выталкиваем все элементы из стека по очереди и печатаем их

        while (S.empty() == false

        {

            node = S.peek();

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

            S.pop();

        }

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

   

        // Давайте создадим деревья, показанные на диаграмме выше

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

   

        System.out.println("Level Order traversal of binary tree is :");

        tree.reverseLevelOrder(tree.root);

   

    }

}

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

питон

# Программа Python для печати обхода ордера уровня REVERSE с использованием
# стек и очередь

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  

  
# Учитывая двоичное дерево, выведите его узлы в обратном порядке

def reverseLevelOrder(root):

    S = []

    Q = []

    Q.append(root)

  

    # Делать что-то вроде обычного порядка обхода порядка уровня.

    # Ниже приведены различия с нормальным уровнем порядка

    # обход:

    # 1) Вместо того, чтобы печатать узел, мы помещаем узел в стек

    # 2) Правое поддерево посещается перед левым поддеревом

    while(len(Q) > 0 ):

  

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

        root = Q.pop(0)

        S.append(root)

  

        # Поставить в очередь правильного ребенка

        if (root.right):

            Q.append(root.right)

  

        # Поставить в очередь левого ребенка

        if (root.left):

            Q.append(root.left)

  

    # Теперь вытаскиваем все элементы из стека по очереди и распечатываем их

    while(len(S) > 0):

        root = S.pop()

        print root.data,

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(6)

root.right.right = Node(7)

  

print "Level Order traversal of binary tree is"

reverseLevelOrder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System.Collections.Generic;

using System;

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

public class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        left = right;

    }

}

  

public class BinaryTree 

{

    Node root;

  

    / * Учитывая двоичное дерево, выведите его

    узлы в обратном порядке уровней * /

    void reverseLevelOrder(Node node) 

    {

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

        Queue<Node> Q = new Queue<Node>();

        Q.Enqueue(node);

  

        // Делаем что-то вроде нормального уровня

        // порядок обхода заказа.

        // различия с нормой

        // уровень прохождения заказа

        // 1) Вместо того, чтобы печатать узел, мы помещаем узел в стек

        // 2) Правое поддерево посещается перед левым поддеревом

        while (Q.Count>0) 

        {

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

            node = Q.Peek();

            Q.Dequeue();

            S.Push(node);

  

            / * Поставить в очередь правого ребенка * /

            if (node.right != null)

                // ПРИМЕЧАНИЕ: ПРАВИЛЬНОГО РЕБЕНКА ВЫПОЛНЯЕТСЯ ПЕРЕД ЛЕТОМ

                Q.Enqueue(node.right); 

                  

            / * Поставить в очередь левого ребенка * /

            if (node.left != null)

                Q.Enqueue(node.left);

        }

  

        // Теперь выталкиваем все элементы из стека

        // один за другим и печатаем их

        while (S.Count>0) 

        {

            node = S.Peek();

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

            S.Pop();

        }

    }

  

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

    public static void Main() 

    {

        BinaryTree tree = new BinaryTree();

  

        // Давайте создадим деревья, показанные на диаграмме выше

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

  

        Console.WriteLine("Level Order traversal of binary tree is :");

        tree.reverseLevelOrder(tree.root);

  

    }

}

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


Выход:

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

Сложность времени: O (n), где n — количество узлов в двоичном дереве.

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

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

Обратный уровень Порядок обхода

0.00 (0%) 0 votes