Рубрики

Распечатать двоичное дерево в вертикальном порядке | Комплект 1

Учитывая двоичное дерево, выведите его вертикально. В следующем примере показан обход вертикального порядка.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
              
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9 

Идея состоит в том, чтобы пройти дерево один раз и получить минимальное и максимальное горизонтальное расстояние относительно корня. Для дерева, показанного выше, минимальное расстояние равно -2 (для узла со значением 4), а максимальное расстояние равно 3 (для узла со значением 9).
Получив максимальное и минимальное расстояния от корня, мы выполняем итерацию для каждой вертикальной линии на расстоянии от минимума до максимума от корня, а также для каждой вертикальной линии пересекаем дерево и выводим узлы, которые лежат на этой вертикальной линии.

Алгоритм:

// min --> Minimum horizontal distance from root
// max --> Maximum horizontal distance from root
// hd  --> Horizontal distance of current node from root 
findMinMax(tree, min, max, hd)
     if tree is NULL then return;
 
     if hd is less than min then
           min = hd;
     else if hd is greater than max then
          *max = hd;
 
     findMinMax(tree->left, min, max, hd-1);
     findMinMax(tree->right, min, max, hd+1);

 
printVerticalLine(tree, line_no, hd)
     if tree is NULL then return;
 
     if hd is equal to line_no, then
           print(tree->data);
     printVerticalLine(tree->left, line_no, hd-1);
     printVerticalLine(tree->right, line_no, hd+1); 

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

C ++

#include <iostream>

using namespace std;

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

struct Node

{

    int data;

    struct Node *left, *right;

};

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

Node* newNode(int data)

{

    Node *temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Полезная функция для нахождения минимального и максимального расстояния по отношению
// для root.

void findMinMax(Node *node, int *min, int *max, int hd)

{

    // Базовый вариант

    if (node == NULL) return;

  

    // Обновляем мин и макс

    if (hd < *min)  *min = hd;

    else if (hd > *max) *max = hd;

  

    // Повтор для левого и правого поддеревьев

    findMinMax(node->left, min, max, hd-1);

    findMinMax(node->right, min, max, hd+1);

}

  
// Вспомогательная функция для печати всех узлов с заданным line_no.
// hd - горизонтальное расстояние текущего узла относительно корня.

void printVerticalLine(Node *node, int line_no, int hd)

{

    // Базовый вариант

    if (node == NULL) return;

  

    // Если этот узел находится на заданном номере строки

    if (hd == line_no)

        cout << node->data << " ";

  

    // Повтор для левого и правого поддеревьев

    printVerticalLine(node->left, line_no, hd-1);

    printVerticalLine(node->right, line_no, hd+1);

}

  
// Основная функция, которая печатает данное двоичное дерево в
// вертикальный порядок

void verticalOrder(Node *root)

{

    // Находим минимальное и максимальное расстояния с пересмотром на корень

    int min = 0, max = 0;

    findMinMax(root, &min, &max, 0);

  

    // Перебираем все возможные вертикальные линии, начиная

    // от самой левой строки и печатаем узлы построчно

    for (int line_no = min; line_no <= max; line_no++)

    {

        printVerticalLine(root, line_no, 0);

        cout << endl;

    }

}

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

int main()

{

    // Создать двоичное дерево, показанное на рисунке выше

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

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

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

  

    cout << "Vertical order traversal is \n";

    verticalOrder(root);

  

    return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class Values 

{

    int max, min;

}

   

class BinaryTree 

{

    Node root;

    Values val = new Values();

   

    // Полезная функция для нахождения минимального и максимального расстояния по отношению

    // для root.

    void findMinMax(Node node, Values min, Values max, int hd) 

    {

        // Базовый вариант

        if (node == null

            return;

   

        // Обновляем мин и макс

        if (hd < min.min) 

            min.min = hd;

        else if (hd > max.max) 

            max.max = hd;

   

        // Повтор для левого и правого поддеревьев

        findMinMax(node.left, min, max, hd - 1);

        findMinMax(node.right, min, max, hd + 1);

    }

   

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

    // hd - горизонтальное расстояние текущего узла относительно корня.

    void printVerticalLine(Node node, int line_no, int hd) 

    {

        // Базовый вариант

        if (node == null

            return;

   

        // Если этот узел находится на заданном номере строки

        if (hd == line_no) 

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

   

        // Повтор для левого и правого поддеревьев

        printVerticalLine(node.left, line_no, hd - 1);

        printVerticalLine(node.right, line_no, hd + 1);

    }

   

    // Основная функция, которая печатает данное двоичное дерево в

    // вертикальный порядок

    void verticalOrder(Node node) 

    {

        // Находим минимальное и максимальное расстояния с пересмотром на корень

        findMinMax(node, val, val, 0);

   

        // Перебираем все возможные вертикальные линии, начиная

        // от самой левой строки и печатаем узлы построчно

        for (int line_no = val.min; line_no <= val.max; line_no++) 

        {

            printVerticalLine(node, line_no, 0);

            System.out.println("");

        }

    }

   

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

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

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

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

   

        System.out.println("vertical order traversal is :");

        tree.verticalOrder(tree.root);

    }

}

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

питон

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

  
# Двоичное дерево

class Node:

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

    def __init__(self, key):

        self.data = key 

        self.left = None

        self.right = None

  
# Функция полезности, чтобы найти минимальное и максимальное расстояния с
# уважение к корню

def findMinMax(node, minimum, maximum, hd):

      

    # Базовый вариант

    if node is None:

        return 

      

    # Обновление мин и макс

    if hd < minimum[0] :

        minimum[0] = hd

    elif hd > maximum[0]:

        maximum[0] = hd

  

    # Повтор для левого и правого поддеревьев

    findMinMax(node.left, minimum, maximum, hd-1)

    findMinMax(node.right, minimum, maximum, hd+1)

  
# Служебная функция для печати всех узлов на заданном line_no
# hd - горизонтальное расстояние текущего узла относительно корня

def printVerticalLine(node, line_no, hd):

      

    # Базовый вариант

    if node is None:

        return

      

    # Если этот узел находится на заданном номере строки

    if hd == line_no:

        print node.data,

  

    # Повтор для левого и правого поддеревьев

    printVerticalLine(node.left, line_no, hd-1)

    printVerticalLine(node.right, line_no, hd+1)

  

def verticalOrder(root):

      

    # Найти минимальное и максимальное расстояния по отношению к корню

    minimum = [0]

    maximum = [0]

    findMinMax(root, minimum, maximum, 0)

  

    # Перебирать все возможные строки, начиная

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

    for line_no in range(minimum[0], maximum[0]+1):

        printVerticalLine(root, line_no, 0)

        print 

           

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

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)

root.right.left.right = Node(8)

root.right.right.right = Node(9)

  

print "Vertical order traversal is"

verticalOrder(root)

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

C #

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

using System;

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

public class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

class Values 

{

    public int max, min;

}

  

public class BinaryTree 

{

    Node root;

    Values val = new Values();

  

    // Полезная функция, чтобы найти мин и

    // максимальные расстояния относительно корня.

    void findMinMax(Node node, Values min,

                    Values max, int hd) 

    {

        // Базовый вариант

        if (node == null

            return;

  

        // Обновляем мин и макс

        if (hd < min.min) 

            min.min = hd;

        else if (hd > max.max) 

            max.max = hd;

  

        // Повтор для левого и правого поддеревьев

        findMinMax(node.left, min, max, hd - 1);

        findMinMax(node.right, min, max, hd + 1);

    }

  

    // Утилита для печати

    // все узлы на заданном line_no.

    // hd - горизонтальное расстояние

    // текущий узел относительно корня.

    void printVerticalLine(Node node, 

                            int line_no, int hd) 

    {

        // Базовый вариант

        if (node == null

            return;

  

        // Если этот узел находится на заданном номере строки

        if (hd == line_no) 

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

  

        // Повтор для левого и правого поддеревьев

        printVerticalLine(node.left, line_no, hd - 1);

        printVerticalLine(node.right, line_no, hd + 1);

    }

  

    // Основная функция, которая печатает

    // данное двоичное дерево в вертикальном порядке

    void verticalOrder(Node node) 

    {

        // Находим минимальное и максимальное расстояния с пересмотром на корень

        findMinMax(node, val, val, 0);

  

        // Перебираем все возможное

        // вертикальные линии, начинающиеся с

        // крайняя левая строка и печатаемые узлы построчно

        for (int line_no = val.min; line_no <= val.max; line_no++) 

        {

            printVerticalLine(node, line_no, 0);

            Console.WriteLine("");

        }

    }

  

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

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

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

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

  

        Console.WriteLine("vertical order traversal is :");

        tree.verticalOrder(tree.root);

    }

}

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


Выход:

Vertical order traversal is
4
2
1 5 6
3 8
7
9

Сложность времени: временная сложность вышеописанного алгоритма составляет O (w * n), где w — ширина двоичного дерева, а n — количество узлов в двоичном дереве. В худшем случае значение w может быть O (n) (рассмотрим, например, полное дерево), а сложность по времени может стать O (n 2 ).

Эту проблему можно решить более эффективно, используя методику, рассмотренную в этом посте. Вскоре мы обсудим полный алгоритм и реализацию более эффективного метода.

Эта статья предоставлена Шалки Агарвал . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Распечатать двоичное дерево в вертикальном порядке | Комплект 1

0.00 (0%) 0 votes