Рубрики

Нахождение лексикографически наименьшего диаметра в бинарном дереве

Учитывая двоичное дерево, в котором значения узлов представляют собой строчные буквы, задача состоит в том, чтобы найти лексикографически наименьший диаметр. Диаметр — это самый длинный путь между любыми двумя листовыми узлами, следовательно, в двоичном дереве может быть несколько диаметров. Задача состоит в том, чтобы напечатать лексикографически наименьший диаметр среди всех возможных диаметров.

Примеры:

Input:          
        a
      /   \
    b       c
  /  \     /  \
 d   e    f    g
Output: Diameter: 5
Lexicographically smallest diameter: d b a c f
Explanation:
Note that there are many other paths 
exist like {d, b, a, c, g}, 
{e, b, a, c, f} and {e, b, a, c, g} 
but {d, b, a, c, f} 
is lexicographically smallest

Input:          
        k
      /   \
    e       s
  /  \       
 g   f    
Output: Diameter: 4
Lexicographically smallest diameter: f e k s
Explanation:
Note that many other paths 
exist like {g, e, k, s} 
{s, k, e, g} and {s, k, e, f} 
but {f, e, k, s} is 
lexicographically smallest

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

шаги:

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

Ниже приведена реализация вышеуказанного подхода:

// C ++ программа для вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

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

struct node {

    char data;

    node *left, *right;

};

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

node* newNode(char data)

{

    node* c = new node;

    c->data = data;

    c->left = c->right = NULL;

    return c;

}

  
// Функция для сравнения и возврата
// лексикографически наименьший вектор
vector<node*> compare(vector<node*> a, vector<node*> b)
{

    for (int i = 0; i < a.size() && i < b.size(); i++) {

        if (a[i]->data < b[i]->data) {

            return a;

        }

        if (a[i]->data > b[i]->data) {

            return b;

        }

    }

  

    return a;

}

  
// Функция для определения диаметра

int diameter(node* root, int& height, vector<node*>& dia,

             vector<node*>& heightv)

{

    // Если root имеет значение null

    if (!root) {

        height = 0;

        return 0;

    }

  

    // Левая высота и правая высота

    // соответственно

    int lh = 0, rh = 0;

  

    // левый диаметр дерева и

    // правильный диаметр дерева

    int ld, rd;

  

    vector<node*> leftdia;

    vector<node*> rightdia;

    vector<node*> leftheight;

    vector<node*> rightheight;

  

    // Левый диаметр поддерева

    ld = diameter(root->left, lh, leftdia, leftheight);

  

    // Правый диаметр поддерева

    rd = diameter(root->right, rh, rightdia, rightheight);

  

    // Если левая высота больше

    // чем правая высота дерева

    if (lh > rh) {

  

        // Добавить текущий корень, чтобы lh + 1

        height = lh + 1;

  

        // Изменение вектора высотыv на левую высоту

        heightv = leftheight;

  

        // Вставляем текущий корень в путь

        heightv.push_back(root);

    }

  

    // Если правильная высота

    // больше левой высоты дерева

    else if (rh > lh) {

  

        // Добавить текущий корень, чтобы rh + 1

        height = rh + 1;

  

        // Изменим высоту вектора на правую высоту

        heightv = rightheight;

  

        // Вставляем текущий корень в путь

        heightv.push_back(root);

    }

  

    // сравниваем обе высоты

    // теперь лексикографически

    else {

  

        // Добавить текущий корень, чтобы rh + 1

        height = rh + 1;

  

        // Лексикографическое сравнение двух векторов

        heightv = compare(leftheight, rightheight);

  

        // Вставляем текущий корень в путь

        heightv.push_back(root);

    }

  

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

    // содержащий корень больше левого

    // диаметр и правильный диаметр

    if (lh + rh + 1 > max(ld, rd)) {

  

        // Делаем dia равной leftheight

        dia = leftheight;

  

        // Добавить текущий корень в него

        dia.push_back(root);

  

        for (int j = rightheight.size() - 1; j >= 0; j--) {

            // Добавить правильное дерево (право на корень) узлов

            dia.push_back(rightheight[j]);

        }

    }

  

    // Если левый диаметр содержит левый

    // поддерево и корень или правый диаметр

    // правильное поддерево и корень больше чем

    // выше lh + rh + 1

    else {

  

        // Если диаметр левого дерева

        // больше наш вектор ответа т.е.

        // dia равна leftdia тогда

        if (ld > rd) {

            dia = leftdia;

        }

  

        // Если оба диаметра

        // такая же проверка лексикографически

        else if (ld == rd) {

            dia = compare(leftdia, rightdia);

        }

  

        // Если диаметр правильного дерева

        // больше наш вектор ответа

        // то есть dia равна rightdia тогда

        else {

            dia = rightdia;

        }

    }

  

    return dia.size();

}

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

int main()

{

    node* root = newNode('a');

    root->left = newNode('b');

    root->right = newNode('c');

    root->left->left = newNode('d');

    root->left->right = newNode('e');

    root->right->left = newNode('f');

    root->right->right = newNode('g');

  

    int height = 0;

    vector<node *> dia, heigh;

    cout << "Diameter is: " << diameter(root, height,

                                        dia, heigh)

         << endl;

  

    // Печать лексикографически наименьшего диаметра

    cout << "Lexicographically smallest diameter:" << endl;

    for (int j = 0; j < dia.size(); j++) {

        cout << dia[j]->data << " ";

    }

  

    return 0;

}

Выход:

Diameter is: 5
Lexicographically smallest diameter:
d b a c f

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

Нахождение лексикографически наименьшего диаметра в бинарном дереве

0.00 (0%) 0 votes