Деревья

[qwertyuiop]

Парни,погмогите написать дерево с помощью структур......
Вобщем идея такая:

struct NODE
{
-----
---
NODE *left
NODE *right
NODE *parent
};

строить дерево должна функция,прототип у неё имеет след. вид

NODE *add(NODE *root, int val) -----прототип
{
if(root == 0)
{
NODE *p = (NODE*)malloc(sizeof(NODE));
p->NODE.left = 0;
............................
............................
return p;
Дальше в цикле пише примерно......Если число больше root,то строим в правую сторону и наоборот
root->left = add(root->left,val)
Наверное она рекурсивно вызываться должна

Забыл сказать на вход поступают числа,и нужно и разложить по этим узлам,а потом отсортировать,но это уже другое

Примерно представляю как это делается,но трудность в не знании синтаксиса,как правильно реализовать это всё....

Помогите ПЛЗ!!!
Заранее спасибо!!!

[Bikutoru]

По-моему, лучше использовать такую структуру

Код: Выделить всё

struct Node
{
     int number;
     Node* left;
     Node* right; 
};

Создаешь корень - элемент Node* с left = NULL, right = NULL, number=<первое число со входа>
А теперь строишь отсортированное дерево.Алгоритм может быть таким
1. Идти в корень
2. Если число больше числа в текущем узле, то идти в корень правого поддерева текущего элемента (если оно не существует, то создать его)
3. Иначе идти в корень левого поддерева текущего элемента (если оно не существует, то создать его)
4. Если поддерево не было создано на шаге 2 или 3, то вернуться к шагу 2
5. Записать число в корень текущего поддерева

Вот, вроде бы, и все, если я тебя правильно понял и нигде не напортачил...

[qwertyuiop]

Спасибо .......Алгоритм то я примерно представляю...
Но хотелось бы увидеть как это всё будет выглядеть на бумаге....

[Bikutoru]

Но хотелось бы увидеть как это всё будет выглядеть на бумаге....

Т.е.?.. Код что ли?.. Я бы сделал примерно так:

Код: Выделить всё

//Для простоты
#define input_count 10
int input&#91]

[qwertyuiop]

Bikutoru, Спасибо большое....
Завтара с утреца буду разбираться.....

Очень благодарен!!!

[Monopo]

А скажите, как можно осуществить ввод-вывод элементов в-из дерево, если оно не бинарное и у каждого элемента может быть произвольное количество потомков??

[Romeo]

Тогда у каждой вершины можно сделать список дуг. Например так.

Код: Выделить всё

struct Edge;

struct Vertex
{
   int data;
   Edge* edges;
};

struct Edge
{
   int data;
   Node* dest;
   Edge* next;
};

В первом случае data - некое поле, содержащее информацию о вершине, например её порядковый номер. Во втором случае data - это некое число, содержащее инофрмацию о дуге, например её длина.

[Monopo]

А можно это все в класс поместить?? Значение в вершине, указатель на массив потомков, количество потомков?? Например как-нибудь так.. :

Код: Выделить всё

typedef  int TreeltemType;

class Vertex
{
        private:
	TreeltemType item; //Значение в вершине
        int count; // Число потомков
	Vertex *ch; // Указатель на потомков
        public:
	Vertex():item(0),count(0),ch(NULL){};
	Vertex(const TreeltemType& nodeltem,int n,Vertex *T):
	item(nodeltem),count(n),ch(T){};
        // ..Методы..
};

И как осуществить именно ввод значений в дерево, допустим, целочисленное?? Как пользователю предоставить ввести любую вершину самому?? Он ведь см выбрать должен, чего и куда вводить. Но прежде он должен увидеть то, что уже имеется.

[Monopo]

road.h:

Код: Выделить всё

#ifndef _ROAD_H_ 
#define _ROAD_H_

#include "string.h"
#include "iostream"

using namespace std;

int **troad;
string *tname;
int tempcount;

#endif // _ROAD_H_

print.cpp:

Код: Выделить всё

#include "road.h"

void Print(int& count)
{
        printf("   ");
        for(int p=0;p<count;p++)
                cout<<tname[p]<<" ";
        printf("\n");
        for(int y=0;y<count;y++)
        {
                cout<<tname[y]<<"  ";
                for(int z=0;z<count;z++)
                        cout<<troad[y][z]<<" ";
                cout<<endl;
        }
}

print.h:

Код: Выделить всё

#ifndef _PRINT_H_
#define _PRINT_H_

void Print(int& count);

#endif // _PRINT_H_

cway.h:

Код: Выделить всё

#ifndef _CWAY_H_
#define _CWAY_H_

bool CheckWay(string& city1,string& city2,int& count);

#endif // _CWAY_H_

cway.cpp:

Код: Выделить всё

#include "road.h"

bool CheckWay(string& city1,string& city2,int& count)
{
        int f1=-1,f2=-1;
        for(int a=0;a<count;a++)
        {
                if(tname[a]==city1)
                        f1=a;
                if(tname[a]==city2)
                        f2=a;
                if((f1>0)&&(f2>0))
                        break;
        }
        if(((f1)>=0)&&((f2)>=0))
        {
                troad[f1][f2]=1;
                troad[f2][f1]=1;
                return true;
        }
        else return false;
}

gamg.h:

Код: Выделить всё

#ifndef _GAMG_H_
#define _GAMG_H_

#include "road.h"

bool CheckGamGraf(int& iX,int& count, int* label);

#endif // _GAMG_H_

gamg.cpp:

Код: Выделить всё

#include "road.h"

bool CheckGamGraf(int& iX,int& count, int* label)
{
        label[iX]=2;
        bool L=false;
        tempcount++;
        for(int i=0;i<count;i++)
        {
                if(troad[iX][i]==1)
                {
                        if(i==0)
                                if(tempcount==count)
                                        return true;
                        if(label[i]==0)
                        {
                                L=CheckGamGraf(i,count,label);
                                if(L==true)return true;
                        }
                }
        }
        tempcount--;
        label[iX]=0;
        return L;
}

Makefile:

Код: Выделить всё

#Makefile for GamGraf project

GamGraf: print.o cway.o gamg.o main.o
	g++ -o GamGraf print.o cway.o gamg.o main.o

main.o: main.cpp
	g++ -c main.cpp

gamg.o: gamg.cpp
	g++ -c gamg.cpp

cway.o: cway.cpp
	g++ -c cway.cpp

print.o: print.cpp
	g++ -c print.cpp

clean:
	rm -f *.o GamGraf

Столкнулся с проблемой мультиопределения глобальных указателей на стадии сборки объектных файлов. #pragma once дает тот же эффект. В принципе оно и понятно. Но как устранить неполадку я так и не додумалсо.

[Monopo]

main.cpp:

Код: Выделить всё

#include "road.h"
#include "print.h"
#include "gamg.h"
#include "cway.h"

int main()
{
        int count=0;
        int out=0;
        char c;
        while(out!=1)
	{
		printf("a - Vertex++\n");
                printf("p - Print\n");
		printf("r - Make roads\n");
                printf("g - Gamilton's graph\n");
		printf("c - EXIT\n");
                printf("\n>>\n");
		cin>>c;
                printf("\n");
		switch (c)
		{
			case 'a':
                        {
                                int **ct;
                                string *cn;
                                if(count!=0)
                                {
                                        ct=new int*[count];
                                        for(int h=0;h<count;h++)
                                                ct[h]=new int[count];
                                        cn=new string[count];
                                        for(int i=0;i<count;i++)
                                        {
                                                ct[i]=troad[i];
                                                for(int q=0;q<count;q++)
                                                        ct[i][q]=troad[i][q];
                                                cn[i]=tname[i];
                                        }


                                }
                                count++;
                                tname=new string[count];
                                troad=new int*[count];
                                for(int j=0;j<count;j++)
                                        troad[j]=new int[count];
                                if(count!=1)
                                {
                                        for(int k=0;k<count-1;k++)
                                        {
                                                for(int kk=0;kk<count-1;kk++)
                                                        troad[k][kk]=ct[k][kk];
                                                troad[k][count-1]=0;
                                                tname[k]=cn[k];
                                        }
                                        for(int j=0;j<count-1;j++)
                                                delete ct[j];
                                        delete[]ct;
                                        delete[]cn;
                                }
                                troad[count-1]=new int[count];
                                for(int x=0;x<count;x++)
                                        troad[count-1][x]=0;
                                printf("Enter the name of the point> ");
                                cin>>tname[count-1];
                                break;
                        }
                        case 'p':
                        {
                                Print(count);
                                break;
                        }
                        case 'g':
                        {
                                int *label=new int[count];
                                for(int j=0;j<count;j++)
                                        label[j]=0;
                                tempcount=0;
                                bool Gam=false;
                                int iX=0;
                                Gam=CheckGamGraf(iX,count,label);
                                if(Gam==true)
                                        printf("This is Gamilton's graph\n");
                                else printf("This is NOT Gamilton's graph\n");
                                delete []label;
                                break;
                        }
                        case 'r':
                        {
                                bool way=false;
                                printf("Don't remember that every road have ONE way!\n\n");
                                printf("1 means the way i-town <--> j-town\n");
                                Print(count);
                                string city1,city2;
                                printf("\nEnter START-town>");
                                cin>>city1;
                                printf("Enter END-town>");
                                cin>>city2;
                                way=CheckWay(city1,city2,count);
                                if(way==false) printf("ERROR!!\n");
                                break;
                        }
                        case 'c':
                        {
                                out++;

                                break;
                        }
                        default:continue;
		}
	}
        return 0;
}