Ниже приведён текст программы на 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, то граф полный.
}
}
}
-------------------------------------------------------------------------------------
бинарные деревья
Модератор: Absurd
> Бинарный граф явл. правильным тогда и только тогда,
> когда кол-во его вершин равно 2**k-1,
ну вот, я же сказал велосипед переизобретаем
> когда кол-во его вершин равно 2**k-1,
ну вот, я же сказал велосипед переизобретаем
michael, ну тебе же уже все дали!
количество узлов посчитать можешь? ( Amount )
log2(от этого количества) посчитать можешь? ( Height )
сравнить количество узлов Amount с 2*Height - 1 можешь?
ну так в чем тогда проблема? в том что CountNodes рекурсивный? Так его легко можно переписать без рекурсии.
количество узлов посчитать можешь? ( Amount )
log2(от этого количества) посчитать можешь? ( Height )
сравнить количество узлов Amount с 2*Height - 1 можешь?
ну так в чем тогда проблема? в том что CountNodes рекурсивный? Так его легко можно переписать без рекурсии.