Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [turbo C++] бинарное дерево

Автор: Jolia 24.9.2009, 20:13

Здравствуйте..судьба-таки свела с бинарными деревьями( помогите пожалуйста..

В общем задача сосотоит в том, чтобы создать сбалансированное бинарное дерево. Для начала создается массив, который затем сортируется. В качестве корня дерева берется середина массива. Потом сыновьями корня идут элементы через один, начиная с середины. их сыновями в свою очередь будут эл-ты через один, начиная с предыдущего или последующего от середины..и т.д.
ну к примеру, имеется:

1 2 3 4 5 6 7
тогда полученное дерево:

               4
         2          6
     1     3    5    7

Код


#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

struct el
{int value;
el *left;
el *right;
};

void sozd( el *tr, int n)
{

if(!tr)
  {
       el *p=new el;
       p->value=n;
       tr=p;

  }
else
  {
    if ((tr->value)>n)
       {sozd(tr->left,n);

       }
    else

       {sozd(tr->right,n);

       }
  }


}

void print(el t)
{
 if(!t)
  {
   if(!t->left)
   {
    cout<<t->value<<" -left";
    cout<<t->left->value;

   }

     if(!t->right)
   {
    cout<<t->value<<" -right";
    cout<<t->right->value;

   }
  }
  print(t->left);
  print(t->right);

}


void main()
{randomize();
clrscr();


int k=10,n=0,i=0,j=0,q=0;
int *mas;
cout<<"Vvedite kol-vo elementov dereva: ";
cin>>n;
 for(i=0;i<n;i++)
   mas[i]=random(20);

 for(i=0;i<n;i++)

   for (j=i;j<n;j++)

     if(mas[i]>mas[j])
     {
      q=mas[j];
      mas[j]=mas[i];
      mas[i]=q;

     }

 i=n/2;
 el *el1=new el;
el1->value=mas[i];
 while((i-2)>=0)
 {
   sozd(el1,mas[i-2]);
   i=i-2;

 }
 i=n/2-1;

  while(i>=0)
 {
   sozd(el1,mas[i]);
   i=i-2;

 }

  i=n/2;

  while(i>=0)
 {
   sozd(el1,mas[i+2]);
   i=i+2;

 }

  i=n/2+1;

  while(i>=0)
 {
   sozd(el1,mas[i]);
   i=i+2;

 }
print(el1);
getchar();
}

Это я тщетно пыталась что то соорудить..но ничего не вышло(
Оч надеюсь на Вашу помощь.

Автор: ИванМ 25.9.2009, 00:01

Попробуй так:

header (tree.h):

Код


#ifndef _tree_
#define _tree_

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>

template<class T>
class tree
{
    T value;
    tree<T> *left, *right;
    
    template<class Iter>
    static tree<T>* create(Iter begin, Iter end, Iter min, Iter max)
    {
        int count=std::distance(begin, end);

        if(count<0)
            return NULL;

        int n=count/2;

        Iter mid=begin;                
        advance(mid, n);    
        
        tree<T> *t=new tree<T>(*mid);

        if(mid!=min)
        {
            Iter nm=mid-1;
            t->left=create(begin, nm, min, max);
        }
        if(mid!=max-1)
        {
            Iter np=mid+1;
            t->right=create(np, end, min, max);
        }
        return t;
    }
public:
    tree(T val): value(val), left(NULL), right(NULL) {}    

    template<class Iter>
    static tree<T>* create(Iter begin, Iter end)
    {
        return create(begin, end, begin, end);
    }

    void out(std::ostream &stream, std::string str) const
    {
        if (left)
        {
            left->out(stream, str + "  ");
        }
        stream << str << value << std::endl;
        if (right)
        {
            right->out(stream, str + "  ");
        }
    } 
};

std::ostream& operator << (std::ostream& stream, const tree<int>& t)
{
    t.out(stream, "");
    return stream;
}

#endif

cpp:

Код


#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include "tree.h"

int main()
{
    std::vector<int> arr;
    copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(arr));
    std::sort(arr.begin(), arr.end());
    tree<int> *t=tree<int>::create(arr.begin(), arr.end());
    std::cout<<*t;
    system("pause");
}

Чтобы остановить ввод данных, нажимай Ctrl+Z

Автор: Jolia 25.9.2009, 22:12

это по ходу вижуал.. у меня турбо) и даже студии нет чтоб посмотреть как что работает.

мне бы конечно лучше тот код исправить smile

я тут щас сама полвечера сидела так ничего и не высидела Ж( пожааалуйста..

Автор: ИванМ 26.9.2009, 15:53

Для Turbo C++:

Код


#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void sort(int arr[], int len)
{
    for(int i = 1; i < len; ++i)
        for(int j = 0; j < len - i; ++j)
            if (arr[j] > arr[j+1])
            {
                int n=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=n;
            }
}

class tree
{
    int value;
    tree *left, *right;
    static tree* create(int *begin, int *end, int *min, int *max)
    {
        int count=end-begin;
        if(count<0)
            return 0;
        int n=count/2;
        int *mid=begin+n;
        tree *t=new tree(*mid);
        if(mid!=min)
        {
            t->left=create(begin, mid-1, min, max);
        }
        if(mid!=max)
        {
            t->right=create(mid+1, end, min, max);
        }
        return t;
    }
    void out(char* str)
    {
        if (left)
        {
            char *s=new char[strlen(str)+3];
            strcpy(s, str);
            strcat(s, "  ");
            left->out(s);
            delete []s;
        }
        cout << str << value << endl;
        if (right)
        {
            char *s=new char[strlen(str)+3];
            strcpy(s, str);
            strcat(s, "  ");
            right->out(s);
            delete []s;
        }
    }
public:
    tree(int val)
    {
        value=val;
        left=0;
        right=0;
    }
    static tree* create(int* begin, int* end)
    {
        return create(begin, end, begin, end);
    }
    void out()
    {
        out("");
    }

};

int *array;
tree* tr;

int main()
{
    clrscr();
    int len;
    cout<<"Enter the number of elements: ";
    cin>>len;
    array=new int[len];
    for(int i=0;i<len;i++)
    {
        cout<<"Enter the value of element #"<<i+1<<": ";
        cin>>array[i];
    }
    sort(array, len);
    tr=tree::create(array, array+len-1);
    tr->out();
    getch();
    delete[] array;
}