Binary tree κωδικας σε C.

[Star_Light]

Κοιταζω εναν κωδικα για την δημιουργια δυαδικου δέντρου στην C.

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

struct tree_el {
int val;
struct tree_el * right, * left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item) {
if(!(*tree)) {
*tree = item;
return;
}
if(item->val<(*tree)->val)
insert(&(*tree)->left, item);
else if(item->val>(*tree)->val)
insert(&(*tree)->right, item);
}

void printout(node * tree) {
if(tree->left) printout(tree->left);
printf("%d\n",tree->val);
if(tree->right) printout(tree->right);
}

void main() {
node * curr, * root;
int i;

root = NULL;

for(i=1;i<=5;i++) {
curr = (node *)malloc(sizeof(node));
curr->left = curr->right = NULL;
curr->val = rand();
insert(&root, curr);
}

printout(root);
}
 

Έχω κανει tracing τον κωδικα στο χαρτι αλλα δεν μπορω να τον καταλαβω απο ενα σημειο και μετά. Το προβλημα ειναι λιγο στους δείκτες απο οτι αντιλαμβάνομαι. Τα νούμερα με τα οποια έχω κανει test στο χαρτι ειναι 1 , 2 , -2 , 4 , 3 αρχικα λοιπον ο root ειναι το 1 ο νεος κομβος που θα δημιουργηθει μεσα στο for δειχνεται απο τον curr ο οποιος περνάει σαν ορισμα στην συναρτηση μεσω του item. Επειδη ομως ο root αρχικα ( *tree == root ) ειναι NULL τοτε θα δειχνει οπου και ο item δηλαδη ο νεος κομβος που έχει τιμή 1 και δυο δεικτες right και left στο NULL. Ως εδω η απορια μου ειναι η εξης γινεται κληση συνάρτησης με &NULL? 

 

Συνεχιζω στην συνεχεια για 2 <= 5 εχουμε νεο κομβο στον οποιο δειχνει ο curr και μετα την κληση της insert ο right αυτου του κομβου δειχνει οπου και ο curr δηλαδη σε κομβο με τιμη 2.Μετα για 3<=5 αφου if( -2 < 1 ) μεσα στην συνάρτηση τοτε καλειται η insert με ορισματα εναν δεικτη προς τον αριστερο δεικτη του κομβου που δημιουργησαμε στην main μεσω της malloc και το αλλο ορισμα με εναν δεικτη προς τον καινουργιο αυτον κομβο.Τελικα επειδη left == NULL o left δειχνει στον κομβο που δημιουργηθηκε στην main και ειναι με τιμη -2. Ομοια για 4 <= 5 ο right του καινουργιου κομβου δειχνει σε αυτον δηλαδη εχει val 4 και τελος ο right του επομενου νεου κομβου εχει τιμη 3. 

 

Το προβλημα μου βρισκεται στην printout(root) μετα την οποια δεν μπορω να αναλυσω. Αρχικα καλειται με την διευθυνση του κομβου root της ριζας δηλαδη που ειναι το 1. Επειδη ομως αυτος ο κομβος ειχε right και left δεικτες στο NULL τοτε απλα εκτυπωνεται η τιμη του που ειναι το 1 απο εκει και περα στο επομενο if 

 
void printout(node * tree) {
if(tree->left) printout(tree->left);
printf("%d\n",tree->val);
if(tree->right) printout(tree->right);  // <---- ΕΔΩ
}
 

Πως ακριβως συνεχιζει? Ποιον right κανει προσπέλαση η tree->right? κανονικα δεν κανει τον right του root? Και αυτος ο right που εχει κατσει κατω απο τον root συμφωνα με την θεωρια των δεντρων εδω πως ακριβως συνδέεται με τον δεικτη στην ριζα του δεντρου? Στις λιστες η συνδεση γινοταν εφοσον ο *next έδειχνε στον επομενο αυτον που δημιουργειται αμεσως μετα εδω ομως δυσκολευομαι να δω την συνδεση τους. 

[ZAKKWYLDE]

Γιατί διπλός pointer στο insert(node ** tree); το root node μπορεί άνετα να θεωρηθεί ότι είναι pointer σε "tree", όπως ακριβώς το όνομα ενός array είναι pointer σε array ουσιαστικά αν και δείχνει μόνο το πρώτο element. Έχω την εντύπωση ότι απο εκεί ξεκινάνε τα προβλήματά σου, Έχω επίσης την εντύπωση ότι εκεί χρειάζεσαι printout(*root)...αλλά μπορεί να λέω και βλακείες .

Κάτι που σίγουρα είναι πρόβλημα ότι στο recursion σου δεν έχεις base case.

[παπι]

&NULL τι ειν τουτο;

[Star_Light]

Γιατί διπλός pointer στο insert(node ** tree); το root node μπορεί άνετα να θεωρηθεί ότι είναι pointer σε "tree", όπως ακριβώς το όνομα ενός array είναι pointer σε array ουσιαστικά αν και δείχνει μόνο το πρώτο element. Έχω την εντύπωση ότι απο εκεί ξεκινάνε τα προβλήματά σου, Έχω επίσης την εντύπωση ότι εκεί χρειάζεσαι printout(*root)...αλλά μπορεί να λέω και βλακείες .

Κάτι που σίγουρα είναι πρόβλημα ότι στο recursion σου δεν έχεις base case.

 

 

http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/tree.html

 

 

&NULL τι ειν τουτο;

 

Αρχικα ο root ειναι NULL οποτε στην πρωτη κληση της insert ειναι insert(&root , curr); 

 

τελοςπαντων έχω ένα λαθος σε αυτα που έγραψα πριν λογω απροσεξίας στην αρχη ο δεξιος δεικτης του root δειχνει στον κομβο με τιμη 2 ενω ο αριστερος σε αυτον με τιμη -2. Μια αλλη ερωτηση που προκυπτει τωρα ειναι οτι αν στη περιπτωση του 4 που ειναι το προτελευταιο δειξει ο δεξιος του root εκει δεν χανεται η επαφη με τα υπολοιπα? με τον κομβο που εχει τιμη 2 πχ? θα το ξανακοιταξω αν και η printout με μπερδευει λιγο.

 

Δεν ειναι ασκηση για σχολη εχω ξεμπερδεψει με αυτα απλα μ αρεσει η C και ηθελα να δω μια δομη δεδομενων οπως τα δεντρα πως υλοποιούνται εδω. 

[ZAKKWYLDE]

Αυτά τα έχεις υπόψη σου;

http://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Programming_Concepts/Tree_traversal_algorithms_for_a_binary_tree

[imitheos]

Γιατί διπλός pointer στο insert(node ** tree); το root node μπορεί άνετα να θεωρηθεί ότι είναι pointer σε "tree", όπως ακριβώς το όνομα ενός array είναι pointer σε array ουσιαστικά αν και δείχνει μόνο το πρώτο element. Έχω την εντύπωση ότι απο εκεί ξεκινάνε τα προβλήματά σου, Έχω επίσης την εντύπωση ότι εκεί χρειάζεσαι printout(*root)...αλλά μπορεί να λέω και βλακείες .

Κάτι που σίγουρα είναι πρόβλημα ότι στο recursion σου δεν έχεις base case.

Η printout δέχεται όρισμα δείκτη σε struct tree_el οπότε το ίδιο με το root όχι με το *root. Η insert μπορεί κάλλιστα να υλοποιηθεί με μονό δείκτη όπως λες. Το πρόβλημα είναι ότι λόγω "by value" δεν θα μπορείς να πειράξεις τους δείκτες με void συνάρτηση και θα πρέπει να επιστρέφεις τον δείκτη ως return value. Ο διπλός δείκτης σου δίνει αυτή την ευκολία.

 

struct tree_el {
    int val;
    struct tree_el * right, * left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item) {
    if(!(*tree)) {
        *tree = item;
        return;
    }
    if(item->val<(*tree)->val)
        insert(&(*tree)->left, item);
    else if(item->val>(*tree)->val)
        insert(&(*tree)->right, item);
}

Η insert ξεκινά από το node που δίνουμε (την αρχή) και αν το *tree είναι NULL σημαίνει ο παρών κόμβος είναι κενός (ή όλο το δέντρο αν είμαστε στην αρχή) οπότε απλά του θέτει την τιμή item (λόγω του διπλού δείκτη μπορούμε να το κάνουμε αυτό). Αν το συγκεκριμένο node δεν είναι κενό τότε ελέγχει την τιμή που θέλουμε να εισάγουμε και αν είναι μικρότερη από τον κόμβο, τότε ξανά-τρέχει recursively με το αριστερό κλαδί και θα συνεχίσει μέχρι να βρει κενό κόμβο ώστε να θέσει την τιμή. Είθισται η insert να παίρνει ως όρισμα την τιμή και να κάνει αυτή allocate τον κόμβο και όχι να γίνεται στην main όπως εδώ αλλά οκ.

 

void printout(node * tree) {
    if(tree->left) printout(tree->left);
    printf("%d\n",tree->val);
    if(tree->right) printout(tree->right);
}

Η printout θα έπρεπε πιο σωστά να λέγεται printout_inorder γιατί έτσι διατρέχει το δέντρο και με τη παρούσα δομή του δέντρου θα μας κάνει ταξινόμηση.

 

int main(void) {
    node * curr, * root;
    int i;
    static const int tt[] = { 2, 7, 3, 5, 1 };

    root = NULL;

    for(i=0;i<5;i++) {
        curr = malloc(sizeof(node));
        curr->left = curr->right = NULL;
        curr->val = tt[i];
        insert(&root, curr);
    }

    printout(root);

    return 0;
}

Εισάγονται στο δέντρο οι τιμές 2,7,3,5,1 οι οποίες λόγω της δομής που χρησιμοποιούμε θα εισαχθούν ως (αν δεν το πηδήξει το code tag)

 2
/ \
1 7
 / \
 3
/ \
   5

Η παρούσα printout επισκέπτεται πρώτα όλα τα αριστερά κλαδιά και μετά γυρνάει πίσω εμφανίζοντας τους αριθμούς και έπειτα επισκέπτεται τα δεξιά κλαδιά οπότε στο παραπάνω δέντρο θα πάει 2->1 και εφόσον δεν έχει άλλο αριστερά θα εμφανίσει 1 και μετά 2. Έπειτα πάει αναγκαστικά δεξιά στο 7 και πάει πάλι όσο πιο αριστερά μπορεί οπότε φτάνει στο 3 το τυπώνει πάει δεξιά στο 5 το τυπώνει και μετά γυρνώντας πίσω τυπώνει το 7 οπότε παίρνουμε 1, 2, 3, 5, 7.

 

Έχω κανει tracing τον κωδικα στο χαρτι αλλα δεν μπορω να τον καταλαβω απο ενα σημειο και μετά. Το προβλημα ειναι λιγο στους δείκτες απο οτι αντιλαμβάνομαι. Τα νούμερα με τα οποια έχω κανει test στο χαρτι ειναι 1 , 2 , -2 , 4 , 3 αρχικα λοιπον ο root ειναι το 1 ο νεος κομβος που θα δημιουργηθει μεσα στο for δειχνεται απο τον curr ο οποιος περνάει σαν ορισμα στην συναρτηση μεσω του item. Επειδη ομως ο root αρχικα ( *tree == root ) ειναι NULL τοτε θα δειχνει οπου και ο item δηλαδη ο νεος κομβος που έχει τιμή 1 και δυο δεικτες right και left στο NULL. Ως εδω η απορια μου ειναι η εξης γινεται κληση συνάρτησης με &NULL?

Ένας δείκτης είναι μια απλή μεταβλητή όπως οι άλλες και έχει μια διεύθυνση και μια τιμή όπως όλες οι άλλες. Απλά τυγχάνει η τιμή του να είναι μια διεύθυνση μνήμης αντί για 3 ή 2.7 ή 'c'. Όταν δηλώνουμε node *root δεσμεύεται μνήμη για ένα δείκτη έστω η διεύθυνση 150. Αυτή η διεύθυνση έχει το συμβολικό όνομα root. Μετά λες root = NULL δηλαδή θέτεις τιμή στον δείκτη το NULL δηλαδή γράφεις την τιμή 0 στη διεύθυνση 150 (χάριν ευκολίας ας θεωρήσουμε ότι NULL είναι συνώνυμο του 0). Όταν καλείς την συνάρτηση με &root της περνάς ως όρισμα το νούμερο 150 που είναι η διεύθυνση της μεταβλητής όπως γίνεται πάντα με το &. Το ότι η μεταβλητή έχει τιμή NULL δεν παίζει κανένα ρόλο.