Запись бинарного дерева в массив

@Tartygin · Регистрация: 08.10.2016

Студворк — интернет-сервис помощи студентам

Как можно записать элементы бинарного дерева в массив? Пробовал одну очень странную идею:

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void run(Tree *root){
    if(root){
        int a[k];
        int i = 0;
 
        while(root->Left){
            a[i] = root->Data;
            run(root->Left);
            i++;
        }
        while(root->Right){
            a[i] = root->Data;
            run(root->Right);
            i++;
        }
}

где k = 10.

Как можно понять это не работает и вообще я сомневаюсь что она делает то что надо(на экран ничего не выходит).

Прошу помочь с записью бинарного дерева в массив

@wlmn · 07.05.2017, 16:57

А каким образом его нужно записать? Просто данные считать в произвольном порядке?
Сразу оговорюсь, что сам в этом деле не профи, просто предложу вариант, который кажется мне логичным:
Насколько понял, у элементов дерева нет ссылки на родителя. И насколько помню, у каждого элемента не может быть 1 потомка. Либо 0, либо 2.
Тогда такой псевдоалгоритм:
Заводим массив переменной длины, в котором будут храниться ссылки. (назовем его второй массив, первый - с данными)
Если у корня 2 потомка, сохраняем корень в массив, идем влево. (Если нет, сохраняем данные корня, завершаем программу)
Пришли влево, повторяем.
В итоге прошли по левой ветви, получился массив ссылок на элементы дерева, которые, к тому же, имеют вторых, правых потомков, которых мы еще не задели.
Начиная с начала массива, по первой ссылке идем к правой дочерней вершине, повторяем алгоритм, каждый раз записывая ссылки на элементы в конец дерева. Удаляем корень из второго массива.
И т.д. пока во втором массиве не останется элементов.

@Tartygin · 07.05.2017, 17:40 **[ТС]**

Необходимо записать элементы бинарного дерева(только данные) в массив, т.е. дерево:
___________5
_____1 _________ 4
__2 ___ 3 ____ 6 ___ 10
надо представить, например, в виде массива 5,1,2,3,4,6,10.
Порядок не важен.

@wlmn · 07.05.2017, 17:44

Ну вроде то же самое, только массив ссылок читается с конца, а не с начала, как у меня.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@wlmn 23 / 23 / 3 Регистрация: 05.02.2017 Сообщений: 207
	07.05.2017, 16:57
	А каким образом его нужно записать? Просто данные считать в произвольном порядке? Сразу оговорюсь, что сам в этом деле не профи, просто предложу вариант, который кажется мне логичным: Насколько понял, у элементов дерева нет ссылки на родителя. И насколько помню, у каждого элемента не может быть 1 потомка. Либо 0, либо 2. Тогда такой псевдоалгоритм: Заводим массив переменной длины, в котором будут храниться ссылки. (назовем его второй массив, первый - с данными) Если у корня 2 потомка, сохраняем корень в массив, идем влево. (Если нет, сохраняем данные корня, завершаем программу) Пришли влево, повторяем. В итоге прошли по левой ветви, получился массив ссылок на элементы дерева, которые, к тому же, имеют вторых, правых потомков, которых мы еще не задели. Начиная с начала массива, по первой ссылке идем к правой дочерней вершине, повторяем алгоритм, каждый раз записывая ссылки на элементы в конец дерева. Удаляем корень из второго массива. И т.д. пока во втором массиве не останется элементов. 0

@Tartygin -12 / 0 / 0 Регистрация: 08.10.2016 Сообщений: 39
	07.05.2017, 17:40 [ТС]
	Необходимо записать элементы бинарного дерева(только данные) в массив, т.е. дерево: ___________5 _____1 _________ 4 __2 ___ 3 ____ 6 ___ 10 надо представить, например, в виде массива 5,1,2,3,4,6,10. Порядок не важен. 0

@wlmn 23 / 23 / 3 Регистрация: 05.02.2017 Сообщений: 207
	07.05.2017, 17:44
	Ну вроде то же самое, только массив ссылок читается с конца, а не с начала, как у меня. 0