Developing.ru

Ниже приведён текст программы на C#.
Она подсчитывает кол-во вершин графа.

После получения этого числа надо использовать:
Теорема.
Бинарный граф явл. правильным тогда и только тогда,
когда кол-во его вершин равно 2**k-1,
где k - высота графа.
Док-во: почти очевидно

Если получено число 'N' и оно имеет такой вид, то граф правильный.
-------------------------------------------------------------------------------------
using System;

namespace chewProject1
{
public class BTree
{
public BTree v1;
public BTree v2;
public string nameNode;
public BTree(string name)
{
nameNode = name;
}

public static int CountNodes(BTree bTree)
{ // выдаёт кол-во вершин бинарного графа
// NB! рекурсивный метод!
int cnt=1; // текущая вершина

if ( (bTree.v1 != null) )
{// левая ветка
cnt += CountNodes(bTree.v1);
}
if ( (bTree.v2 != null) )
{// правая ветка
cnt += CountNodes(bTree.v2);
}

if ( (bTree.v1 == null) && (bTree.v2 == null) )
{// лист
return (1);
}
return (cnt);
}

public static void Main()
{
// заполняем дерево
BTree c1= new BTree("c1"); // лист
BTree c2= new BTree("c2"); // лист
BTree b1= new BTree("b1");
b1.v1 = c1;
b1.v2 = c2;
BTree d1= new BTree("d1"); // лист
BTree d2= new BTree("d2"); // лист
BTree b2= new BTree("b2");
b2.v1 = d1;
b2.v2 = d2;

BTree a1= new BTree("a1"); // корень
a1.v1 = b1;
a1.v2 = b2;

int n= BTree.CountNodes(a1);
Console.WriteLine("CountNodes: {0}", n);
// если n=2**k -1, то граф полный.
}
}
}
-------------------------------------------------------------------------------------

kod horowiy. No nado v TOY je funkzie vi4isliat' visotu dereva.
Ya v ot4aenie

> Бинарный граф явл. правильным тогда и только тогда,
> когда кол-во его вершин равно 2**k-1,

ну вот, я же сказал велосипед переизобретаем

ya znaiu 4to 2**k-1 no problema 4to visotu ya doljen pods4itat' v toy je funkzie

michael, ну тебе же уже все дали!
количество узлов посчитать можешь? ( Amount )
log2(от этого количества) посчитать можешь? ( Height )
сравнить количество узлов Amount с 2*Height - 1 можешь?
ну так в чем тогда проблема? в том что CountNodes рекурсивный? Так его легко можно переписать без рекурсии.

spasibo -razorabralsia