структуры данных двоичного дерева

Question

Кто-нибудь может дать мне доказательство того, что число узлов в строго двоичном дереве равно 2n-1, где n - число листовых узлов ??

Answer 1

Доказательство по индукции.Базовый случай, когда у вас есть один лист.Предположим, что это верно для k листьев.Тогда вы должны доказать для k + 1.Таким образом, вы получаете новый узел, его родитель и другой лист (по определению строгого двоичного дерева).Остальные листья k-1, и тогда вы можете использовать гипотезу индукции.Таким образом, фактическое количество узлов составляет 2 * (k-1) + 3 = 2k + 1 == 2 * (k + 1) -1.

Answer 2

просто перейдем к основам, если предположить, что всего имеется x узлов, тогда у нас есть n узлов со степенью 1 (листья), 1 со степенью 2 (корень) и xn-1 со степенью 3 (внутренние узлы) какдерево с x узлами будет иметь х-1 ребра.Итак, суммируя

n + 3 * (xn-1) + 2 = 2 (x-1) (приравнивая общее количество градусов)

, решая для x, мы получаем x = 2n-1

Answer 3

Я предполагаю, что вам действительно нужно что-то вроде доказательства того, что глубина - это log ₂ (N), где N - количество узлов.В этом случае ответ довольно прост: для любой заданной глубины D число узлов составляет 2 ^D .

Редактировать: в ответ на отредактированный вопрос: тот же факт в значительной степени применим,Поскольку число узлов на любой глубине равно 2 ^D , число узлов, расположенных дальше по дереву, равно 2 ^D-1 + 2 ^D-2 +...2 ⁰ = 2 ^D -1.Следовательно, общее количество узлов в сбалансированном двоичном дереве составляет 2 ^D + 2 ^D -1.Если вы установите n = 2 ^D , вы пройдете полный круг обратно к исходному уравнению.

Answer 4

To prove: A strictly binary tree with n leaves contains 2n-1 nodes.
Show P(1): A strictly binary tree with 1 leaf contains 2(1)-1 = 1 node.
Show P(2): A strictly binary tree with 2 leaves contains 2(2)-1 = 3 nodes.
Show P(3): A strictly binary tree with 3 leaves contains 2(3)-1 = 5 nodes.
Assume P(K): A strictly binary tree with K leaves contains 2K-1 nodes.
Prove P(K+1): A strictly binary tree with K+1 leaves contains 2(K+1)-1 nodes.
2(K+1)-1 = 2K+2-1
         = 2K+1
         = 2K-1 +2*
* This result indicates that, for each leaf that is added, another node must be added to the father of the leaf , in order for it to continue to be a strictly binary tree. So, for every additional leaf, a total of two nodes must be added, as expected.

Answer 5

Доказательство математической индукцией:

Утверждение о наличии (2n-1) узлов в строго двоичном дереве с n листовыми узлами верно для n = 1.{дерево только с одним узлом, т.е. корневым узлом}

давайте предположим, что утверждение верно для дерева с n-1 листовыми узлами.Таким образом, дерево имеет 2 (n-1) -1 = 2n-3 узла

, чтобы сформировать дерево с n конечными узлами, нам нужно добавить 2 дочерних узла к любому из конечных узлов в вышеприведенном дереве.Таким образом, общее количество узлов = 2n-3 + 2 = 2n-1.

, следовательно, доказано

Answer 6

Я думаю, что вы пытаетесь найти доказательство для: N = 2L - 1, где L - это число листовых узлов, а N - общее количество узлов в двоичном дереве.

Чтобы эта формула сохранялась, вам нужно наложить несколько ограничений на то, как дерево построено. Каждый узел является либо листом, что означает, что он не имеет дочерних элементов, либо это внутренний узел. Внутренние узлы имеют 3 Возможные конфигурации:

• 2 дочерних узла
• 1 дочерний и 1 внутренний узел
• 2 внутренних узла

Все три конфигурации подразумевают, что внутренний узел соединяется с двумя другими узлами. Это явно исключает ситуацию, когда узел подключается к одному дочернему элементу, как в:

   o
  /
 o

Неофициальное доказательство

Начните с минимального дерева из 1 листа: L = 1, N = 1 подставьте в N = 2L - 1 и увидите, что формула верна (1 = 1, пока все хорошо).

Теперь добавьте еще один минимальный кусок к дереву. Для этого вам нужно добавить еще два узла и дерево выглядит так:

    o
   / \
  o  o

Обратите внимание, что вы должны добавить узлы в парах, чтобы удовлетворить ограничения, установленные ранее. Добавление пары узлов всегда добавляет один лист (два новых листовых узла, но вы теряете один, так как он становится внутренним узлом). Узел роста прогрессирует как ряд: 1, 3, 5, 7, 9 ... но рост листьев составляет: 1, 2, 3, 4, 5 ... Именно поэтому формула N = 2L - 1 верно для этого типа дерева.

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

Answer 7

int N = 1000; insert here the value of N
int sum = 0; // the number of total nodes
int currFactor = 1; 
for (int i = 0; i< log(N);  ++i) //the is log(N) levels
{
   sum += currFactor;
   currFactor *= 2; //in each level the number of node is double than the upper level
}

if(sum == 2*N - 1)
{
    cout<<"wow that the number of nodes is 2*N-1";
}