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

Поиск всех путей максимальной длины в дереве

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

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

Поиск ключа в бинарном дереве поиска
Здравствуйте! Помогите ещё с задачками) 1.Поиск ключа в бинарном дереве поиска (точное.

Поиск суммы в бинарном дереве поиска
Сначала думал делать запоминанием прошлого значения, и сравнивать с новым значением. if.

Реализовать добавление и поиск элементов бинарном дереве поиска
Доброго времени суток . Задание по лабе — Реализовать добавление и поиск элементов бинарном дереве.

Трассировка пути в бинарном дереве
Добрый вечер. Ум за разум заходит уже. Прошу помощи. Реализовал нахождение максимального пути в.

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

Добавлено через 33 минуты
Можно и рекурсивно:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public (int length, int height) Solve(Node node) { if(node == null) return (0, 0); var left = Solve(node.Left); var right = Solve(node.Right); var height = Math.Max(left.height, right.height) + 1; var length1 = Math.Max(left.length, right.length); var length2 = left.height + right.height + 1; var length = Math.Max(length1, length2); return (length, height); } public class Node { public Node Left { get; set; } public Node Right { get; set; } }

Максимальная длина пути в поддереве — это (что больше) длина пути с вершиной в корне или максимальная длина пути в одном из поддеревьев.

Источник

Максимальная сумма путей в двоичном дереве

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

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

Связанный пост:

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

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

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

Максимальная сумма путей, проходящих “через” узел, равна максимальному из следующего:

1. Значение узла.
2. Значение узла + максимальная сумма путей, “начиная” с его левого дочернего элемента.
3. Значение узла + максимальная сумма путей, “начиная” с его правого потомка.
4. Значение узла + максимальная сумма путей, “начинающаяся” с его левого дочернего элемента + максимальная сумма путей, “начинающаяся” с его правого дочернего элемента.

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

Источник