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

#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 # программа для печати двоичного дерева в обратном порядке

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 * /