Деревья-Нелинейные структуры данных

@Zumuist · Регистрация: 23.09.2013

Author24 — интернет-сервис помощи студентам

Помогите пож-ста реализовать программу.
УСЛОВИЕ:
Сформировать и вывести на экран бинарное дерево поиска, элементами которого являются случайные числа. Количество элементов дерева вводится с клавиатуры.
Реализовать прямой обход созданного дерева.

@Algoritmer · 07.10.2013, 11:38

Примерно так:

C++

struct Node
{
double value;
Node *left, *right;
};
//-ф-я создания
Node *createTree(int n)
{ 
if(n<=0) return NULL;
Node *Top=new Node;
Top->value=random(100);
int ln, rn=(n-1)/2;
if((n-1)%2==0) ln=rn; 
else ln=rn+1;
Top->left=createTree(ln);
Top->right=createTree(rn);
return Top;
}
//---обход напишешь по аналогии
 
//вызывать так:
void main()
{
    int n;
  cout<<"kolichestvo uzlov = ";
  cin>>n;
  srand(); //кажеться так называется эта ф-я, но точно не помню
  Node *Top=createTree(n);
}

@Zumuist · 07.10.2013, 13:46 **[ТС]**

на

C++

srand()

компилятор ругается.

Добавлено через 3 минуты
Наверно имеется ввиду

C++

rand()

@Zumuist · 07.10.2013, 14:16 **[ТС]**

Так выглядит?? В main явно наверно что-то ещё дописать нужно.

C++

#include <iostream.h>
#pragma hdrstop
 struct Node
{
double value;
Node *left, *right;
};
//-ô-ÿ ñîçäàíèÿ
Node *createTree(int n)
{
if(n<=0) return NULL;
Node *Top=new Node;
Top->value=random(100);
int ln, rn=(n-1)/2;
if((n-1)%2==0) ln=rn;
else ln=rn+1;
Top->left=createTree(ln);
Top->right=createTree(rn);
return Top;
}
 
//---------------------------------------------------------------------------
 
#pragma argsused
int main(int argc, char* argv[])
{
 int n;
  cout<<"kolichestvo uzlov = ";
  cin>>n;
  rand();
  Node *Top=createTree(n);
       system("pause");
       return 0;
}

@Algoritmer · 07.10.2013, 17:48

Всё-таки там должен быть srand(). Нужно подключить ещё <time.h>

Добавлено через 1 минуту
Точнее вот так:

C++

1	srand(time(NULL))

Смотри: Srand

Добавлено через 1 минуту

Сообщение от Zumuist

В main явно наверно что-то ещё дописать нужно

Читай строку 20 в моем коде. Я написал тебе создание дерева. Ты по аналогии напиши его обход и вывод на экран

@Zumuist · 08.10.2013, 14:30 **[ТС]**

Тоже самое выводит

Добавлено через 4 часа 31 минуту
Пробую, не получается вывести. Ошибку выводит.

@Algoritmer · 08.10.2013, 17:46

Сообщение от Zumuist

Пробую, не получается вывести. Ошибку выводит

Ну так покажи код, как пробуешь (это должна быть рекурсивная функция обхода дерева и поэлементного вывода) и в твоем коде уже поищем ошибку

@Zumuist · 09.10.2013, 09:57 **[ТС]**

где ошибка??

C++

//---------------------------------------------------------------------------
#include <iostream.h>
#include <time.h>
#pragma hdrstop
 struct Node
{
double value;
Node *left, *right;
};
//-ô-ÿ ñîçäàíèÿ
Node *createTree(int n)
{
if(n<=0) return NULL;
Node *Top=new Node;
Top->value=random(100);
int ln, rn=(n-1)/2;
if((n-1)%2==0) ln=rn;
else ln=rn+1;
Top->left=createTree(ln);
Top->right=createTree(rn);
return Top;
}
 
void pr1 (Node *Top) {  // префиксный обход 
if Top!=0 {
cout << Top ->Elem;
pr1 (Top->left);
pr1 (Top ->Right);
   }
void pr2 (Node *Top) {   //симметричный обход
if Top!=0 {
pr2 (Top ->left);
cout << Top ->Elem;
pr2 (Top ->Right);
   }
   void pr3 (Node *Top) { // постфиксный обход
if Top!=0 {
pr3 (Top ->Left);
pr3 (Top->Right);
cout <<Top ->Elem;
   }
 }
 
//---------------------------------------------------------------------------
 
#pragma argsused
int main(int argc, char* argv[])
{
 int n;
  cout<<"kolichestvo uzlov = ";
  cin>>n;
  srand(time(NULL));
  Node *Top=createTree(n);
   cout << Top;
       system("pause");
       return 0;
}
//---------------------------------------------------------------------------

@govorov · 09.10.2013, 10:08

По-моему еще нужно <stdlib.h> подключить. srand() из этой библиотеки)

@Zumuist · 09.10.2013, 10:10 **[ТС]**

C++

//---------------------------------------------------------------------------
#include <iostream.h>
#include <time.h>
#pragma hdrstop
 struct Node
{
double value;
Node *left, *right;
};
//-ô-ÿ ñîçäàíèÿ
Node *createTree(int n)
{
if(n<=0) return NULL;
Node *Top=new Node;
Top->value=random(100);
int ln, rn=(n-1)/2;
if((n-1)%2==0) ln=rn;
else ln=rn+1;
Top->left=createTree(ln);
Top->right=createTree(rn);
return Top;
}
 
void pr1 (Node *Top) {  // ïðåôèêñíûé îáõîä
if (Top!=0) {
cout << Top;
pr1 (Top->left);
pr1 (Top ->right);
   }
   }
void pr2 (Node *Top) {   //ñèììåòðè÷íûé îáõîä
if (Top!=0) {
pr2 (Top ->left);
cout << Top;
pr2 (Top ->right);
   }
   }
   void pr3 (Node *Top) { // ïîñòôèêñíûé îáõîä
if (Top!=0) {
pr3 (Top ->left);
pr3 (Top->right);
cout <<Top;
   }
 }
 
//---------------------------------------------------------------------------
 
#pragma argsused
int main(int argc, char* argv[])
{
 int n;
  cout<<"kolichestvo uzlov = ";
  cin>>n;
  srand(time(NULL));
  Node *Top=createTree(n);
   cout << Top;
       system("pause");
       return 0;
}
//---------------------------------------------------------------------------

Добавлено через 1 минуту
вот вроде так обход по элементам пишется?? А как вывод поэлементно сделать??

@Algoritmer · 09.10.2013, 10:57

Сообщение от Zumuist

А как вывод поэлементно сделать??

Что значит поэлементно? У тебя в коде 3 процедуры обхода: pr1, pr2, pr3
Вызывай в main() одну из них и будет тебе поэлементный вывод в зависимости от порядка обхода

@Zumuist · 09.10.2013, 22:21 **[ТС]**

Так, что ли?

C++

printf("\obhod_1=");
   cout << pr1<<endl;
   printf("\obhod_2=");
   cout << pr2<<endl;
    printf("\obhod_3=");
   cout << pr3<<endl ;

Но это явно не то.

Добавлено через 11 часов 9 минут
всё разобрался. Сделал. через print (рекурсивную функцию)

@Algoritmer · 10.10.2013, 11:30

Сообщение от Zumuist

Но это явно не то.

Разумеется, это не то. Вы, извините за выражение, содрали где-то функции pr1, pr2, pr3, или Вам их кто-то написал, и даже не удосужились прочитать, что в них в средине.
Что по вашему должно произойти, когда выпишите "cout << pr1"?
pr1 у Вас возвращает void, т.е. не возвращает ничего.
Но в pr1 (точно так же в pr2, pr3) уже содержится cout .
Вам достаточно было просто вызвать одну из них без всякого cout

@Zumuist · 10.10.2013, 12:03 **[ТС]**

Я в дальнейшем так и сделал.

Добавлено через 3 минуты

Сообщение от Algoritmer

Разумеется, это не то. Вы, извините за выражение, содрали где-то функции pr1, pr2, pr3, или Вам их кто-то написал, и даже не удосужились прочитать, что в них в средине.
Что по вашему должно произойти, когда выпишите "cout << pr1"?
pr1 у Вас возвращает void, т.е. не возвращает ничего.
Но в pr1 (точно так же в pr2, pr3) уже содержится cout .
Вам достаточно было просто вызвать одну из них без всякого cout

C++

void print (Node *Top,int k)
{
    if (Top==NULL) return;
    else
    {
    print(t->l,++k);
    for (int i=0;i<k;++i) cout<<"___";
    cout<<Top->info<<endl;
    k--;
    }
    print(Top->right,++k); 
}
 void Show(node *&Tree)
{
    if (NULL==Tree)    return;    //Если дерева нет, выходим
 
    cout<<Tree->inf<<endl; 
    Show(Tree->left); 
    Show(Tree->right);

@Algoritmer · 10.10.2013, 12:43

Ну вот. Ф-я Show вполне прилично выглядит, и кстати, ничем не отличается от той, к-рая у Вас раньше называлась pr1

Единственный момент:

Сообщение от Zumuist

void print (Node *Top,int k)

Сообщение от Zumuist

void Show(node *&Tree)

У вас два разных типа для узла? (Node и node ) Зачем?

@Zumuist · 10.10.2013, 13:14 **[ТС]**

У меня один Node. Второй опечатка.

Добавлено через 4 минуты

Сообщение от Algoritmer

Ну вот. Ф-я Show вполне прилично выглядит, и кстати, ничем не отличается от той, к-рая у Вас раньше называлась pr1

Единственный момент:

У вас два разных типа для узла? (Node и node ) Зачем?

как-то так

C++

void push(int a,Node **Top)
{
    if ((*Top)==NULL) //Если дерева не существует
    {
        (*Top)=new Node;
        (*Top)->inf=a;
        (*Top)->left=(*Top)->right=NULL;
        return;
    }
     else  
        if (a<(*Top)->inf) push(a,&(*Top)->left);
        else push(a,&(*Top)->right);
}
 
 
void print (Node *Top,int k)
{
    if (Top==NULL) return;
    else
    {
    print(Top->left,++k);
    for (int i=0;i<k;++i) cout<<"__";
    cout<<Top->inf<<endl;
    k--;
    }

@Algoritmer 159 / 98 / 25 Регистрация: 07.03.2013 Сообщений: 513 Записей в блоге: 1
	10.10.2013, 12:43	15
	Ну вот. Ф-я Show вполне прилично выглядит, и кстати, ничем не отличается от той, к-рая у Вас раньше называлась pr1 Единственный момент: Сообщение от Zumuist void print (Node Top,int k) Сообщение от Zumuist* void Show(node *&Tree) У вас два разных типа для узла? (Node и node ) Зачем? 0

@Zumuist 2 / 2 / 0 Регистрация: 23.09.2013 Сообщений: 150
		1
	Деревья-Нелинейные структуры данных 07.10.2013, 11:17. Показов 3477. Ответов 15 Метки нет (Все метки) Помогите пож-ста реализовать программу. УСЛОВИЕ: Сформировать и вывести на экран бинарное дерево поиска, элементами которого являются случайные числа. Количество элементов дерева вводится с клавиатуры. Реализовать прямой обход созданного дерева. 0

@Zumuist 2 / 2 / 0 Регистрация: 23.09.2013 Сообщений: 150
	08.10.2013, 14:30 [ТС]	6
	Тоже самое выводит Добавлено через 4 часа 31 минуту Пробую, не получается вывести. Ошибку выводит. 0

@Algoritmer 159 / 98 / 25 Регистрация: 07.03.2013 Сообщений: 513 Записей в блоге: 1
	08.10.2013, 17:46	7
	Сообщение от Zumuist Пробую, не получается вывести. Ошибку выводит Ну так покажи код, как пробуешь (это должна быть рекурсивная функция обхода дерева и поэлементного вывода) и в твоем коде уже поищем ошибку 0

@govorov 25 / 25 / 2 Регистрация: 25.09.2013 Сообщений: 76
	09.10.2013, 10:08	9
	По-моему еще нужно <stdlib.h> подключить. srand() из этой библиотеки) 0

@Algoritmer 159 / 98 / 25 Регистрация: 07.03.2013 Сообщений: 513 Записей в блоге: 1
	09.10.2013, 10:57	11
	Сообщение от Zumuist А как вывод поэлементно сделать?? Что значит поэлементно? У тебя в коде 3 процедуры обхода: pr1, pr2, pr3 Вызывай в main() одну из них и будет тебе поэлементный вывод в зависимости от порядка обхода 0

@Algoritmer 159 / 98 / 25 Регистрация: 07.03.2013 Сообщений: 513 Записей в блоге: 1
	10.10.2013, 11:30	13
	Сообщение от Zumuist Но это явно не то. Разумеется, это не то. Вы, извините за выражение, содрали где-то функции pr1, pr2, pr3, или Вам их кто-то написал, и даже не удосужились прочитать, что в них в средине. Что по вашему должно произойти, когда выпишите "cout << pr1"? pr1 у Вас возвращает void, т.е. не возвращает ничего. Но в pr1 (точно так же в pr2, pr3) уже содержится cout . Вам достаточно было просто вызвать одну из них без всякого cout 0