Nieuws:

We zijn er weer.

Na lange tijd van afwezigheid zijn we er weer  :laugh:
We hebben alle wachtwoorden gereset, je oude wachtwoord werkt niet meer.Je moet via het "wachtwoord vergeten"-linkje je wachtwoord resetten. Je krijgt hiervoor een mailtje op het adres dat je bij ons geregistreerd hebt.

De komende tijd zijn we nog druk bezig om de rest van de site op te bouwen, dus het kan zijn dat sommige onderdelen (tijdelijk) niet werken.

Welkom, Gast. Alsjeblieft inloggen of registreren.
Heb je de activerings-mail niet ontvangen?

Auteur Topic: [C] Probleem met binary tree  (gelezen 1397 keer)

Offline Joshua822

  • Documentatieteam
  • Steunpunt: Nee
[C] Probleem met binary tree
« Gepost op: 2009/08/13, 16:43:17 »
Hallo.

Ik probeer een functie te schrijven om waarden in een binary tree toe te voegen in C. Nu, ik weet niet wat ik moet doen. Ik maak een root element aan, geef deze een stukje geheugen, en probeer met de functie instert_val_tree(waarde,plaats) die ik zelf heb geschreven de sleutelwaarde ( wat de variabel val is, in de eerste struct node. ) in te voegen. Daarna print ik die waarde uit. Maar hij eindig altijd op 0.

Hier is de code :

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

 struct node {

 int val;
 struct node *left;
 struct node *right;

};

 void insert_val_tree(int val2, struct node *blad)
 {
   if(blad == 0)
   {
     blad = (struct node*)malloc(sizeof(struct node));
     blad->val = val2;
   }
   if(val2 < blad->val)
     insert_val_tree(val2,blad->left);
   if(val2 > blad->val)
     insert_val_tree(val2,blad->right);
 }
 int main()
 {

   struct node *root;
   root = (struct node*)malloc(sizeof(struct node));
   insert_val_tree(5,root);
   printf("%d",root->val);
   return 0;
 }

Alvast bedankt voor de hulp.
 

Offline SeySayux

  • Lid
    • SeySayux.net
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #1 Gepost op: 2009/08/13, 17:17:44 »
#include <stdio.h>
#include <stdlib.h>

#define cnew(x) x##_create
#define cdelete(x,y) x##_destroy(y); y = 0

 struct node {

 int val;
 struct node *left;
 struct node *right;

};

struct node *node_create() {
      struct node *n = (struct node*)calloc(sizeof(struct node),1);
      return n;
}

void node_destroy(struct node *self) {
      if(self->right != NULL) cdelete(node,right);
      if(self->left != NULL) cdelete(node,left);
      free(self);
}

 void node_append(struct node *self, int val) {
   struct node* leafptr = self;
   while(leafptr != 0) {
       if(leafptr->val < val) leafptr = leafptr->left;
       else leafptr = leafptr->right;
   }
   leafptr = cnew(node)();
   leafptr->val = val;
 }

 int main()
 {

   struct node *root = cnew(node)();
   node_append(root,5);
   printf("%d",root->val);
   cdelete(node,root);
   return 0;
 }
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Offline Joshua822

  • Documentatieteam
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #2 Gepost op: 2009/08/13, 17:46:18 »
@SeySayux : Bedankt, maar dat begrijp ik nog niet echt.

Ik zou graag een oplossing voor het probleem in mijn functie zien, niet gewoon iets dat ik maar half begrijp klakkeloos overnemen.

Offline profoX

  • Lid
    • wesley
    • Lionslink
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #3 Gepost op: 2009/08/13, 19:08:42 »
Hoe wil je waarden toevoegen in de binary tree? Wat voor een binary tree is dit? Je voorbeeldimplementatie vertelt me niet veel. Ik kan er alleen uit opmaken dat je de waarde 5 'ergens' in je binary tree wil steken en die daarna weer wil opvragen...

Als je door je code loopt zul je zien dat root->left en root->right nooit geïnitialiseerd zijn. Met insert_val_tree ga je op een gegeven moment een nieuw blad creëren. Dit nieuwe blad is echter op geen enkele manier gelinkt aan de root node; node->right zal nog steeds NULL zijn. De waarde van root zelf wordt ook nooit aangepast.
Human Knowledge Belongs To The World -- Antitrust (2001)
Nederlandstalige Ubuntu documentatie van Ubuntu-NL (wiki)

Offline SeySayux

  • Lid
    • SeySayux.net
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #4 Gepost op: 2009/08/13, 19:45:03 »
Ik zal de code even becommentarieren:
#include <stdio.h>
#include <stdlib.h>

#define cnew(x) x##_create
#define cdelete(x,y) x##_destroy(y); y = 0
Dit zijn twee macro's die de werking van new en delete in C++ simuleren: cnew creëert een nieuwe variable van type x, cdelete verwijdert variable y van type x, en zet de pointer op 0.

struct node {

 int val;
 struct node *left;
 struct node *right;

};
Dit heb ik gewoon gekopieerd van jouw code

struct node *node_create() {
      struct node *n = (struct node*)calloc(sizeof(struct node),1);
      return n;
}
Dit is de constructor van node. Functies die op een object werken beginnen altijd met de naam van de klasse en een underscore in dit schema (Ik heb dit schema voor OOP in C zelf onworpen). De constructor wordt aangeroepen door cnew. De constructor moet een pointer naar de klasse retourneren, en neemt als enige geen T *self aan. Ik gebruik hier calloc om de variabelen onmiddelijk op 0 te zetten.

void node_destroy(struct node *self) {
      if(self->right != NULL) cdelete(node,right);
      if(self->left != NULL) cdelete(node,left);
      free(self);
}
Dit is de destructor, deze wordt door cdelete aangeroepen. Hier zie je dus een andere functie die op een object werkt (in andere talen met 'echte' klassen heet dit een memberfunctie). Deze neemt wél een pointer naar het object aan. Eerst worden de bladeren links en rechts verwijderd (tenzij ze 0 zijn), daarna wordt het object zelf verwijderd d.m.v. free

void node_append(struct node *self, int val) {
   struct node* leafptr = self;
   while(leafptr != 0) {
       if(leafptr->val < val) leafptr = leafptr->left;
       else leafptr = leafptr->right;
   }
   leafptr = cnew(node)();
   leafptr->val = val;
 }
Dit is hetzelfde als je insert_val_tree. Weer een functie die op een object werkt, met de prefix en de pointer naar self (je mag overigens elke naam voor self kiezen die je wilt: ik gebruik gewoon self uit stijl, en om niet 'this' te gebruiken, wat conflicteert met C++). We itereren zolang over de tree totdat we een leeg plaatsje gevonden hebben: afhankelijk of de waarde kleiner of groter is gaan we naar links of naar rechts. Dan alloceren we een nieuw object (geen schrik, de destructor geeft ze allemaal vrij!), en vullen de gegeven in.


int main()
 {

   struct node *root = cnew(node)();
   node_append(root,5);
   printf("%d",root->val);
   cdelete(node,root);
   return 0;
 }
Dit heb ik gewoon gekopiëerd. Enkel heb ik hier cnew en cdelete gebruikt in plaats van malloc (de constructor en destructor moeten zelf voor hun malloc/free zorgen).

Ik hoop dat je hier iets aan hebt en wat bij hebt geleerd over object geörienteerd programmeren in C. Je hoeft mijn stijl niet te volgen, je kan even goed je eigen stijl ontwikkelen :)
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Offline Joshua822

  • Documentatieteam
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #5 Gepost op: 2009/08/13, 21:16:27 »
Bedankt voor de uitleg, SeySayux ! Dit verklaart het inderdaad, en ik heb weer wat bijgeleerd.

Ik heb het probleem echter opgelost. Ik was namelijk het volgende vergeten, ik keek alleen of blad 0 is, terwijl ik ook moest kijken of blad->val 0 is, en daarna de waarde van val->blad wijzigen in val2.

Hier is de code :

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

 struct node {

 int val;
 struct node *left;
 struct node *right;

 };

 void insert_val_tree(int val2, struct node *blad)
 {
   if(blad == 0)
   {
     blad = (struct node*)malloc(sizeof(struct node));
     blad->val = val2;
     blad->left = 0;
     blad->right = 0;
   }
   if(blad->val == 0)
     blad->val = val2;
   if(val2 < blad->val)
     insert_val_tree(val2,blad->left);
   if(val2 > blad->val)
    i nsert_val_tree(val2,blad->right);
 }

 int main()
 {

   struct node *root;
   root = (struct node*)malloc(sizeof(struct node));
   root->left = 0;
   root->right = 0;
   insert_val_tree(5,root);
   printf("%d \n",root->val);
   return 0;
 }

Bedankt voor de hulp !
 

 

Offline profoX

  • Lid
    • wesley
    • Lionslink
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #6 Gepost op: 2009/08/13, 21:35:38 »
Ik weet niet wat je van plan bent, maar dit lijkt me toch niet echt correct ???
root->val is in het begin niet geïnitialiseerd, maar ervan uitgaande dat het op 0 geïnitialiseerd is,
zal de waarde van de root node veranderen in 5, maar de rest van de code in de insert_val_tree functie is dan vrij nutteloos.
Human Knowledge Belongs To The World -- Antitrust (2001)
Nederlandstalige Ubuntu documentatie van Ubuntu-NL (wiki)

Offline Joshua822

  • Documentatieteam
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #7 Gepost op: 2009/08/13, 22:24:01 »
Nee, de functie is geschreven om ook in andere vergelijkbare scripts ingezet te kunnen worden.


Offline SeySayux

  • Lid
    • SeySayux.net
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #8 Gepost op: 2009/08/14, 09:52:32 »
Gebruik toch maar een OO-schema met constructors en destructors. Kan geen kwaad :P
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Offline Joshua822

  • Documentatieteam
  • Steunpunt: Nee
Re: [C] Probleem met binary tree
« Reactie #9 Gepost op: 2009/08/14, 12:15:46 »
Akkoord. Die werken wat handiger. Maar dit was maar een experiment, om te weten hoe het ongeveer gaat, hé ;)