Как найти максимальный путь в дереве - AvtoShod.ru

I will leave this answer in case any one need it. Here is my solution in c++.
The function Get_Max_Path() returns a vector with the longest path itself so you got the path, it’s length and it’s sum if needed:

vector<int> Max_Path(vector<int>rightpath, vector<int>leftpath)
{
    return (rightpath.size() > leftpath.size()) ? rightpath : leftpath;
}

vector<int> GetPath(node* N, vector<int> v)
{
    v.push_back(N->Data);
    return v;
}
vector<int> Get_Max_Path(node* root)
{
    if (!root) return 
        vector<int>(0);
    return Max_Path(GetPath( root, Get_Max_Path(root->Right)), 
                    GetPath( root, Get_Max_Path(root->Left)) );
}

And here is the tree structure


class node
{
public:
    node* Right = NULL;
    node* Left = NULL;
    int Data;
};

class Tree
{
private:
    node* Root = NULL;

public:

    void Insert_Node(int Data)
    {
        node* DataNode = (node*)malloc(sizeof(node));
        DataNode->Data = Data;
        DataNode->Left = DataNode->Right = NULL;

        if (Root == NULL) {
            Root = DataNode;
            return;
        }

        node* tmp_root = Root, * prev = NULL;
        while (tmp_root != NULL)
        {
            prev = tmp_root;
            tmp_root = (tmp_root->Data < Data) ?
                tmp_root->Right :
                tmp_root->Left;
        }
        (prev->Data < Data) ? (prev->Right = DataNode) : (prev->Left = DataNode);
    }

    vector<int> Max_Path(vector<int>rightpath, vector<int>leftpath)
    {
        return (rightpath.size() > leftpath.size()) ? rightpath : leftpath;
    }
    vector<int> Update_Path(node* N, vector<int> v)
    {
        v.push_back(N->Data);
        return v;
    }
    vector<int> Get_Max_length_Path(node* root)
    {
        if (!root) return
            vector<int>(0);
        return Max_Path(
            Update_Path(root, Get_Max_length_Path(root->Right)),
            Update_Path(root, Get_Max_length_Path(root->Left)));
    }

    vector<int> Get_Max_length_Path()
    {
        return Get_Max_length_Path(Root);
    }
};

This is the driver Code

int main()
{
    Tree T;

    int nodes[] = { 11, 6, 8, 19, 4, 13, 5, 17, 43, 49, 16, 31, 32};
    int length = sizeof(nodes) / sizeof(nodes[0]);

    for (size_t i = 0; i < length; i++)
        T.Insert_Node(nodes[i]);

    int sum = 0;

    vector<int> path = T.Get_Max_length_Path();
    cout << "The path length is : " << path.size() <<endl;
    cout << "The path from the leaf to the root is : ";
    for (int i = 0; i < path.size(); i++)
    {
        cout << path[i] << " ";
        sum += path[i] ;
    }
    cout << endl;
    cout << "the path sum is :" << sum << endl;
    return 0;
}

Test Case

BST sample

Output

The path length is : 5 The path from the leaf to the root is : 16 17
13 19 11 the path sum is :76

Источник

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

Например, максимальный суммарный путь в следующем бинарном дереве равен 22:

Потренируйтесь в этой проблеме

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

Временная сложность этого решения O(n²) как есть n узлов в дереве, и для каждого узла мы вычисляем максимальную сумму пути от узла к листу его левого и правого поддерева, который занимает O(n) время.

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

Алгоритм может быть реализован следующим образом на C++, Java и Python. Здесь мы передаем путь максимальной суммы по ссылке на функцию (вместо того, чтобы возвращать ее) и обновляем его значение внутри самой функции, используя возвращаемое значение левого и правого поддеревьев.

C++

#include <iostream>

#include <climits>

using namespace std;

// Структура данных для хранения узла бинарного дерева

struct Node

{

int data;

Node *left, *right;

Node(int data)

{

this->data = data;

this->left = this->right = nullptr;

}

};

// Рекурсивная функция для нахождения пути максимальной суммы между двумя листьями

// в бинарном дереве

int findMaxSumPath(Node* root, int &max_sum)

{

// базовый случай: пустое дерево

if (root == nullptr) {

return 0;

}

// найти максимальную сумму пути от узла к листу, начиная с левого потомка

int left = findMaxSumPath(root->left, max_sum);

// найти максимальную сумму пути от узла к листу, начиная с правого потомка

int right = findMaxSumPath(root->right, max_sum);

// важно вернуть максимальную сумму пути от узла к листу, начиная с

// текущий узел

// случай 1: левый дочерний элемент равен нулю

if (root->left == nullptr) {

return right + root->data;

}

// случай 2: правый дочерний элемент равен нулю

if (root->right == nullptr) {

return left + root->data;

}

// найти максимальный суммарный путь «сквозь» текущий узел

int cur_sum = left + right + root->data;

// обновить путь максимальной суммы, найденный до сих пор (обратите внимание, что путь максимальной суммы

// «исключение» текущего узла в поддереве с корнем в текущем узле

// уже обновляется, так как мы выполняем обход в обратном порядке)

max_sum = max(cur_sum, max_sum);

// случай 3: существуют и левый, и правый дочерние элементы

return max(left, right) + root->data;

}

// Функция для возврата пути максимальной суммы между двумя листьями в бинарном дереве

int findMaxSumPath(Node* root)

{

int max_sum = INT_MIN;

findMaxSumPath(root, max_sum);

return max_sum;

}

int main()

{

/* Построим следующее дерево

2 3

-4 5 6

7 8

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

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

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

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

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

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

cout << findMaxSumPath(root) << endl;

return 0;

}

Скачать Выполнить код

результат:

22

Java

import java.util.concurrent.atomic.AtomicInteger;

// Класс для хранения узла бинарного дерева

class Node

{

int data;

Node left = null, right = null;

Node(int data) {

this.data = data;

}

class Main

{

// Рекурсивная функция для нахождения пути максимальной суммы между двумя листьями

// в бинарном дереве

public static int findMaxSumPath(Node root, AtomicInteger max_sum)

{

// базовый случай: пустое дерево

if (root == null) {

return 0;

}

// найти максимальную сумму пути от узла к листу, начиная с левого потомка

int left = findMaxSumPath(root.left, max_sum);

// найти максимальную сумму пути от узла к листу, начиная с правого потомка

int right = findMaxSumPath(root.right, max_sum);

// важно вернуть максимальную сумму пути от узла к листу, начиная

// из текущего узла

// случай 1: левый дочерний элемент равен нулю

if (root.left == null) {

return right + root.data;

}

// случай 2: правый дочерний элемент равен нулю

if (root.right == null) {

return left + root.data;

}

// найти максимальный суммарный путь «сквозь» текущий узел

int cur_sum = left + right + root.data;

// обновить путь максимальной суммы, найденный до сих пор (обратите внимание, что путь максимальной суммы

// «исключение» текущего узла в поддереве с корнем в текущем узле

// уже обновляется, так как мы выполняем обход в обратном порядке)

max_sum.set(Math.max(cur_sum, max_sum.get()));

// случай 3: существуют и левый, и правый дочерние элементы

return Math.max(left, right) + root.data;

}

// Функция для возврата пути максимальной суммы между двумя листьями в бинарном дереве

public static int findMaxSumPath(Node root)

{

// использование `AtomicInteger` для получения результата, так как `Integer` передается

// значение в Java

AtomicInteger max_sum = new AtomicInteger(Integer.MIN_VALUE);

findMaxSumPath(root, max_sum);

return max_sum.get();

}

public static void main(String[] args)

{

/* Построим следующее дерево

2 3

-4 5 6

7 8

Node root = new Node(1);

root.left = new Node(2);

root.right = new Node(3);

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

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

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

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

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

System.out.println(findMaxSumPath(root));

}

Скачать Выполнить код

результат:

22

Python

import sys

# Класс для хранения узла бинарного дерева.

class Node:

def __init__(self, data, left=None, right=None):

self.data = data

self.left = left

self.right = right

# Рекурсивная функция для нахождения пути максимальной суммы между двумя листьями

# в бинарном дереве

def findMaxSumPath(root, max_sum=—sys.maxsize):

# Базовый случай: пустое дерево

if root is None:

return 0, max_сумма

# найти максимальную сумму пути от узла к листу, начиная с левого дочернего элемента

left, max_sum = findMaxSumPath(root.left, max_sum)

# найти максимальную сумму пути от узла к листу, начиная с правого потомка

right, max_sum = findMaxSumPath(root.right, max_sum)

# важно вернуть максимальную сумму пути от узла к листу, начиная с

# текущий узел

#, случай 1: левый дочерний элемент None

if root.left is None:

return (right + root.data), max_сумма

#, случай 2: правый дочерний элемент None

if root.right is None:

return (left + root.data), max_сумма

# найти максимальный суммарный путь «через» текущий узел

cur_sum = left + right + root.data

# обновляет путь максимальной суммы, найденный до сих пор (обратите внимание, что путь максимальной суммы

# «исключая» текущий узел в поддереве с корнем в текущем узле

# уже обновлен, так как мы выполняем обратный обход)

max_sum = max(cur_sum, max_sum)

#, случай 3: существуют и левый, и правый дочерние элементы

return (max(left, right) + root.data), max_sum

if __name__ == ‘__main__’:

»’ Construct the following tree

2 3

-4 5 6

7 8

»’

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.right = Node(—4)

root.right.left = Node(5)

root.right.right = Node(6)

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

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

print(findMaxSumPath(root)[1])

Скачать Выполнить код

результат:

22

Временная сложность приведенного выше решения равна O(n), куда n это общее количество узлов в бинарном дереве. Программа требует O(h) дополнительное место для стека вызовов, где h это высота дерева.

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования

Источник

Есть бинарное дерево, пусть оно будет сбаллансированное. Необходимо найти глубину дерева (максимальное расстояние от корня до листа) и вернуть все пути в дереве (их почти гарантированно несколько) с этой глубиной.

Структура ноды дерева

struct TreeNodeMod {
    int data;
    struct TreeNodeMod* leftChild;
    struct TreeNodeMod* rightChild;
};

Создается бинарное дерево

int * arr = new int[n];

for (size_t i = 0; i < n; i++) {
    arr[i] = i;
}

TreeNodeMod * head = CreateBalancedTree(arr, 0, n-1);

Функция создания дерева

TreeNodeMod * CreateBalancedTree(int arr[], int start, int end) {

if (arr == nullptr) {
    return nullptr;
}

if (end < start) {
    return nullptr;
}

int mid = (start + end) / 2;

TreeNodeMod *n = MakeNode(arr[mid]);

n->leftChild = CreateBalancedTree(arr, start, mid - 1);
n->rightChild = CreateBalancedTree(arr, mid + 1, end);

return n;
}

TreeNodeMod * MakeNode(int x) {
TreeNodeMod * n = new TreeNodeMod;
n->data = x;
n->leftChild = nullptr;
n->rightChild = nullptr;
return n;
}

Сам я дошел только до печати дерева по уровням

void PrintTreeByLevel(TreeNodeMod * n) {

int h = TreeHeight(n);

auto prnt = [](auto&& self, TreeNodeMod * n, int lvl){
    if (n == nullptr) {
        return;
    }
    if (lvl == 1) {
        std::cout << n->data << " ";
    }
    else {
        if (lvl > 1) {
            self(self, n->leftChild, lvl-1);
            self(self, n->rightChild, lvl-1);
        }
    }
};

for (int i = 1; i < h+1; i++) {
    prnt(prnt, n, i);
    std::cout << std::endl;
}

}

Возможно, для этого можно как-то модифицировать фукцию подсчета глубины дерева, но я не могу сообразить, как

size_t TreeHeight(TreeNodeMod * node) {

if (node == nullptr) {
    return 0;
}
else
{
    int lheight = TreeHeight(node->leftChild);
    int rheight = TreeHeight(node->rightChild);

    if (lheight > rheight)
        return(lheight + 1);
    else
        return(rheight + 1);
}

}

Буду рад любым подсказкам и советам.

Источник

Всем привет!

Дано двоичное дерево поиска. Ключи — целые числа. Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков.

Для начала я бы хотел уточнить:
1. путь может проходить как угодно по дереву, т е, например из левого дерева подниматься к корню и затем уходить в правое поддерево? Т е путю необязательно двигаться по связям вершин дерева?
2. вроде гарантируется, что одной из такой вершин будет лист, т к появление листа гарантировано увеличивает протяженность пути на +1. Два листа быть не может, т к у них будет равное число потомков = 0.
3. число потомков ведь может быть 0, когда берется лист
4. вроде не гарантируется, что эти две вершины будут лежать по разные стороны от корня исходного дерева? Например, ДДП, которое выродилось в ЛОС, там все элементы принадлежат одному из поддеревьев. Кстати, в случае ЛОС-ДДП максимальный путь будет проложен от корня до листа.

Какие мысли есть: найти кол-во потомков для КАЖДОГО узла исходного ДДП (это я знаю, как сделать). А даст ли это что-нибудь?! Наверное, придется еще получить номер уровня для каждого узла дерева, не знаю)

Может существует какое-то простое решение (типа одной рекурсивной функцией), решающее такую проблему??

P.S. возможно, что здесь нужно каким-то боком задействовать дин.прогр. + может быть, преобразовать структуру в граф (хотя дерево и так есть разновидность графа в любом случае)

Источник

msm.ru

Нравится ресурс?
Помоги проекту!

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code…/code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии «срочно надо», заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Поиск наидлиннейшего пути в бинарном дереве поиска

Подписаться на тему
Сообщить другу
Скачать/распечатать тему

Сообщ.
#1

,
09.12.20, 12:00

Всем хай! Сходу к делу!
Дано двоичное дерево поиска. Ключи — целые числа. Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков.

Может существует какое-то простое решение (типа одной рекурсивной функцией), решающее такую проблему??

Akina

Сообщ.
#2

,
09.12.20, 12:18

Цитата FasterHarder @ 09.12.20, 12:00

Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков.

Очевидно, речь идёт о пути, который посещает любой узел не более одного раза.

Изначально очевидно, что одним концом такого пути будет лист, а другим — узел, потомки которого листья (или единственный потомок — лист). так что для унификации мы просто ищем максимальный путь между двумя листьями, а потом отбрасываем единичку (любой из конечных листов заменяем на его родителя).
Далее — такой путь поднимается вверх по дереву до общего родителя, потом спускается.
Итог — следует перебирать все узлы, являющиеся би-родителем, для каждого находить максимальный по длине путь до листа в левой и правой ветви. Решением будет комбинация пары таких путей, которые показывают максимальную суммарную длину в пределах дерева.

Как бы я решал. Берём все листья. От каждого начинаем двигаться вверх (желательно делать это по уровням). На каждом родителе для дальнейшего движения из двух пришедших в него путей оставляем длиннейший, а текущую сумму сравниваем с текущей максимальной в аккумуляторе, и если она больше, то перезаписываем аккумулятор, кладя в него и новую макс. сумму, и оба составляющих её пути. По завершении в аккумуляторе будем иметь длиннейший путь (если таковых несколько — какой-то один из них, или можно запоминать все).

Сообщение отредактировано: Akina — 09.12.20, 12:26

FasterHarder

Сообщ.
#3

,
09.12.20, 12:32

Akina, спс за достаточно полное описание
би-родитель, это хто?) Вершина, имеющая левого и правого потомка?
2. Вот ты говоришь неоднократно «двигаться вверх», но структура дерева не имеет линка parent, а только left/right. Это ведь важно оказывается вроде

Добавлено 09.12.20, 12:38

Цитата Akina @ 09.12.20, 12:18

это красивый подход, но, что ты будешь делать, когда ДДП является ЛОСом? Там всего лишь 1 узел является листом…

AVA12

Сообщ.
#4

,
09.12.20, 15:32

Небольшие замечания к алгоритму, который предложил Akina:

Нет необходимости строить все возможные пути, а потом отбрасывать лишние. Достаточно знать высоты всех поддеревьев и «корень», через который проходит длиннейший путь. Чтобы этот путь восстановить, нужно спуститься из этого «корня» влево и вправо, каждый раз выбирая потомка с максимальной высотой и занося посещенную вершину в список пути. (После чего отбросить первый или последний лист).

Для поиска «корня» нужно обойти дерево в глубину. Для каждого узла/листа храним высоту его поддерева H (изначально 0). Отдельно храним длину лучшего найденного пути L (изначально 0) и ссылку на «корень» этого пути P. Каждый раз, поднимаясь из потомка к родителю, пишем в H родителя MAX(H_родителя, H_потомка + 1). Когда посещены оба потомка, длина максимального пути, для которого узел является «корнем», равна сумме H дочерних узлов. Если эта длина больше L, то в L пишем эту длину, а в P пишем ссылку на узел.

FasterHarder

Сообщ.
#5

,
09.12.20, 15:54

Цитата AVA12 @ 09.12.20, 15:32

Для поиска «корня» нужно обойти дерево в глубину.

именно такой вариант дали на одном из форумов, процитирую:
«Обходим дерево в глубину, проставляя в каждый узел высоту.
От корня начинаем спускаться к самому дальнему листу (выбирая на каждом шаге самого высокого потомка) и сравниваем максимальную длину пути с вершиной в данном узле с текущей максимальной длиной пути. Останавливаемся, когда становится известно, что длиннее уже не получится.»

а также готовую рекурсивную функцию на шарпе, но там такая функция, что переписать на Си, например, пока непонятно как)

Akina

Сообщ.
#6

,
09.12.20, 16:37

Цитата FasterHarder @ 09.12.20, 12:32

би-родитель, это хто?) Вершина, имеющая левого и правого потомка?

Он

Цитата FasterHarder @ 09.12.20, 12:32

ты говоришь неоднократно «двигаться вверх», но структура дерева не имеет линка parent, а только left/right

Дерево — всего лишь исходные данные, к которым никто не мешает прилепить что-то дополнительное. Кстати, отсутствие линка на родителя — обычай, но не догма.

Цитата FasterHarder @ 09.12.20, 12:32

что ты будешь делать, когда ДДП является ЛОСом? Там всего лишь 1 узел является листом…

Обработаю этот единственный особый случай отдельно.

Цитата AVA12 @ 09.12.20, 15:32

Нет необходимости строить все возможные пути, а потом отбрасывать лишние. Достаточно знать высоты всех поддеревьев и «корень», через который проходит длиннейший путь.

Всё равно предобработка…

Сообщение отредактировано: Akina — 09.12.20, 16:37

FasterHarder

Сообщ.
#7

,
10.12.20, 06:22

В общем у меня ВРОДЕ получилось, но сделал я, конечно, не так, как мне тут подсказывали, т к в приведенных подсказках везде нужно было подниматься от потомка к родителю. Разумеется, алгоритм неоптимальный получился) + я вот далеко не уверен, что он работает корректно на всех конфигах ДДП

Просто находил ДЛЯ КАЖДОГО УЗЛА ДДП высоты левого и правого поддерева, суммировал их и проверял с максимальной. На рис., как я понимаю, длиннейший путь = 6, ну, прожка так и выдает.

Единственное, что мне не оч.нравится, что пришлось задействовать глобальную переменную, т е не чистая рекурсия получилась.

int maxP = 0;

int GMP(const TREE* root)

{

if(root != NULL)

{

LPK(root->left);

LPK(root->right);

int currentP = GH(root->left) + GH(root->right) — 1; // вот эта «-1» связана с логикой функции G(et)H(eight) + потомки не должны быть листьями оба одновременно, поэтому одного из потомка «поднимаем» на 1 уровень вверх, отбирая у пути одну единицу движения

if(currentP > maxP)

maxP = currentP;

return maxP;

}

else

return 0;

}

Прикреплённая картинка