двоичное дерево с высотой N - Помощь студентам

NiCola999 · 18.12.2009, 17:46

Здравствуйте. Меня интересует вопрос, есть ли какой-нибудь алгоритм построения двоичного дерева поиска с заданной высотой. Сейчас меня не интересует код построения, мне интересно как это делается на листе бумаги. Допустим надо построить дерево высотой 3 с ключами от 1 до 15, как в этом случае надо рассуждать ?

NiCola999 · 18.12.2009, 18:46

ап....................

NiCola999 · 18.12.2009, 19:19

поправка, симметричное дерево
допустим корень будет 8, тогда дерево будет такое

Код:

                                          8
                               4                   12
                        2           6        10         14
                      1   3      5   7    9   11    13  15

как рассуждать при построении такого дерева, если начинать с корня ?

Анатоль · 20.12.2009, 09:58

Знаешь, что такое бинарная куча?
это массив, у которого M[i] <= M[2*i+1] и M[i] <= M[2*i].
то есть наверху всегда самый маленький элемент. Чтобы создать такую кучу, достаточно увеличить колво элементов массива, присвоить последнему элементу массива заданное значение и пропихивать его вверх
до тех пор пока не будет выполняться неравенство для этого элемента.
M[i] >= M[i div 2].
Только у 1ого элемента нету предка. У всех остальных ровно 1 предок, и не более 2ух сыновей. Каждый сын больше своего предка. Смотри в гугле
Пирамидальную сортировку. Всё поймёшь.

18.12.2009, 17:46	#1
NiCola999 Не Участник клуба Регистрация: 29.10.2009 Сообщений: 1,456	двоичное дерево с высотой N Здравствуйте. Меня интересует вопрос, есть ли какой-нибудь алгоритм построения двоичного дерева поиска с заданной высотой. Сейчас меня не интересует код построения, мне интересно как это делается на листе бумаги. Допустим надо построить дерево высотой 3 с ключами от 1 до 15, как в этом случае надо рассуждать ?

18.12.2009, 19:19	#3
NiCola999 Не Участник клуба Регистрация: 29.10.2009 Сообщений: 1,456	поправка, симметричное дерево допустим корень будет 8, тогда дерево будет такое Код: `8 4 12 2 6 10 14 1 3 5 7 9 11 13 15` как рассуждать при построении такого дерева, если начинать с корня ? Последний раз редактировалось NiCola999; 18.12.2009 в 19:24.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Двоичное дерево на си++	fesked	Помощь студентам	0	22.10.2009 23:44
двоичное дерево	s20	Помощь студентам	0	22.10.2009 03:51
Двоичное дерево поиска структур	lioshenka	Общие вопросы C/C++	3	15.08.2009 12:18
Двоичное дерево	afeg	Паскаль, Turbo Pascal, PascalABC.NET	0	19.12.2008 14:49

18.12.2009, 18:46	#2
NiCola999 Не Участник клуба Регистрация: 29.10.2009 Сообщений: 1,456	ап....................

20.12.2009, 09:58	#4
Анатоль Пользователь Регистрация: 17.12.2009 Сообщений: 74	Знаешь, что такое бинарная куча? это массив, у которого M[i] <= M[2i+1] и M[i] <= M[2i]. то есть наверху всегда самый маленький элемент. Чтобы создать такую кучу, достаточно увеличить колво элементов массива, присвоить последнему элементу массива заданное значение и пропихивать его вверх до тех пор пока не будет выполняться неравенство для этого элемента. M[i] >= M[i div 2]. Только у 1ого элемента нету предка. У всех остальных ровно 1 предок, и не более 2ух сыновей. Каждый сын больше своего предка. Смотри в гугле Пирамидальную сортировку. Всё поймёшь.