Рубрики

Диагональный обход бинарного дерева

Рассмотрим линии наклона -1, проходящие между узлами. Для заданного двоичного дерева выведите все диагональные элементы в двоичном дереве, принадлежащем одной строке.

Input : Root of below tree


Output : 
Diagonal Traversal of binary tree : 
 8 10 14
 3 6 7 13
 1 4

Идея состоит в том, чтобы использовать карту. Мы используем разные наклонные расстояния и используем их в качестве ключа на карте. Значением на карте является вектор (или динамический массив) узлов. Мы пересекаем дерево, чтобы сохранить значения в карте. Как только карта построена, мы печатаем ее содержимое.

Ниже приведена реализация вышеуказанной идеи.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    Node *left, *right;

};

  
/ * root - корень двоичного дерева

   d - расстояние от текущей линии до крайнего правого

        самый верхний уклон.

   diagonalPrint - мультикарта для хранения диагонали

                   элементы (Передано по ссылке) * /

void diagonalPrintUtil(Node* root, int d,

                      map<int, vector<int>> &diagonalPrint)

{

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

    if (!root)

        return;

  

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

    diagonalPrint[d].push_back(root->data);

  

    // Увеличить вертикальное расстояние, если левый ребенок

    diagonalPrintUtil(root->left, d + 1, diagonalPrint);

  

    // Вертикальное расстояние остается неизменным для правого ребенка

    diagonalPrintUtil(root->right, d, diagonalPrint);

}

  
// Распечатать диагональный обход заданного двоичного дерева

void diagonalPrint(Node* root)

{

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

    map<int, vector<int> > diagonalPrint;

    diagonalPrintUtil(root, 0, diagonalPrint);

  

    cout << "Diagonal Traversal of binary tree : n";

    for (auto it = diagonalPrint.begin();

         it != diagonalPrint.end(); ++it)

    {

        for (auto itr = it->second.begin();

             itr != it->second.end(); ++itr)

            cout << *itr  << ' ';

  

        cout << 'n';

    }

}

  
// Служебный метод для создания нового узла

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

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

    return node;

}

  
// Драйвер программы

int main()

{

    Node* root = newNode(8);

    root->left = newNode(3);

    root->right = newNode(10);

    root->left->left = newNode(1);

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

    root->right->right = newNode(14);

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

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

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

  

    / * Node * root = newNode (1);

        root-> left = newNode (2);

        root-> right = newNode (3);

        root-> left-> left = newNode (9);

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

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

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

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

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

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

        root-> left-> left-> right = newNode (10); * /

  

    diagonalPrint(root);

  

    return 0;

}

Джава

// Java-программа для диагонального обхода двоичного дерева

import java.util.HashMap;

import java.util.Map.Entry;

import java.util.Vector;

  

public class DiagonalTraversalBTree 

{

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

    static class Node{

        int data;

        Node left;

        Node right;

          

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

        Node(int data)

        {

            this.data=data;

            left = null;

            right =null;

        }

    }

      

    / * root - корень двоичного дерева

       d - расстояние от текущей линии до крайнего правого

            самый верхний уклон.

       diagonalPrint - HashMap для хранения диагонали

                       элементы (Передано по ссылке) * /

    static void diagonalPrintUtil(Node root,int d,

            HashMap<Integer,Vector<Integer>> diagonalPrint){

          

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

        if (root == null)

            return;

          

        // получить список с определенным значением d

        Vector<Integer> k = diagonalPrint.get(d);

          

        // k ноль, затем создать вектор и сохранить данные

        if (k == null)

        {

            k = new Vector<>();

            k.add(root.data);

        }

          

        // k не равен NULL, тогда обновите список

        else

        {

            k.add(root.data);

        }

          

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

        diagonalPrint.put(d,k);

          

        // Увеличить вертикальное расстояние, если левый ребенок

        diagonalPrintUtil(root.left, d + 1, diagonalPrint);

           

        // Вертикальное расстояние остается неизменным для правого ребенка

        diagonalPrintUtil(root.right, d, diagonalPrint);

    }

      

    // Распечатать диагональный обход заданного двоичного дерева

    static void diagonalPrint(Node root)

    {

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

        HashMap<Integer,Vector<Integer>> diagonalPrint = new HashMap<>();

        diagonalPrintUtil(root, 0, diagonalPrint);

          

        System.out.println("Diagonal Traversal of Binnary Tree");

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

        {

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

        }

    }

      

    // Драйвер программы

    public static void main(String[] args) {

          

        Node root = new Node(8);

        root.left = new Node(3);

        root.right = new Node(10);

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

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

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

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

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

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

          

        diagonalPrint(root);

    }

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

питон

# Программа Python для диагонального обхода двоичного дерева

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

class Node:

  

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  

  
"" "root - корень двоичного дерева

   d - расстояние от текущей линии до крайнего правого

        самый верхний уклон.

   diagonalPrint - мультикарта для хранения диагонали

                   элементы (переданные по ссылке) "" "

def diagonalPrintUtil(root, d, diagonalPrintMap):

      

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

    if root is None:

        return 

  

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

    try :

        diagonalPrintMap[d].append(root.data)

    except KeyError:

        diagonalPrintMap[d] = [root.data]

  

    # Увеличить вертикальное расстояние, если оставлен ребенок

    diagonalPrintUtil(root.left, d+1, diagonalPrintMap)

      

    # Вертикальное расстояние остается тем же для правильного ребенка

    diagonalPrintUtil(root.right, d, diagonalPrintMap)

  

  

  
# Вывести диагональный обход заданного двоичного дерева

def diagonalPrint(root):

  

    # Создать диктат для хранения диагностических элементов

    diagonalPrintMap = dict()

      

    # Найти диагональный обход

    diagonalPrintUtil(root, 0, diagonalPrintMap)

  

    print "Diagonal Traversal of binary tree : "

    for i in diagonalPrintMap:

        for j in diagonalPrintMap[i]:

            print j,

        print ""

  

  
# Драйверная программа

root = Node(8)

root.left = Node(3)

root.right = Node(10)

root.left.left = Node(1)

root.left.right = Node(6)

root.right.right = Node(14)

root.right.right.left = Node(13)

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

root.left.right.right = Node(7)

  
diagonalPrint(root)

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


Выход :

Diagonal Traversal of binary tree : 
 8 10 14
 3 6 7 13
 1 4

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

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

Диагональный обход бинарного дерева

0.00 (0%) 0 votes