Mam napisać taki oto program:
- W oparciu o wygenerowaną pseudolosowo tablicę unikalnych liczb całkowitych zadanego rozmiaru zbudować drzewo BST. W kolejności zgodnej z kolejnością liczb w tablicy:
a) zaimplementować operację obrotów poddrzewa w lewo i prawo
b) napisać funkcję wypisujące zawartość drzewa w kolejności inOrder, preOrder, postOrder - Analogicznie do pkt.1 zbudować drzewo AVL w oparciu o tablicę
#include <iostream>
#include <time.h>
#include <cstdlib>
struct drzewo
{
int key;
drzewo *lewy;
drzewo *prawy;
};
drzewo *x=NULL;
void Insert(drzewo *&x, int key)
{
if(x==NULL)
{
x=new drzewo;
x->key=key;
x->lewy=NULL;
x->prawy=NULL;
}
else{
if(key>=x->key) Insert(x->prawy, key);
if(key<x->key) Insert(x->lewy, key);
}
}
void inorder(drzewo *x){
if(x!=NULL){
inorder(x->lewy);
std::cout<<x->key<<" ";
inorder(x->prawy);
}
}
void preorder(drzewo *x){
if(x!=NULL){
std::cout<<x->key<<" ";
preorder(x->lewy);
preorder(x->prawy);
}
}
void postorder(drzewo *x){
if (x!=NULL){
postorder(x->lewy);
postorder(x->prawy);
std::cout<<x->key<<" ";
}
}
void obrot(struct drzewo *top) //obroty poddrzewa
{
if (top != NULL)
{
drzewo* tmp = top->lewy;
top->lewy = top->prawy;
top->prawy = top->lewy;
}
}
using namespace std;
int main()
{
cout<<"Jak duza ma byc tablica"<<endl;
int u;
cin>>u;
int *tab=new int[u];
srand(time(NULL));
for (int i = 0; i < u; ++i)
{
tab[i] = rand() % 100;
cout<<tab[i]<<endl;
}
drzewo *x=NULL;
for(int i=0; i<u; i++)
{
Insert(x, tab[i]);
}
inorder(x);
cout<<endl;
preorder(x);
cout<<endl;
postorder(x);
return 0;
}
Tyle udało mi się napisać do drzewa bst. Program ten tworzy drzewo z tablicy losowej. Podpunkt b, czyli funkcję inorder,preorder i pastorder działają dobrze. Głównie chodzi mi o podpunkt a) w moim kodzie jest to "void obrot" ale nie jestem pewien czy działa ona prawidłowo. Czym będziesz się różniło drzewo AVL analogicznie zbudowane co to?