Построить бинарное дерево из родительского массива
Дан целочисленный массив, представляющий двоичное дерево, такое, что отношение родитель-потомок определяется как (A[i], i) для каждого индекса i в массиве A , построить из него бинарное дерево. Значение корневого узла равно i если -1 присутствует в индексе i в массиве. Можно предположить, что входные данные, предоставленные программе, действительны.
- -1 присутствует в индексе 0, что означает, что корень бинарного дерева является узлом 0.
- 0 присутствует в индексах 1 и 2, что означает, что левый и правый потомки узла 0 — это 1 и 2.
- 1 присутствует в индексе 3, что означает, что левый или правый дочерний элемент узла 1 равен 3.
- 2 присутствует в индексах 4 и 5, что означает, что левый и правый потомки узла 2 — это 4 и 5.
- 4 присутствует в индексах 6 и 7, что означает, что левый и правый потомки узла 4 — это 6 и 7.
Соответствующее бинарное дерево:
Решение простое и эффективное – создайте n новые узлы дерева, каждый из которых имеет значения от 0 до n-1 , куда n — это размер массива, и сохранить их на карте или в массиве для быстрого поиска. Затем пройдите по данному родительскому массиву и постройте дерево, установив отношение родитель-потомок, определенное (A[i], i) для каждого индекса i в массиве A . Поскольку из одного входа можно сформировать несколько бинарных деревьев, решение должно построить любое из них. Решение всегда будет устанавливать левый дочерний узел для узла перед установкой его правого дочернего элемента.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
Источник
Бинарное дерево на основе массива
Всем привет. Начал изучать бинарное дерево на основе массива, нужна подсказка, я правильно начал делать? Или лучше использовать классы? И кто-нибудь может показать, для примера, как написать функцию добавления элемента. Поискал в интернете, но на основе массива толком ничего нет. Заранее спасибо!
1 2 3 4 5 6 7 8 9 10 11 12 13
#include using namespace std; const int MaxLength = 100; //Описание структуры struct Node { int Values[MaxLength]; int father; int left; int right; int free; // Индекс свободного списка Node() { father = left = right = free = 0; }; }; Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.
На основе вводимой с клавиатуры последовательности чисел до первого нуля формируется бинарное дерево поиска
Страшно каюсь, не подумайте что я ленивый тюлень и мне не хочется вникать в тему, обычно я никогда.
Перемещение элементов массива на бинарное дерево
Добрый день. Помогите пожалуйста, стоит задача сформировать минимальное пирамидальное дерево для.
Бинарное дерево с использованием статического массива
Помогите пожалуйста с программой. Мне дали вот такое задание: Cпроектировать структуру типа.
Бинарное дерево — структура данных с самоадресацией, массив ограничивает количество элементов, так что с помощью него никто Бин.дерево не реализовывает, это изврат.
Сообщение от Aidar 
Aidar, ссылку дайте. Бывают разреженные массивы и хеш-таблицы не основе BST но не наоборот.
Хотя массив бинарных деревьев указателей на бинарные деревья создать можно.
Сообщение от Aidar
IGPIGP, вот, что я имел виду(задание): реализовать все типовые операции над двоичным деревом поиска на базе одномерного массива.
Добавлено через 6 минут
MrGluck, а если не пройдет, вы поможете?
Добавлено через 5 минут
MrGluck, а если использовать динамический массив, допустим, вектор, это тоже изврат?
Сообщение от Aidar
IGPIGP, вот, что я имел виду(задание): реализовать все типовые операции над двоичным деревом поиска на базе одномерного массива.
На базе массива можно, например, организовать бинарный поиск если его упорядочить. Но дерево на основе массива делать можно лишь как дерево указателей на элементы. Это достаточно изощрённый подход, но он имеет право на жизнь если экземпляры имеют большой размер, а приходят как поток. Тогда можно быстро создавать хранилище как список или даже массив (агромадный статический), а поисковую структуру организовать в виде дерева указателей.
Я думаю, это не о том. Или Вы излагаете задачу языком далёким от её постановки.
Тут скорее всего либо бинарный поиск на массиве либо разреженный массив на основе дерева. Последнее технически и идеологически намного сложнее. Советую уточнить задание и точный текст — сюда, если не всё понятно.
Источник
Создание бинарного дерева из массива
Всем привет. Есть массив чисел, например 1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0, в котором записаны все узлы бинарного дерева если обходить его в прямом порядке. 0 означает отсутствие потомка. Никак не могу разобраться как из этого массива сделать бинарное дерево. Деревом у меня является массив объектов node с полями
int value,
node left,
node right,
node parent
Подскажите пожалуйста как это реализовать.
В рабочей программе добавить для дерева бинарного поиска нахождение отрицательных значений узлов дерева
Полностью готовая программа, но что дописать в мейне чтобы он выводил произведение отрицательных.
Вывод бинарного дерева в виде дерева
Помогите пожалуйста вывести дерево в консоль в виде дерева. Саму структуру я написал и обход.
создание Бинарного дерева
Здравствуйте! Разбираюсь с деревьями, необходимо реализовать функцию Create (T, n), где n-.
Сообщение было отмечено Cy83r как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
int[] arr = new int[] { 1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0 }; Node[] tree = new Node[arr.Length]; Node parent = null; for (int i = 0; i arr.Length; i++) { tree[i] = new Node(); // сслыка для удобства, что бы не писать вечно tree[i] var node = tree[i]; // присваиваем значение из массива node.value = arr[i]; // присваем раннее запомненого родителя node.parent = parent; // запоминаем текущий элемент как родителя parent = node.value == 0 ? node.parent : node; // Если есть родитель if (node.parent != null) { bool flag = true; while (flag) { // Сначала левый потомок, потом правый // Если есть потомки, поднимаемся по дереву вверх if (node.parent.left == null) { node.parent.left = node; flag = false; } else if (node.parent.right == null) { node.parent.right = node; flag = false; } else { node.parent = node.parent.parent; } } } } foreach (var item in tree) { Console.WriteLine(" left, right parent ", item.value, item.left, item.right, item.parent); }
Источник