Рубрики

Узлы печати в виде сверху двоичного дерева

Вид сверху бинарного дерева — это набор узлов, видимых при просмотре дерева сверху. Учитывая двоичное дерево, выведите его вид сверху. Выходные узлы могут быть напечатаны в любом порядке. Ожидаемая сложность времени O (n)

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

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7
Top view of the above binary tree is
4 2 1 3 7

        1
      /   \
    2       3
      \   
        4  
          \
            5
             \
               6
Top view of the above binary tree is
2 1 3 6

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

C ++

// C ++ программа для печати сверху
// просмотр двоичного дерева

  
#include <iostream> 
#include<queue> 
#include<map>

using namespace std;

  
// Структура двоичного дерева

struct Node

{

    Node * left;

    Node* right;

    int hd;

    int data;

};

  
// функция для создания нового узла

Node* newNode(int key)

{

    Node* node=new Node();

    node->left = node->right = NULL;

    node->data=key;

    return node;

}

  
// функция должна напечатать topView
// двоичное дерево

void topview(Node* root)

{

    if(root==NULL)

       return;

     queue<Node*>q;

     map<int,int> m; 

     int hd=0;

     root->hd=hd;

       

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

    q.push(root);

      

    cout<< "The top view of the tree is : \n";

      

    while(q.size())

    {

        hd=root->hd;

          

        // функция count возвращает 1, если контейнер

        // содержит элемент, ключ которого эквивалентен

        // в hd или возвращает ноль в противном случае.

        if(m.count(hd)==0)  

        m[hd]=root->data;

        if(root->left)

        {

            root->left->hd=hd-1;

            q.push(root->left);

        }

        if(root->right)

        {

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

            q.push(root->right);

        }

        q.pop();

        root=q.front();

        

    }

      

      

      

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

    {

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

    }

      
}

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

int main()

{

    / * Создать следующее двоичное дерево

            1

        / /

        2 3

        /

            4

            /

            5

            /

                6 * /

   Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

    cout<<"Following are nodes in top view of Binary Tree\n"

    topview(root);

    return 0;

}
/ * Этот код предоставлен Нитешем Кумаром * /

Джава

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

import java.util.Queue;

import java.util.TreeMap;

import java.util.LinkedList;

import java.util.Map;

import java.util.Map.Entry;

  
// класс для создания узла

class Node {

    int data;

    Node left, right;

  

    public Node(int data) {

        this.data = data;

        left = right = null;

    }

}

  
// класс двоичного дерева

class BinaryTree {

    Node root;

  

    public BinaryTree() {

        root = null;

    }

      

    // функция должна напечатать topView

    // двоичное дерево

    private void TopView(Node root) {

        class QueueObj {

            Node node;

            int hd;

  

            QueueObj(Node node, int hd) {

                this.node = node;

                this.hd = hd;

            }

        }

        Queue<QueueObj> q = new LinkedList<QueueObj>();

        Map<Integer, Node> topViewMap = new TreeMap<Integer, Node>();

  

        if (root == null) {

            return;

        } else {

            q.add(new QueueObj(root, 0));

        }

  

        System.out.println("The top view of the tree is : ");

          

        // функция count возвращает 1, если контейнер

        // содержит элемент, ключ которого эквивалентен

        // в hd или возвращает ноль в противном случае.

        while (!q.isEmpty()) {

            QueueObj tmpNode = q.poll();

            if (!topViewMap.containsKey(tmpNode.hd)) {

                topViewMap.put(tmpNode.hd, tmpNode.node);

            }

  

            if (tmpNode.node.left != null) {

                q.add(new QueueObj(tmpNode.node.left, tmpNode.hd - 1));

            }

            if (tmpNode.node.right != null) {

                q.add(new QueueObj(tmpNode.node.right, tmpNode.hd + 1));

            }

  

        }

        for (Entry<Integer, Node> entry : topViewMap.entrySet()) {

            System.out.print(entry.getValue().data);

        }

    }

      

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

    public static void main(String[] args) 

    

        / * Создать следующее двоичное дерево

            1

        / /

        2 3

        /

            4

            /

            5

            /

                6 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

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

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

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

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

        System.out.println("Following are nodes in top view of Binary Tree"); 

        tree.TopView(tree.root); 

    

      
}

python3

# Python3 программа для печати сверху
# просмотр двоичного дерева

  
# Узел двоичного дерева
"" "утилита, которая выделяет новый узел
с заданным ключом "" "

class newNode: 

  

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

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

        self.hd = 0

  
# функция должна печатать topView
# двоичного дерева

def topview(root) :

  

    if(root == None) :

        return

    q = []

    m = dict()

    hd = 0

    root.hd = hd 

  

    # толкать узел и горизонталь

    # расстояние до очереди

    q.append(root) 

  

    while(len(q)) :

        root = q[0]

        hd = root.hd 

          

        Функция # count возвращает 1, если

        # контейнер содержит элемент

        # чей ключ эквивалентен hd,

        # или возвращает ноль в противном случае.

        if hd not in m:

            m[hd] = root.data 

        if(root.left) :         

            root.left.hd = hd - 1

            q.append(root.left) 

          

        if(root.right):         

            root.right.hd = hd + 1

            q.append(root.right) 

          

        q.pop(0)

    for i in sorted (m):

        print(m[i], end = "") 

  
Код водителя

if __name__ == '__main__':

  

    "" "Создать следующее двоичное дерево

            1

        / /

        2 3

        /

            4

            /

            5

            /

                6 * ""»

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.right = newNode(4

    root.left.right.right = newNode(5

    root.left.right.right.right = newNode(6

    print("Following are nodes in top"

          "view of Binary Tree"

    topview(root)

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)


Выход:

Following are nodes in top view of Binary Tree
2136

Другой подход:

Этот подход не требует очереди. Здесь мы используем две переменные: одну для вертикального расстояния текущего узла от корня и другую для глубины текущего узла от корня. Мы используем вертикальное расстояние для индексации. Если снова появляется один узел с тем же вертикальным расстоянием, мы проверяем, является ли глубина нового узла ниже или выше относительно текущего узла с таким же вертикальным расстоянием на карте. Если глубина нового узла ниже, то мы его заменим.

C ++

#include<bits/stdc++.h>

using namespace std;

  
// Структура двоичного дерева

struct Node{

    Node * left;

    Node* right;

    int data;

};

  
// функция для создания нового узла

Node* newNode(int key){

    Node* node=new Node();

    node->left = node->right = NULL;

    node->data=key;

    return node;

}

  
// функция для заполнения карты

void fillMap(Node* root,int d,int l,map<int,pair<int,int>> &m){

    if(root==NULL) return;

  

    if(m.count(d)==0){

        m[d] = make_pair(root->data,l);

    }else if(m[d].second>l){

        m[d] = make_pair(root->data,l);

    }

  

    fillMap(root->left,d-1,l+1,m);

    fillMap(root->right,d+1,l+1,m);

}

  
// функция должна напечатать topView
// двоичное дерево

void topView(struct Node *root){

  

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

    // относительно вертикального расстояния от корня.

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

  

    // fillmap (корень, vectical_distance_from_root, level_of_node, карта)

    fillMap(root,0,0,m);

  

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

        cout << it->second.first << " ";

    }

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

int main(){

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

    cout<<"Following are nodes in top view of Binary Tree\n"

    topView(root);

    return 0;

}
/ * Этот код предоставлен Akash Debnath * /

Джава

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

import java.util.*;

  

class GFG

{

      
// Структура двоичного дерева

static class Node

{

    Node left;

    Node right;

    int data;

}

  

static class pair

{

    int first, second;

      

    pair(){}

    pair(int i, int j)

    {

        first = i;

        second = j;

    }

}

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

static TreeMap<Integer, 

               pair> m= new TreeMap<>();

  
// функция для создания нового узла

static Node newNode(int key)

{

    Node node = new Node();

    node.left = node.right = null;

    node.data = key;

    return node;

}

  
// функция для заполнения карты

static void fillMap(Node root, int d, int l)

{

    if(root == null) return;

  

    if(m.get(d) == null)

    {

        m.put(d, new pair(root.data, l));

    

    else if(m.get(d).second>l)

    {

        m.put(d, new pair(root.data, l));

    }

  

    fillMap(root.left, d - 1, l + 1);

    fillMap(root.right, d + 1, l + 1);

}

  
// функция должна напечатать topView
// двоичное дерево

static void topView(Node root)

{

    fillMap(root, 0, 0);

      

    for (Map.Entry<Integer, 

                   pair> entry : m.entrySet())

    {

        System.out.print(entry.getValue().first + " ");

    }

}

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

public static void main(String args[])

{

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.right = newNode(4);

    root.left.right.right = newNode(5);

    root.left.right.right.right = newNode(6);

    System.out.println("Following are nodes in" +

                     " top view of Binary Tree"); 

    topView(root);

}
}

  
// Этот код предоставлен Арнабом Кунду

python3

# Узел двоичного дерева
"" "утилита, которая выделяет новый узел
с заданным ключом "" "

class newNode: 

  

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

    def __init__(self, key): 

        self.data = key 

        self.left = None

        self.right = None

  
# функция для заполнения карты

def fillMap(root, d, l, m):

    if(root == None):

        return

      

    if d not in m:

        m[d] = [root.data,l]

    elif(m[d][1] > l):

        m[d] = [root.data,l]

    fillMap(root.left, d - 1, l + 1, m)

    fillMap(root.right, d + 1, l + 1, m)

  
# функция должна отображать topView
# двоичное дерево

def topView(root):

      

    # карта для хранения пары значений узла и его уровня

    # относительно вертикального расстояния от корня.

    m = {}

      

    fillMap(root, 0, 0, m)

    for it in sorted (m.keys()):

        print(m[it][0], end = " ")

      
Код водителя

root = newNode(1)

root.left = newNode(2)

root.right = newNode(3)

root.left.right = newNode(4)

root.left.right.right = newNode(5)

root.left.right.right.right = newNode(6)

print("Following are nodes in top view of Binary Tree")

topView(root)

  
# Этот код предоставлен SHUBHAMSINGH10


Выход:

Following are nodes in top view of Binary Tree
2 1 3 6

Этот подход внес Акаш Дебнатх

Сложность по времени в приведенной выше реализации равна O (n), где n — количество узлов в данном двоичном дереве. Здесь предполагается, что методы add () и contains () HashSet работают за O (1) раз.

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

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

Узлы печати в виде сверху двоичного дерева

0.00 (0%) 0 votes