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

Question

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

Я думаю, что вот так:

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 узла (-ов) ДО max = 2 ^ X - 1 узла (-ов)], где X представляет уровень

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

Answer 1

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

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

Возможно, вам нужен более убедительный и подробный ответ, но это суть.

Answer 2

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

Answer 3

Узел на уровне 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 или уровне K.