Рубрики

Вид снизу бинарного дерева

Учитывая Двоичное Дерево, нам нужно напечатать вид снизу слева направо. Узел x находится на выходе, если x — самый нижний узел на его горизонтальном расстоянии. Горизонтальное расстояние левого дочернего узла x равно горизонтальному расстоянию x минус 1, а правого дочернего элемента — горизонтальное расстояние x плюс 1.

Примеры:

                      20
                    /    \
                  8       22
                /   \      \
              5      3      25
                    / \      
                  10    14

Для вышеприведенного дерева вывод должен быть 5, 10, 3, 14, 25.

Если для горизонтального расстояния от корня имеется несколько самых нижних узлов, распечатайте последний в обход уровня. Например, на приведенной ниже диаграмме 3 и 4 являются самыми нижними узлами на горизонтальном расстоянии 0, нам нужно вывести 4.

                   
                      20
                    /    \
                  8       22
                /   \    /   \
              5      3 4     25
                    / \      
                  10    14 

Для вышеприведенного дерева вывод должен быть 5, 10, 4, 14, 25.


Метод 1 — Использование очереди

Ниже приведены шаги для печати вида снизу двоичного дерева.
1. Мы помещаем узлы дерева в очередь для прохождения порядка уровней.
2. Начните с горизонтального расстояния (hd) 0 корневого узла, продолжайте добавлять левого дочернего элемента в очередь вместе с горизонтальным расстоянием как hd-1 и правым дочерним элементом как hd + 1.
3. Также используйте TreeMap, в котором хранятся пары ключ-значение, отсортированные по ключу.
4. Каждый раз, когда мы сталкиваемся с новым горизонтальным расстоянием или существующим горизонтальным расстоянием, вводим данные узла для горизонтального расстояния в качестве ключа. В первый раз он добавит на карту, в следующий раз он заменит значение. Это обеспечит наличие на карте самого нижнего элемента для этого горизонтального расстояния, и если вы увидите дерево снизу, то увидите этот элемент.

Java-реализация ниже:

C ++

// C ++ Программа для печати вида снизу двоичного дерева
#include<bits/stdc++.h>

using namespace std;

  
// Класс дерева узла

struct Node

{

    int data; // данные узла

    int hd; // горизонтальное расстояние узла

    Node *left, *right; // левая и правая ссылки

  

    // Конструктор узла дерева

    Node(int key)

    {

        data = key;

        hd = INT_MAX;

        left = right = NULL;

    }

};

  
// Метод, который печатает вид снизу.

void bottomView(Node *root)

{

    if (root == NULL)

        return;

  

    // Инициализируем переменную 'hd' с 0

    // для корневого элемента.

    int hd = 0;

  

    // TreeMap, в котором хранится пара ключ-значение

    // отсортировано по значению ключа

    map<int, int> m;

  

    // Очередь для хранения узлов дерева на уровне

    // обход заказа

    queue<Node *> q;

  

    // Назначаем инициализированное горизонтальное расстояние

    // значение корневого узла и добавление его в очередь.

    root->hd = hd;

    q.push(root);  // В STL push () используется для постановки в очередь

  

    // Цикл, пока очередь не пуста (стандартно

    // уровень порядка цикла)

    while (!q.empty())

    {

        Node *temp = q.front();

        q.pop();   // В STL pop () используется для удаления элемента

  

        // Извлекаем значение горизонтального расстояния

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

        hd = temp->hd;

  

        // Поместить удаленный узел дерева в TreeMap

        // имея ключ в качестве горизонтального расстояния. каждый

        // раз мы находим узел, имеющий такую же горизонталь

        // расстояние, на которое нужно заменить данные в

        // карта.

        m[hd] = temp->data;

  

        // Если у удаленного узла есть левый потомок, добавляем

        // это в очередь с горизонтальным расстоянием hd-1.

        if (temp->left != NULL)

        {

            temp->left->hd = hd-1;

            q.push(temp->left);

        }

  

        // Если у удаленного узла есть правильный дочерний элемент, добавляем

        // это в очередь с горизонтальным расстоянием

        // HD + 1.

        if (temp->right != NULL)

        {

            temp->right->hd = hd+1;

            q.push(temp->right);

        }

    }

  

    // Обход элементов карты с помощью итератора.

    for (auto i = m.begin(); i != m.end(); ++i)

        cout << i->second << " ";

}

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

int main()

{

    Node *root = new Node(20);

    root->left = new Node(8);

    root->right = new Node(22);

    root->left->left = new Node(5);

    root->left->right = new Node(3);

    root->right->left = new Node(4);

    root->right->right = new Node(25);

    root->left->right->left = new Node(10);

    root->left->right->right = new Node(14);

    cout << "Bottom view of the given binary tree :\n"

    bottomView(root);

    return 0;

}

Джава

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

import java.util.*;

import java.util.Map.Entry;

  
// Класс дерева узла

class Node

{

    int data; // данные узла

    int hd; // горизонтальное расстояние узла

    Node left, right; // левая и правая ссылки

  

    // Конструктор узла дерева

    public Node(int key)

    {

        data = key;

        hd = Integer.MAX_VALUE;

        left = right = null;

    }

}

  
// Класс дерева

class Tree

{

    Node root; // корневой узел дерева

  

    // Конструктор по умолчанию

    public Tree() {}

  

    // Параметризованный конструктор дерева

    public Tree(Node node)

    {

        root = node;

    }

  

    // Метод, который печатает вид снизу.

    public void bottomView()

    {

        if (root == null)

            return;

  

        // Инициализируем переменную 'hd' с 0 для корневого элемента.

        int hd = 0;

  

        // TreeMap, в котором хранится пара ключ-значение, отсортированная по значению ключа

        Map<Integer, Integer> map = new TreeMap<>();

  

         // Очередь для хранения узлов дерева в порядке обхода уровня

        Queue<Node> queue = new LinkedList<Node>();

  

        // Присваиваем инициализированное значение горизонтального расстояния корню

        // узел и добавить его в очередь.

        root.hd = hd;

        queue.add(root);

  

        // Цикл до тех пор, пока очередь не станет пустой (стандартный уровень порядка цикла)

        while (!queue.isEmpty())

        {

            Node temp = queue.remove();

  

            // Извлекаем значение горизонтального расстояния из

            // удаленный узел дерева.

            hd = temp.hd;

  

            // Поместить удаленный узел дерева в TreeMap, имеющий ключ

            // как горизонтальное расстояние. Каждый раз, когда мы находим узел

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

            // данные на карте.

            map.put(hd, temp.data);

  

            // Если у удаленного узла есть левый потомок, добавьте его в

            // очередь с горизонтальным расстоянием hd-1.

            if (temp.left != null)

            {

                temp.left.hd = hd-1;

                queue.add(temp.left);

            }

            // Если у удаленного узла есть левый потомок, добавьте его в

            // очередь с горизонтальным расстоянием hd + 1.

            if (temp.right != null)

            {

                temp.right.hd = hd+1;

                queue.add(temp.right);

            }

        }

  

        // Извлекаем записи карты в набор для прохождения

        // итератор над этим.

        Set<Entry<Integer, Integer>> set = map.entrySet();

  

        // Сделать итератор

        Iterator<Entry<Integer, Integer>> iterator = set.iterator();

  

        // Обход элементов карты с помощью итератора.

        while (iterator.hasNext())

        {

            Map.Entry<Integer, Integer> me = iterator.next();

            System.out.print(me.getValue()+" ");

        }

    }

}

  
// Основной класс драйвера

public class BottomView

{

    public static void main(String[] args)

    {

        Node root = new Node(20);

        root.left = new Node(8);

        root.right = new Node(22);

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

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

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

        root.right.right = new Node(25);

        root.left.right.left = new Node(10);

        root.left.right.right = new Node(14);

        Tree tree = new Tree(root);

        System.out.println("Bottom view of the given binary tree:");

        tree.bottomView();

    }

}

Выход:

Bottom view of the given binary tree:
5 10 4 14 25

Метод 2 — Использование HashMap ()
Этот метод предоставлен Ekta Goel .
Подходить:
Создайте карту, например, map, где key — это горизонтальное расстояние, а value — пара (a, b), где a — значение узла, а b — высота узла. Выполните предварительный обход дерева. Если текущий узел на горизонтальном расстоянии h является первым, который мы видели, вставьте его в карту. В противном случае сравните узел с существующим на карте и, если высота нового узла больше, обновите на карте.

Ниже приведена реализация вышеперечисленного:

// C ++ Программа для печати вида снизу двоичного дерева
#include < bits / stdc++.h > 
#include < map >

using namespace std;

  
// Класс дерева узла

struct Node 

{

    // данные узла

    int data;

      

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

    int hd; 

      

    // левая и правая ссылки

    Node * left, * right; 

      

    // Конструктор узла дерева

    Node(int key) 

    {

        data = key;

        hd = INT_MAX;

        left = right = NULL;

    }

};

  

void printBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m)

{

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

    if (root == NULL)

        return;

      

    // Если узел для конкретного

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

    // представить, добавить на карту.

    if (m.find(hd) == m.end()) 

    {

        m[hd] = make_pair(root -> data, curr);

    

    // Сравнить высоту уже

    // представить узел на аналогичной горизонтали

    // расстояние

    else 

    {

        pair < int, int > p = m[hd];

        if (p.second <= curr)

        {

            m[hd].second = curr;

            m[hd].first = root -> data;

        }

    }

      

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

    printBottomViewUtil(root -> left, curr + 1, hd - 1, m);

      

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

    printBottomViewUtil(root -> right, curr + 1, hd + 1, m);

}

  

void printBottomView(Node * root) 

{

      

    // Карта для сохранения горизонтального расстояния,

    // Высота и данные.

    map < int, pair < int, int > > m;

      

    printBottomViewUtil(root, 0, 0, m);

      

     // Печатает значения, хранящиеся в printBottomViewUtil ()

    map < int, pair < int, int > > ::iterator it;

    for (it = m.begin(); it != m.end(); ++it)

    {

        pair < int, int > p = it -> second;

        cout << p.first << " ";

    }

}

  

int main() 

{

    Node * root = new Node(20);

    root -> left = new Node(8);

    root -> right = new Node(22);

    root -> left -> left = new Node(5);

    root -> left -> right = new Node(3);

    root -> right -> left = new Node(4);

    root -> right -> right = new Node(25);

    root -> left -> right -> left = new Node(10);

    root -> left -> right -> right = new Node(14);

    cout << "Bottom view of the given binary tree :\n";

    printBottomView(root);

    return 0;

}

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

Вид снизу бинарного дерева

0.00 (0%) 0 votes