Рубрики

Распечатать двоичное дерево в вертикальном порядке | Набор 2 (метод на основе карты)

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

           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

Мы обсудили решение O (n 2 ) в предыдущем посте . В этом посте обсуждается эффективное решение, основанное на хэш-карте. Нам нужно проверить горизонтальные расстояния от корня для всех узлов. Если два узла имеют одинаковое горизонтальное расстояние (HD), то они находятся на одной вертикальной линии. Идея HD проста. HD для корня равен 0, правый край (край, соединяющийся с правым поддеревом) рассматривается как +1 горизонтальное расстояние, а левый край — как -1 горизонтальное расстояние. Например, в приведенном выше дереве HD для узла 4 равен -2, HD для узла 2 равен -1, HD для 5 и 6 равен 0, а HD для узла 7 равен +2.
Мы можем сделать предварительный обход заданного двоичного дерева. Обходя дерево, мы можем рекурсивно вычислять HD. Мы изначально передаем горизонтальное расстояние как 0 для корня. Для левого поддерева мы передаем горизонтальное расстояние как горизонтальное расстояние от корня минус 1. Для правого поддерева мы передаем горизонтальное расстояние как горизонтальное расстояние от корня плюс 1. Для каждого значения HD мы поддерживаем список узлов в хэш-карте. Всякий раз, когда мы видим узел в обходе, мы идем к записи карты хеша и добавляем узел к карте хеша, используя HD в качестве ключа на карте.

Ниже приведена реализация вышеуказанного метода на C ++. Спасибо Chirag за предоставленную ниже реализацию C ++.

C ++

// C ++ программа для печати вертикального порядка заданного двоичного дерева
#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;

}

  
// Утилита для сохранения вертикального порядка на карте 'm'
// 'hd' - горизонтальное расстояние текущего узла от корня.
// 'hd' изначально передается как 0

void getVerticalOrder(Node* root, int hd, map<int, vector<int>> &m)

{

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

    if (root == NULL)

        return;

  

    // Сохраняем текущий узел на карте 'm'

    m[hd].push_back(root->key);

  

    // Сохраняем узлы в левом поддереве

    getVerticalOrder(root->left, hd-1, m);

  

    // Сохраняем узлы в правом поддереве

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

}

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

void printVerticalOrder(Node* root)

{

    // Создать карту и сохранить вертикальный порядок на карте, используя

    // функция getVerticalOrder ()

    map < int,vector<int> > m;

    int hd = 0;

    getVerticalOrder(root, hd,m);

  

    // Обходим карту и печатаем узлы на каждом горизонтали

    // расстояние (hd)

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

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

    {

        for (int i=0; i<it->second.size(); ++i)

            cout << it->second[i] << " ";

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

    printVerticalOrder(root);

    return 0;

}

Джава

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

import java.util.TreeMap;

import java.util.Vector;

import java.util.Map.Entry;

  

public class VerticalOrderBtree 

{

    // Узел дерева

    static class Node

    {

        int key;

        Node left;

        Node right;

          

        // Конструктор

        Node(int data)

        {

            key = data;

            left = null;

            right = null;

        }

    }

      

    // Утилита для сохранения вертикального порядка на карте 'm'

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

    // 'hd' изначально передается как 0

    static void getVerticalOrder(Node root, int hd,

                                TreeMap<Integer,Vector<Integer>> m)

    {

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

        if(root == null)

            return;

          

        // получаем список векторов в 'hd'

        Vector<Integer> get =  m.get(hd);

          

        // Сохраняем текущий узел на карте 'm'

        if(get == null)

        {

            get = new Vector<>();

            get.add(root.key);

        }

        else

            get.add(root.key);

          

        m.put(hd, get);

          

        // Сохраняем узлы в левом поддереве

        getVerticalOrder(root.left, hd-1, m);

          

        // Сохраняем узлы в правом поддереве

        getVerticalOrder(root.right, hd+1, m);

    }

      

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

    // с заданным корнем

    static void printVerticalOrder(Node root)

    {

        // Создать карту и сохранить вертикальный порядок на карте, используя

        // функция getVerticalOrder ()

        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();

        int hd =0;

        getVerticalOrder(root,hd,m);

          

        // Обходим карту и печатаем узлы на каждом горизонтали

        // расстояние (hd)

        for (Entry<Integer, Vector<Integer>> entry : m.entrySet())

        {

            System.out.println(entry.getValue());

        }

    }

      

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

    public static void main(String[] args) {

  

        // TO DO автоматически сгенерированный метод заглушки

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

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

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

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

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

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

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

        System.out.println("Vertical Order traversal is");

        printVerticalOrder(root);

    }

}
// Этот код предоставлен Sumit Ghosh

питон

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

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

class Node:

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

  
# Утилита для сохранения вертикального порядка на карте 'm'
# 'hd' - горизонтальное расстояние текущего узла от корня
# 'hd' изначально передается как 0

def getVerticalOrder(root, hd, m):

  

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

    if root is None:

        return

      

    # Сохранить текущий узел на карте 'm'

    try:

        m[hd].append(root.key)

    except:

        m[hd] = [root.key]

      

    # Хранить узлы в левом поддереве

    getVerticalOrder(root.left, hd-1, m)

      

    # Хранить узлы в правом поддереве

    getVerticalOrder(root.right, hd+1, m)

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

def printVerticalOrder(root):

      

    # Создать карту и сохранить вертикальный порядок на карте, используя

    # function getVerticalORder ()

    m = dict()

    hd = 0 

    getVerticalOrder(root, hd, m)

      

    # Пройдите по карте и напечатайте узлы на каждой горизонтали

    # расстояние (hd)

    for index, value in enumerate(sorted(m)):

        for i in m[value]:

            print i,

        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"

printVerticalOrder(root)

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


Выход:

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

Сложность времени решения на основе хеширования можно рассматривать как O (n) в предположении, что у нас есть хорошая функция хеширования, которая позволяет выполнять операции вставки и извлечения за время O (1). В приведенной выше реализации C ++ используется карта STL . Карта в STL обычно реализуется с использованием самобалансирующегося бинарного дерева поиска, где все операции занимают O (Logn) время. Следовательно, временная сложность вышеописанной реализации составляет O (nLogn).

Обратите внимание, что вышеприведенное решение может печатать узлы в том же вертикальном порядке, как они отображаются в дереве. Например, выше программа печатает 12 , прежде чем 9. См это для образца перспективы.

             1
          /     
         2       3
        /      /  
       4    5  6    7
                  /  
                 8 10  9 
                     
                     11
                       
                        12      

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

Распечатать двоичное дерево в вертикальном порядке | Набор 3 (с использованием обхода уровня)

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

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

Распечатать двоичное дерево в вертикальном порядке | Набор 2 (метод на основе карты)

0.00 (0%) 0 votes