Публикации по теме 'tree-traversal'
Обход дерева (структура данных)
Короткая остановка на переулке памяти:
Типы данных:
В программировании существует много типов структур данных, некоторые из наиболее распространенных включают в себя:
Массивы : набор элементов одного типа данных, хранящихся в смежной области памяти. Связанные списки: набор элементов, каждый из которых содержит ссылку на следующий элемент в списке. Стеки : структура данных по принципу "последний пришел - первый ушел" (LIFO). Очереди : структура данных в порядке поступления..
Обход древовидной структуры
Всем привет! В этой статье я просто хочу показать вам, как вы можете перемещаться по древовидной структуре в TypeScript тремя различными способами.
Часто на собеседовании можно встретить вопросы о древовидной структуре, и, несмотря на свою простоту, они могут ввести в ступор, если вы никогда с ней не сталкивались.
Прежде всего, давайте посмотрим, с чем мы будем иметь дело.
interface Tree<T> {
value: T,
children?: Tree<T>[]
}
const tree: Tree<number> = {..
Вопрос на собеседовании по программированию: объяснение обхода дерева в ширину
Для бинарных и небинарных деревьев
Несмотря на то, что в Интернете полно примеров вопросов для собеседования, советов и приемов их решения, чаще всего я нахожу эти объяснения довольно сложными и обескураживающими. Вот почему я решил сам решить некоторые вопросы интервью и попытаться объяснить их максимально простым и понятным языком. Примеры кода даны на JavaScript, но я объясняю каждый шаг простым английским языком, поэтому написать решение на любом языке программирования не составит..
JavaScript (часть 1): поиск в глубину в деревьях
Поиск в глубину был исследован в XIX веке французским математиком Шарлем Пьером Тремо в качестве стратегии решения лабиринтов . >
Поиск в глубину ( DFS ) — это алгоритм обхода или поиска в древовидных или графовых структурах данных. Алгоритм начинается с корневого узла (выбирая какой-либо произвольный узел в качестве корневого узла в случае графа) и исследует как можно дальше каждую ветвь перед возвратом .
В этом обходе дерева первым достигается входной корень...
Обход дерева в ширину и в глубину в Javascript
Когда мы ищем в дереве, чтобы определить, содержит ли оно определенный узел, мы можем построить два алгоритма. Мы можем пройти по дереву в ширину или в глубину.
Метод «сначала в глубину» предполагает спуститься по дереву как можно глубже, пока не зайдет в тупик. Как только он достигает нулевого значения, он запускается снова вверху и следует тому же процессу.
Метод «в ширину» изо всех сил старается оставаться как можно ближе к вершине. Он проходит по дереву по одной строке за раз и..
Вопросы по теме 'tree-traversal'
C++ TCL (библиотека контейнеров дерева): как пройти по дереву от узла прямо к корню
Я использую эту библиотеку для хранения информации о древовидной структуре:
http://www.datasoftsolutions.net/tree_container_library/overview.php
Вот упрощенная версия моего кода C++:
#include "tcl/sequential_tree.h"
// Node has some data...
1026 просмотров
schedule
05.06.2023
Как изменить алгоритм обхода дерева предварительного порядка для обработки узлов с несколькими родителями?
Я долго искал и не могу найти альтернативного решения. Мне нужен алгоритм обхода дерева таким образом, чтобы у узла могло быть более одного родителя, если это возможно (нашел отличную статью здесь: Хранение иерархических данных в базе данных )....
2238 просмотров
schedule
21.07.2023
Катаморфизм и обход дерева в Haskell
Я нетерпелив, с нетерпением жду понимания катаморфизма связанных с этим вопросом SO :)
Я практиковался только в начале учебника Real World Haskell. Так что, может быть, я собираюсь попросить слишком многого прямо сейчас, если бы это было так,...
3228 просмотров
schedule
11.07.2023
Python: превышена максимальная глубина рекурсии
У меня есть следующий код рекурсии, на каждом узле я вызываю sql-запрос, чтобы узлы принадлежали родительскому узлу.
вот ошибка:
Exception RuntimeError: 'maximum recursion depth exceeded' in <bound method DictCursor.__del__ of...
203290 просмотров
schedule
17.07.2022
Обход дерева порядка уровней для общего дерева с отображением уровня дерева за уровнем
Я хотел бы отображать древовидную структуру по уровням. Мой текущий код выполняет BFS или обход порядка уровней, но я не могу получить вывод для отображения древовидной структуры, такой как дерево. См. текущий вывод и ожидаемый вывод.
Моя идея...
5919 просмотров
schedule
07.04.2023
Возможно ли, чтобы обход до заказа был в том же порядке, что и обход после заказа?
Если T — упорядоченное дерево с более чем одним узлом. Возможно ли, что обход T в прямом порядке посещает узлы в том же порядке, что и обход T в обратном порядке? если "да", можете привести пример. И если «Нет», не могли бы вы объяснить, почему это...
7856 просмотров
schedule
07.06.2023
Как представить двоичные числа в С++ (используется для кодировщика Хаффмана)?
Я пишу свой собственный кодер Хаффмана , и до сих пор я создал дерево Хаффмана, используя minHeap чтобы вытолкнуть два узла с самой низкой частотой и создать узел, который ссылается на них, а затем отодвинуть новый узел назад на один (намылить,...
3232 просмотров
schedule
25.01.2024
Каков следующий шаг для этого дерева, согласно Моррису Инордеру?
Незадолго до того, как я сел писать код для обхода Морриса по порядку, я попробовал этот пример и немного смущен тем, как он будет работать в этом конкретном случае:
80
/ \
60 100
\ /
70 90
/
65...
70 просмотров
schedule
20.08.2022
Обход BST
Мне нужна ваша помощь. Возможно ли иметь двоичное дерево поиска, в котором обходы в предварительном порядке и в порядке генерируют один и тот же результат?
Я попытался взять пример дерева, состоящего из 7 узлов, и я пометил узлы от a до g .. это...
192 просмотров
schedule
12.08.2022
Существует ли алгоритм обхода дерева с фиксированным использованием памяти?
У меня есть первый узел дерева. Что-то такое:
class TreeNode {
int uniqueValue;
List<TreeNode> children;
}
Я хочу найти наиболее эффективный способ печати всех узлов дерева. Дерево может быть большим или ОЧЕНЬ БОЛЬШИМ. Он может...
881 просмотров
schedule
30.05.2022
Как итеративное углубление влияет на временную сложность?
У меня есть алгоритм обхода дерева, который обычно работает за O(b m ), где b — коэффициент ветвления, а m — максимальная глубина.
Используя итеративное углубление, этот алгоритм запускается снова и снова, m раз с увеличением глубины:
O(b m ) =...
1622 просмотров
schedule
07.01.2023
Построение дерева с обходом в порядке и перед порядком в Python3.x
Я пытаюсь построить дерево, используя обходы предварительного и неупорядоченного (список целых чисел). Вот что у меня есть на данный момент:
def build(preorder, inorder, heap): # Builds tree with the inorder and preorder traversal
if...
497 просмотров
schedule
07.10.2022
Как составить список всех ветвей дерева?
Возникла проблема с деревьями в Haskell. Есть дерево:
data Tree a b = Leaf a | Branch (b,Tree a b) (b,Tree a b)
deriving(Eq, Show)
tree = Branch
("A",Branch
("C",Leaf 3)
("D",Branch...
688 просмотров
schedule
10.06.2024
Как пройти дерево, хранящееся в базе данных SQL, с помощью Python?
У меня есть корневое дерево, хранящееся в SQL с использованием материализованного пути (сохранение строки пути для каждой строки).
Каков наилучший способ посетить каждый узел узла, не начиная каждый раз с корня? Подходит ли материализованный путь...
1015 просмотров
schedule
02.06.2022
преобразование дерева в data.frame в R
Прежде чем я напишу это сам, мне интересно, есть ли функция, которая уже это делает:
У меня есть древовидная структура, реализованная в виде вложенного списка списков. каждый узел имеет некоторые внутренние данные (например, его имя) и список...
1326 просмотров
schedule
07.09.2022
Как удалить путь в дереве, начиная с листа?
У меня есть объекты, организованные в виде дерева (не бинарного). Каждый узел имеет набор свойств Children и Parent. Все это уже представлено в TreeView. Я хотел бы щелкнуть лист и удалить его таким образом, чтобы лист удалялся, он поднимался к...
140 просмотров
schedule
03.09.2022
Обход дерева Java
Я работаю над API, в котором я генерирую запрос на основе дерева условий, полученного в запросе. Ниже приведен формат дерева:
Это должно быть переведено в SQL-запрос следующим образом:
WHERE (a>b OR c<d) AND (e>f OR g<h)...
486 просмотров
schedule
18.10.2022
Функции высшего порядка в обходе дерева
Как бы я мог создавать общие операции дерева, такие как вставка и поиск, при передаче функций, чтобы уменьшить избыточность. Например, рекурсивная функция вызывает себя на левой ветви, когда переданное значение больше, чем текущий узел. Если бы я...
299 просмотров
schedule
31.10.2022
Как найти n-й узел в небинарном дереве?
Я знаю, как пройти по двоичному дереву, используя ответ здесь , но если я хочу остановиться, скажем, на 10-м узле в обходе предварительного заказа, как мне это сделать?
114 просмотров
schedule
06.08.2023
Как найти n-й узел в двоичном дереве?
Я хочу найти n-й узел / элемент в двоичном дереве. Не n-е наибольшее / наименьшее, например, просто n-е в порядке порядка.
Как это сделать? Можно ли сохранить одну функцию? Многие функции используют внешнюю переменную для отслеживания итераций...
5998 просмотров
schedule
16.05.2023