Binární strom – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Binární strom – C / C++ – Fórum – Programujte.comBinární strom – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Michaela
~ Anonymní uživatel
5 příspěvků
27. 3. 2011   #1
-
0
-

Ahoj, potřebovala bych poradit s kouskem kódu. Nevím, jak na to. Jedná se o část, kde se mají smazat uzly binárního stromu.. Je u toho napsáno //úkol... Ještě bych chtěla, kdyby mi někdo zkontroloval, zda jsem správně udělala smazání celého stromu. Moc děkuji.



//ADT binární strom
//Podle prednasek implementujte ADT binární strom, který bude bude poskytovat následující metody
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>


//pomocna struktura pro definici prvku ukladaneho do stromu
typedef struct tDatatag
{
int Key;
}tData;


typedef struct tUzelStromutag
{
tData data; //ukladana data
struct tUzelStromutag* ukLevy; //ukazatel na leveho nasledovnika
struct tUzelStromutag* ukPravy; //ukazatel na praveho nasledovnika
}tUzelStromu;

typedef tUzelStromu* tUkUzel; //tUzelStromu* tUkUzel;

//pomocna funkce pro vypis dat
void writedata(tData* d)
{
printf("(%d)", d->Key);
}

//vlo?í do stromu nový uzel s daty d. Pokud uz ve stromu existuje strom se stejnými daty, neudilá nic
void BSTInsert(tUkUzel* RootPtr, tData* d)
{
if( (*RootPtr) != NULL )
{
if( d->Key < (*RootPtr)->data.Key )
BSTInsert(&(*RootPtr)->ukLevy, d);
else if( d->Key > (*RootPtr)->data.Key )
BSTInsert(&(*RootPtr)->ukPravy, d);
else
(*RootPtr)->data.Key = d->Key;
}
else
{
(*RootPtr) = (tUkUzel)malloc(sizeof(tUzelStromu)); //vytvooení nového uzlu
(*RootPtr)->ukLevy = NULL; //a jeho naplniní správnými hodnotami}
(*RootPtr)->ukPravy = NULL;
(*RootPtr)->data.Key = d->Key;
}
}

//vyhledá uzel, jeho? data jsou shodná jako parametr d
tUkUzel BSTSearch(tUkUzel RootPtr, tData* d)
{
if( RootPtr != NULL )
{
if( d->Key < RootPtr->data.Key )
return BSTSearch(RootPtr->ukLevy, d);
else if( d->Key > RootPtr->data.Key )
return BSTSearch(RootPtr->ukPravy, d);
else
return RootPtr;
}
else
return NULL;
}

//projde strom pruchodem preorder a vytiskne v?echny jeho uzly
void BSTPreorder(tUkUzel uzel)
{
if( uzel != NULL )
{
writedata(&uzel->data);
BSTPreorder( uzel->ukLevy );
BSTPreorder( uzel->ukPravy );
}
}

//projde strom pruchodem inorder a vytiskne v?echny jeho uzly
void BSTInorder(tUkUzel uzel)
{
if( uzel != NULL )
{
BSTInorder( uzel->ukLevy );
writedata(&uzel->data);
BSTInorder( uzel->ukPravy );
}
}

//projde strom pruchodem postorder a vytiskne v?echny jeho uzly
void BSTPostorder(tUkUzel uzel)
{
if( uzel != NULL )
{
BSTPostorder( uzel->ukLevy );
BSTPostorder( uzel->ukPravy );
writedata(&uzel->data);
}
}

//korektni ze stromu sma?e uzel, jeho? data jsou stejné jako parametr d
void BSTDelete(tUkUzel RootPtr, tData* d)
{
//ukol
}

//sma?e celý strom
void BSTDeleteTree(tUkUzel RootPtr)
{
if (RootPtr != NULL)
{
BSTDeleteTree(RootPtr->ukLevy);
BSTDeleteTree(RootPtr->ukPravy);
RootPtr = NULL;
}
}

int main()
{
tUkUzel strom = NULL;
tData data;
int i;

srand( (unsigned)time( NULL ) );

printf("\nVkladam nahodne cislo: ");
for(i=0; i<5; i++)
{
data.Key = rand()%50;
BSTInsert(&strom, &data);
printf("%d ", data.Key);
}
data.Key = 25;
BSTInsert(&strom, &data);
printf("%d ", data.Key);
for(i=0; i<5; i++)
{
data.Key = rand()%50;
BSTInsert(&strom, &data);
printf("%d ", data.Key);
}

printf("\nVypis stromu metodou inorder:\n");
BSTInorder(strom);

printf("\nVypis stromu metodou preorder:\n");
BSTPreorder(strom);

printf("\nVypis stromu metodou postorder:\n");
BSTPostorder(strom);

data.Key = 25;
BSTDelete(strom, &data);
printf("\nVypis stromu metodou inorder po smazani prvku %d:\n", data.Key);
BSTInorder(strom);

BSTDeleteTree(strom);
printf("\nVypis stromu metodou inorder po smazani vsech prvku:\n");
BSTInorder(strom);

printf("\nLibovolnou klavesou ukoncete program.");
getch();
return 0;
}

Nahlásit jako SPAM
IP: 85.132.142.–
Reklama
Reklama
KIIV+42
God of flame
27. 3. 2011   #2
-
0
-

pokud dobre vidim tak mazani je spatne.. bude ti delat unik pameti (memory leak) - neuvolnujes totiz data, na ktere ukzatel odkazuje.. jen se zbavis toho odkazu, kde pamet je...

na todle se nejvic hodi valgrind - hned vis kolik zustalo neuvolneno na konci behu

Nahlásit jako SPAM
IP: 94.142.234.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Michaela
~ Anonymní uživatel
5 příspěvků
28. 3. 2011   #3
-
0
-

takže tam mám dát free(RootPtr); ?

Nahlásit jako SPAM
IP: 195.113.98.–
KIIV+42
God of flame
28. 3. 2011   #4
-
0
-

jak na to koukam, mohl by byt jeste problem ze nebudes vracet zpet ten NULL nadrazeny instanci..
takze bud zneuzit ** nebo to NULLovat az v nadrazeny instanci...

      if (RootPtr != NULL)

{
BSTDeleteTree(RootPtr->ukLevy);
free(RootPtr->ukLevy);
RootPtr->ukLevy = NULL;
BSTDeleteTree(RootPtr->ukPravy);
free(RootPtr->ukPravy);
RootPtr->ukPravy = NULL;
}


problem je akorat s tim root prvkem.. ... takze spis void BSTDeleteTree(tUkUzel * RootPtr)
a uvnitr (*RootPtr)->...

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
igorS0
Duch
7. 9. 2015   #5
-
0
-

#4 KIIV

Můj příspěvek přichází už poněkud pozdě, myslím ale, že bude mít pro někoho význam. tak tedy: Výše uvedené řešení také způsobí únik paměti. Nedojde k odalokování posledních členů stromu. (listů)

Příklad stromu:

                           10
                         /      \
                        6      14
                       /  \      /  \
                      5  8  11 18

bude se dít následující rekurzivní volání 

DeleteUzel(RootPtr_10)
  DeleteUzel(RootPtr_10->ukLevy, což je RootPtr_6)
    DeleteUzel(RootPtr_6->ukLevy, což je RootPtr_5)  
      DeleteUzel(RootPtr_5->ukLevy, což je nullptr)    // podmínka RootPtr != nullptr nesplněna 
      free(RootPtr_5->ukLevy, což je nullptr)  ;       // uvolňuje se kukazatel na nullptr
          RootPtr_5->ukLevy = nullptr; 
    DeleteUzel(RootPtr_6->ukPravy, což je RootPtr_8)  
      DeleteUzel(RootPtr_8->ukPravy, což je nullptr)   // podmínka RootPtr != nullptr nesplněna 
      free(RootPtr_8->ukPravy, což je nullptr)  ;      // uvolňuje se kukazatel na nullptr
          RootPtr_8->ukPravy = nullptr; 
  free(RootPtr_10->ukLevy, což je RootPtr_6)  ;        // ukazatel na 5 a 8 zůstává neuvolněn
  RootPtr_10->ukLevy = nullptr;                        // uvolněním 6tky zaniká přístup k jeho větvím
  
  DeleteUzel(RootPtr_10->ukLevy, což je RootPtr_6)
  ...

Lepší řešení je: 

void DeleteUzel(tUkUzel RootPtr)
{
  if( Ptr != nullptr )
  {
        DeleteUzel(RootPtr->ukLevy);
        DeleteUzel(RootPtr->ukPravy);
        free(RootPtr);
        RootPtr = nullptr;
  }
}

Volání bude probíhat takto:

DeleteUzel(RootPtr_10)
  DeleteUzel(RootPtr_10->ukLevy), což je RootPtr_6)
    DeleteUzel(RootPtr_6->ukLevy), což je RootPtr_5)
      DeleteUzel(RootPtr_5->ukLevy), což je nullptr)   // 5ka nemá levou větev. Ukazatel je nullptr pokračuje se na pravou
      DeleteUzel(RootPtr_5->ukPravy), což je nullptr)  // prava větev je rovnež nullptr
      free(RootPtr_5);                                 // uvolnění paměti
		  RootPtr_5 = nullptr;
    DeleteUzel(RootPtr_6->ukPravy), což je RootPtr_8)  // pokracuje se na pravou větev 6tky
      DeleteUzel(RootPtr_8->ukLevy), což je nullptr)
      DeleteUzel(RootPtr_8->ukPravy), což je nullptr)
      free(RootPtr_8);
		  RootPtr_8 = nullptr;
    free(RootPtr_6);                                   // 6tka už nemá pravou ani levou větev a proto je možné ji odalokovat
		RootPtr_6 = nullptr; 

 DeleteUzel(RootPtr_10->ukPravy), což je RootPtr_14)
    DeleteUzel(RootPtr_14->ukLevy), což je RootPtr_11)
      DeleteUzel(RootPtr_11->ukLevy), což je nullptr)  // 11ka nemá levou větev. Ukazatel je nullptr pokračuje, se na pravou
      DeleteUzel(RootPtr_11->ukPravy), což je nullptr) // prava větev je rovnez nulptr
      free(RootPtr_11);                                // uvolnění paměti
		  RootPtr_11 = nullptr;
    DeleteUzel(RootPtr_14->ukPravy), což je RootPtr_11)// pokracuje se na pravou větev 14tky
      DeleteUzel(RootPtr_11->ukLevy), což je nullptr)
      DeleteUzel(RootPtr_11->ukPravy), což je nullptr)
      free(RootPtr_11);
		  RootPtr_11 = nullptr;
    free(RootPtr_14);                                  // 14tka už nemá pravou ani levou větev a proto je možné ji odalokovat
		RootPtr_14 = nullptr; 
  free(RootPtr_10);                                    // Nakonec se odalokuje kořen
	RootPtr_10 = nullptr;

KIIV mně inspiroval k hledání leak detektoru pro Windows Visual Studio

Můžu doporučit https://vld.codeplex.com/ funguje perfektně a je zdarma.

Igor


Nahlásit jako SPAM
IP: 94.113.240.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 228 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý