Роздрукуйте двійкове дерево у вертикальному порядку


Рівень складності Medium
Часто запитують у Аколіт Амазонка BrowserStack Dell Flipkart Грофери MakeMyTrip Нетскап Лабораторії Walmart
Мішанина Дерево Обхід дерева

У цій задачі ми навели покажчик, що позначає корінь двійкове дерево і ваше завдання - надрукувати бінарне дерево у вертикальному порядку.

Приклад

вхід

           1
        /    \ 
      2         3
    / \      /  \
  4    5    6    7
               \     \ 
                8      9

Вихід

4
2
+1 5 6 XNUMX
3 8
7
9

Пояснення

Роздрукуйте двійкове дерево у вертикальному порядку

Алгоритм друку двійкового дерева у вертикальному порядку

  1. Вставте елементи в різні вузли.
  2. Встановіть відстань на 0.
  3. Перевірте, чи кореневий код дорівнює нулю, якщо true, тоді поверніть.
  4. Встановіть keyValue значення відстані як ключ на карті.
    1. Перевірте, чи є “KeyValue” дорівнює нулю.
      1. Якщо true, тоді ініціалізуйте a “KeyValue” до нового вектора та додайте кореневе значення (елемент) у цьому векторі.
    2. В іншому випадку додайте кореневе значення до цього вектора, оскільки воно вже існує.
  5. Поставте відстань і “Ключове значення” на карті.
  6. Рекурсивно викликає функцію printVerticalTree за допомогою “Root.left”, відстань -1, "М" і “Root.right”, відстань +1, "М" для лівого та правого піддерев відповідно.
  7. Роздрукувати карту.

Пояснення для друку двійкового дерева у вертикальному порядку

Наша основна ідея для друку бінарного дерева у вертикальному порядку полягає в тому, щоб рекурсивно викликати функції з оновленими значеннями, що передаються щоразу як аргумент, і продовжувати оновлювати нашу карту відповідно до результату, який ми хочемо.

Починаючи з вставки вузлів у root, root.right, root.left, root.left.left тощо, ми маємо свої значення як вхідні дані. Нам потрібно взяти ці входи по одному, починаючи з самого лівого елемента в дереві. Ми ініціалізуємо вектор, який потім вставляється на карту з цілим числом як ключем для кожного індексу вектора. У векторі ми збираємося зберігати всі значення по вертикалі, а потім поміщаємо відстані та keyValue на карту як “Ключове значення” пару.

Головна частина

Коли ми вперше передаємо корінь, він не має нульового значення. Тоді map.get (distance) буде зберігатись у keyValue, якщо тоді keyValue виявиться нульовим, це означає як 'відстань', оскільки ключ на карті він не має жодного значення, тоді ми ініціалізуємо вектор keyValue і додаємо корінь. ключ, що означає деякий елемент, на який вказує root.key. Якщо keyValue не має значення null, це означає, що вже є деякі існуючі значення, які зберігаються вздовж його 'ключа'. Нам просто потрібно додати цей “root.key” (елемент, який вказується).

У всьому цьому є ще один важливий термін - відстань. Відстань означає вертикальну відстань будь-якого вузла в дереві від кореневого вузла, ми отримуємо числа як відстань, як ліве піддерево отримуємо від'ємні числа, а для правого піддерева отримуємо додатні числа, а для правого та вузлів нижче кореня вважається на відстані 0 від кореня, який ми передаємо як свої аргументи рекурсивно. Кожен раз, коли ми передаємо відстань як аргумент, це означає, що ми будемо зберігати разом із нею деякі значення, які, як виявилося, є ключем на карті, як у цьому прикладі, -2, -1, 0, 1, 2 3. Це ключі для кожного вектора, в якому ми збираємось зберігати наші елементи.

Нам потрібно надрукувати значення з карти, всі значення на карті мають ключі (відсортовані), починаючи з самого лівого елемента, означає від -2 до 3, що означає крайній правий елемент. Ми отримаємо всі елементи вертикально і роздрукуємо.

Реалізація для друку бінарного дерева у вертикальному порядку

Програма С ++

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node
{
    int key;
    Node *left, *right;
};
struct Node* newNode(int key)
{
    struct Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
void printVerticalTree(Node* root, int distance, map<int, vector<int>> &mymap)
{
    if (root == NULL)
        return;

    mymap[distance].push_back(root->key);

    printVerticalTree(root->left, distance-1, mymap);

    printVerticalTree(root->right, distance+1, mymap);
}
void printVerticalOrder(Node* root)
{
    map < int,vector<int> > mymap;
    int distance = 0;
    printVerticalTree(root, distance,mymap);
    map< int,vector<int> > :: iterator it;
    for (it=mymap.begin(); it!=mymap.end(); it++)
    {
        for (int i=0; i<it->second.size(); ++i)
            cout << it->second[i] << " ";
        cout << endl;
    }
}
int main()
{
    Node *root = newNode(3);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(11);
    root->right->left = newNode(14);
    root->right->right = newNode(17);
    root->right->left->right = newNode(18);
    root->right->right->right = newNode(25);
    cout << "Vertical order traversal is \n";
    printVerticalOrder(root);
    return 0;
}
Vertical order traversal is
8
4
3 11 14
6 18
17
25

Програма Java

import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;

class printBinarytreeVertical
{
    static class Node
    {
        int key;
        Node left;
        Node right;
        Node(int data)
        {
            key = data;
            left = null;
            right = null;
        }
    }
    static void printVerticalTree(Node root, int distance, TreeMap<Integer,Vector<Integer>> map)
    {

        if(root == null)
        {
            return;
        }
        Vector<Integer> keyValue = map.get(distance);
        if(keyValue == null)
        {
            keyValue = new Vector<>();
            keyValue.add(root.key);
        }
        else
            keyValue.add(root.key);

        map.put(distance, keyValue);

        printVerticalTree(root.left, distance-1, map);

        printVerticalTree(root.right, distance+1, map);
    }
    static void printVerticalOrder(Node root)
    {
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
        int distance =0;
        printVerticalTree(root,distance,m);
        for (Entry<Integer, Vector<Integer>> getentry : m.entrySet())
        {
            System.out.println(getentry.getValue());
        }
    }
    public static void main(String[] args)
    {
        Node root = new Node(3);
        root.left = new Node(4);
        root.right = new Node(6);
        root.left.left = new Node(8);
        root.left.right = new Node(11);
        root.right.left = new Node(14);
        root.right.right = new Node(17);
        root.right.left.right = new Node(18);
        root.right.right.right = new Node(25);
        System.out.println("Vertical Order traversal is");
        printVerticalOrder(root);
    }
}
Vertical Order traversal is
[8]
[4]
[3, 11, 14]
[6, 18]
[17]
[25]

Аналіз складності для друку двійкового дерева у вертикальному порядку

Складність часу

O (n Вхід) де "N" - кількість елементів у дереві.

Складність простору

О (п) де "N" - кількість елементів у дереві.

посилання