VPF::Высота бинарного дерева - Форум программистов

m9yt

Дата 13.3.2010, 18:09 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 173
Регистрация: 27.2.2010

Репутация: нет
Всего: нет

Всем привет.
В общем, нужно найти высоту идеально сбалансированного бинарного дерева(не дерева поиска).
Количество элементов ввожу с клавы.
Вот код программы, если что.

Код

#include <iostream>
#include<windows.h>
using namespace std;

struct point
{
int data;//информационное поле
point *left;//адрес левого поддерева
point *right;//адрес правого поддерева
};

point* Tree(int n, point *p)
{
    point *r;
    int nl,nr;
    if(n==0){p=NULL;return p;}
    nl=n/2;
    nr=n-nl-1;
    r=new point;
    cout<<"элемент:";
    cin>>r->data;
    r->left=Tree(nr, r->left);
    r->right=Tree(nl, r->right);
    p=r;
    return p;
}

void Print(point*p, int l) 
{
    if(p)
    {
        Print(p->left,l+5);
        for(int i=0;i<l;i++)
            cout<<" ";
        cout<<p->data<<"\n";
        Print(p->right,l+5);
    }
}

void main()
{
    SetConsoleOutputCP(1251);
    SetConsoleCP(1251);
    int n,i=0;
    cout<<"Задайте количество элементов дерева\n";
    cin>>n;
    point *root;
    root=new point;
    root=Tree(n, root);
    Print(root,1);
}

Модератор: не забываем пользоваться кнопочкой "Код"

Это сообщение отредактировал(а) bsa - 13.3.2010, 18:12

baldina

Дата 13.3.2010, 18:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

высота идеально сбалансированного двоичного дерева h=log2(n)
Само дерево тут не нужно, только число элементов

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

Это сообщение отредактировал(а) baldina - 13.3.2010, 18:20

m9yt

Дата 13.3.2010, 18:37 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 173
Регистрация: 27.2.2010

Репутация: нет
Всего: нет

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

Это сообщение отредактировал(а) m9yt - 13.3.2010, 18:38

baldina

Дата 13.3.2010, 21:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

конечно, целым. округляйте - получите целое.

bsa

Дата 14.3.2010, 11:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(baldina @ 13.3.2010, 21:54

)

округляйте - получите целое.

причем, в большую сторону.
Идеально сбалансированное дерево

M
bsa

m9yt, если ответ на вопрос получен, то пометь тему решенной

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »