сколько узлов может иметь бинарное дерево на уровне n? Используйте индукцию, чтобы доказать ответ

Это домашнее задание, и у меня не было много времени, чтобы потратить на него, но я знаю некоторые ответы и мне нужна небольшая помощь, пожалуйста.

Я думаю так, предположим, что у нас есть:

1 узел ----> Уровень 1

2,3 узла ----> Уровень 2

3,4,5,6,7 узлов ----> уровень 3

4,5,6,.....,15 узлов ----> Уровень 4

5,6,7,8,9,.....,31 узел ----> Уровень 5

Интервал узлов (узлов) от [min=X узел (узлы) TO max = 2^X - 1 узел (узлы)], где X представляет уровень

с этого момента я запутался, как завершить


data-structures tree binary-tree treenode
person Bobj-C    schedule 29.12.2010    source источник
comment
Этот вопрос кажется не по теме, потому что он касается теории графов и математики.   -  person Ondrej Janacek    schedule 06.02.2014

Ответы (3)


arrow_upward
4
arrow_downward

Насколько я помню, чтобы использовать индукцию, вы должны доказать N-й случай и N + 1-й случай. И мы видим для любого N, что на N + 1-м уровне их ровно в два раза больше. Таким образом, показано как 2 ^ (N + 1) / 2 ^ N = 2

Общее количество узлов можно найти, взяв сумму от n = 0 до N - 1 из 2 ^ n

Вы, вероятно, хотите более убедительный и подробный ответ, но это суть.

person EnabrenTane    schedule 29.12.2010

arrow_upward
1
arrow_downward

Похоже, вы правы. Минимальное количество узлов, которое может иметь бинарное дерево, равно n, а максимальное — 2^n-1.

person atx    schedule 29.12.2010
comment
То, что вы показали, является доказательством по индукции, вы должны формализовать его немного больше, например, в утверждении. - person atx; 29.12.2010
comment
если я хочу сказать, что в N+1 у меня есть от [N+1 до (2^(N+1)-1)] я запутался в двух значениях [от N+1 до (2^(N+1)-1) ] и как доказать равенство - person Bobj-C; 29.12.2010

arrow_upward
0
arrow_downward

У узла на уровне n в бинарном дереве будет n предков. Доказательство по индукции: Показать P (0): узел на уровне 0 не имеет предков. (Это верно, потому что это корень.) Показать P(1): узел на уровне 1 имеет одного предка. (Это верно; предком является корень, его отец, который находится на уровне 0.) Предположим, что P(K): узел на уровне K имеет K предков. Его отец находится на уровне K - 1. Докажите P(K+1): узел на уровне K+1 будет иметь на одного предка больше, чем узел на уровне K. K+1-й элемент будет иметь родителя на уровне (K+ 1)-1 или уровень К.

person jaxkewl    schedule 28.08.2016