Публикации по теме 'binary-tree'
Высота и глубина бинарного дерева
В этой статье мы рассмотрим высоту и глубину бинарных деревьев и то, как они рассчитываются.
Начнем с разницы между высотой и глубиной. Это довольно просто, так что давайте сразу углубимся в это — после некоторой терминологии:
Край — край считается линией между узлами, поэтому край является ссылкой от одного узла к другому. Ссылочный узел называется…
Двоичное дерево поиска: реализация в JavaScript
Двоичное дерево поиска — это особый тип двоичного дерева, в котором данные каждого правого дочернего узла больше, чем его родительский узел, а данные каждого левого дочернего узла меньше, чем его родительский узел.
Двоичное дерево поиска используется для выполнения операций поиска данных, поскольку оно может находить данные за время O (log (n)), что довольно эффективно. В BST выполняются следующие операции:
Вставка Удаление Идет поиск Обходы
Вставка в BST выполняется с..
Основы древовидной структуры данных
В отличие от массивов и связанных списков, дерево - это нелинейная структура данных, которая связывает узлы (или элементы) в отношениях родитель-потомок. Это означает, что данные организованы иерархически. Каждый родительский узел имеет указатель на дочерний узел и, следовательно, знает о нем.
Другой важной особенностью деревьев является тот факт, что они представляют собой рекурсивную структуру данных - такую же, как массивы и связанные списки! Другими словами, каждое дерево..
Суммируйте числа от корней до листьев
Суммируйте числа от корней до листьев
Проблема:
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123 .
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12 .
The root-to-leaf path..
Сумма путей II двоичного дерева
Проблема
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22 ,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Возвращение:
[
[5,4,11,2],
[5,8,4,5]
]
Решение:
*Давайте создадим массив, в котором будут храниться все возможности дерева, где сумма значений корневого узла и конечного узла..
Интуитивно понятный итеративный обход дерева
Обход бинарного дерева является основным элементом процесса технического собеседования во многих компаниях-разработчиках программного обеспечения, малых и крупных. Для любого, кто понимает рекурсию, семейство методов обхода довольно просто. Обычный поворот этих концепций, который больше проявляется в технических интервью, чем в наборах задач бакалавриата по информатике, - это довольно искусственное ограничение, которое требует реализации обходов с использованием итерации, а не рекурсии.
Я..
Вопросы по теме 'binary-tree'
Оценка выражений и обход дерева с использованием полиморфизма? (аля Стив Йегге)
Этим утром я читал Steve Yegge: When Polymorphism Fails , когда наткнулся на вопрос, который его коллега задавал потенциальным сотрудникам, когда они приходили на собеседование в Amazon.
В качестве примера полиморфизма в действии давайте...
6655 просмотров
schedule
04.06.2023
Допускаются ли повторяющиеся ключи в определении деревьев двоичного поиска?
Я пытаюсь найти определение двоичного дерева поиска и везде нахожу разные определения.
Некоторые говорят, что для любого заданного поддерева левый дочерний ключ меньше или равен корню.
Некоторые говорят, что для любого заданного поддерева правый...
120043 просмотров
schedule
10.05.2023
Обнаружение циклов в генеалогическом графе во время поиска в глубину
Я рекурсивно загружаю генеалогические данные лошадей. Для некоторых неправильных наборов данных моя рекурсия никогда не останавливается... и это потому, что в данных есть циклы.
Как обнаружить эти циклы, чтобы они не повторялись?
Я подумал о...
2672 просмотров
schedule
14.02.2023
Какова степень дерева? (Как в дереве ADT)
Я понимаю, что степень узла - это количество детей, которые у него есть.
Однако как определить степень дерева?
72287 просмотров
schedule
16.03.2023
Как определить, сбалансировано ли двоичное дерево?
Давно прошли те школьные годы. Получил работу айтишником в больнице. Сейчас пытаюсь заняться программированием. Сейчас я работаю над бинарными деревьями, и мне было интересно, как лучше всего определить, сбалансировано ли дерево по высоте.
Я...
132971 просмотров
schedule
14.07.2022
Найти первый нуль в двоичном дереве с ограниченной памятью
У меня есть двоичное дерево, в котором каждый узел может иметь значение.
Я хочу найти узел в дереве, который имеет значение null и находится ближе всего к корню. Если есть два узла на одинаковом расстоянии от корня, подойдет любой. Мне нужно...
669 просмотров
schedule
09.06.2022
Самая короткая ветвь в двоичном дереве?
Двоичное дерево может быть закодировано с использованием двух функций l и r , так что для node n , l(n) дает левый дочерний элемент n , r(n) дает правый дочерний элемент n .
Ветвь дерева - это путь от корня к листу, длина ветви до...
2624 просмотров
schedule
21.03.2023
Объекты, представляющие деревья
Существуют ли какие-либо объекты в С# (или в .net), представляющие двоичное дерево (или для любопытства) и n-арное дерево?
Я говорю не об элементах управления деревом представления, а как об объектах модели.
Если нет, есть ли хорошие внешние...
25097 просмотров
schedule
12.02.2022
реализация бинарного дерева поиска и Java
Я пытаюсь реализовать алгоритм BST, используя псевдокод Кормена, но у меня есть проблема.
Вот мой код для узла:
public class Node {
Node left;
Node right;
int value;
Node(int value){
this.value = value;...
20231 просмотров
schedule
21.05.2023
Возвращение рекурсивных троичных уродов
принять следующую функцию:
int binaryTree::findHeight(node *n) {
if (n == NULL) {
return 0;
} else {
return 1 + max(findHeight(n->left), findHeight(n->right));
}
}
Довольно стандартная рекурсивная treeHeight...
3328 просмотров
schedule
13.09.2023
Сбалансированный запрос дерева поиска, асимтотический анализ
Ситуация следующая:-
У нас есть n номеров, и мы печатаем их в отсортированном порядке. У нас есть доступ к сбалансированной структуре данных словаря, которая поддерживает операции поиска, вставки, удаления, минимума, максимума за время O(log...
222 просмотров
schedule
25.09.2022
Рекурсия и поиск по дереву в C?
Вид нового для деревьев и рекурсивных функций....
Я знаю основы создания стека и создания рекурсивных функций.
Я делаю предварительно упорядоченный обходной поиск, который должен возвращать адрес узла в дереве, когда искомое значение совпадает...
4136 просмотров
schedule
02.08.2022
сколько узлов может иметь бинарное дерево на уровне n? Используйте индукцию, чтобы доказать ответ
Это домашнее задание, и у меня не было много времени, чтобы потратить на него, но я знаю некоторые ответы и мне нужна небольшая помощь, пожалуйста.
Я думаю так, предположим, что у нас есть:
1 узел ----> Уровень 1
2,3 узла ----> Уровень 2...
32116 просмотров
schedule
19.06.2023
Код с объяснением поворота бинарного дерева (влево ИЛИ вправо)
Я пытался понять, как написать код для вращения двоичного дерева. Я просмотрел http://en.wikipedia.org/wiki/Tree_rotation и enfuzzled.com. смотрел на это 2 часа и смотрел на это несколько раз раньше. Я все еще вижу проблемы в статье в Википедии и...
30937 просмотров
schedule
07.08.2022
Количество способов заполнения бинарного дерева, чтобы сделать его bst
Нам дан набор из n различных элементов и непомеченное двоичное дерево с n узлами. Сколько можно заполнить дерево данным набором, чтобы оно стало двоичным деревом поиска?
1803 просмотров
schedule
16.05.2024
Преобразование двоичного дерева в зигзагообразном порядке в двусвязный список
Ii have a problem. i have to convert a Binary Tree in its zigZag format to a doubly linked list.
Given BT:
[1]
[2] [3]
[4] [5] [6] [7]
[8] [9] [10] [11] [12] [13] [14]...
1758 просмотров
schedule
06.09.2022
Случайное двоичное дерево поиска
у меня есть BST, где я вставляю ключи от 1 до n случайным образом (каждая перестановка выполняется с вероятностью 1/n!) . мой вопрос: почему результирующие деревья не равномерны , даже если перестановка однородна ?
947 просмотров
schedule
20.04.2023
полиморфное бинарное дерево поиска
У меня есть 2 класса, NonEmptyTree и EmptyTree, которые реализуют интерфейс Tree. Метод toString() в классе NonEmptyTree должен возвращать строку: key=>value key=>value key>value и т.д... Я не знаю, как удалить последний пробел в конце...
2564 просмотров
schedule
13.05.2024
Получение двоичного дерева из листинга предварительного или предварительного заказа
У меня вопрос по бинарным деревьям. поэтому я знаю о предварительном порядке, обратном порядке и порядке, который используется для построения двоичного дерева. Теперь, как мне получить неупорядоченный список дерева из списка дерева в обратном...
1009 просмотров
schedule
13.12.2022
Реализация двоичной кучи с использованием связанного списка
Возможный дубликат: Реализация связанного списка Binary Min Heap (возникают проблемы с манипулированием)
Привет,
У меня возникли проблемы с определением алгоритма, который даст мне расположение узла дерева в реализации связанного...
8674 просмотров
schedule
12.08.2023
