Ερώτηση πάνω σε Δυαδικό δέντρο αναζήτησης σε c++

[realez]

Καλησπέρα προσπαθώ να φτιάξω ένα δυαδικό δένδρο αναζήτησης σε c++ τα έχω κάνει σχεδόν αλλά έχω κολλήσει σε μια συγγεκριμένη συνάρτηση. Η συνάρτηση αυτή πρέπει να προσθέτει σε μία γραμμική λίστα όλα τα στοιχεία του δέντρου στο διάστημα [α, β] , να τυπώνει τη λίστα αυτή και στη συνέχεια να την καταστρέφει(το δένδρο παραμένει αμετάβλητο).  Άμα βρείτε κάποιο λαθάκι θα με βοηθήσετε πάρα πολύ να συνεχίσω.

 

 

void interval(TreeNode *t, int min, int max) // t ριζα δεντρου, min =α και max=β
{
    static int counter = 0;
    static ListNode *head = NULL;
    static ListNode *temp2 = NULL;
    if (t == NULL )
    {
        cout<<"o komvos einai kenos"<<endl;
        return;
    }
    interval ( t->left, min, max);
    counter= counter + 1;
    if(t->item >=min || t->item <=max)
    {
        ListNode *temp = new ListNode;
        temp->data = t->item;
        temp->next = head;
        head = temp;
    }
    interval ( t->right, min, max);
    if(head != NULL)
    {
        cout<<head->data<<endl;
        temp2 = head->next;
       do
       {
           cout<<temp2->data<<endl;
           temp2 = temp2->next;
           
       }while(temp2->next != NULL);
    }
    else cout<<"kenh lista"<<endl;    
}

Επεξ/σία 14 Ιανουαρίου 2013 από realez

[defacer]

Βοήθα μας λίγο να σε βοηθήσουμε όμως! 

• Την έτρεξες αυτή τη συνάρτηση σα μέρος ενός δοκιμαστικού προγράμματος; Αν όχι, προφανώς πρέπει να το κάνεις πριν ζητήσεις βοήθεια σε οτιδήποτε. Αν ναι, ήταν τα αποτελέσματα διαφορετικά από αυτά που περίμενες; Αν ήταν, ποιές ήταν οι διαφορές;
• Καλός ο κώδικας της συνάρτησης, αλλά πολύ καλύτερο θα ήταν να μας δώσεις ένα SSCCE. Μπορείς είτε απλά να κάνεις copy/paste το σχετικό κώδικα εδώ είτε (ακόμα καλύτερα!) σε κάποιο online εργαλείο όπως το ideone όπου θα μπορούμε να δούμε και τον κώδικα και το αποτέλεσμα χωρίς να χρειάζεται να στήσουμε μόνοι μας project.
• Όσο πιο εύκολο είναι για κάποιον να βοηθήσει τόσο περισσότεροι θα βρεθούν να το κάνουν.

[realez]

Το υπόλοιπο πρόγραμμα τρέχει κανονικά, σίγουρα θέλει λίγο σουλούπομα αλλά δεν έχει θέμα, εκτός απο 2 συναρτήσεις rotate που δεν τις έχω φτιάξει ακόμα αλλά δεν ενοχλούν. Δεν πρέπει να είναι δύσκολο απλά δεν το βλέπω αυτή τη στιγμή. Ανέβασα τον κώδικα εδώ  . Για το interval μου εμφανίζει segmentation fault(core dumped).

 

 

Επίσης αν κάποιος ξέρει που θα μπορούσα να βρω ένα καλό παράδειγμα να καταλάβω το rotation θα του ήμουν πολύ ευγνώμων.

Επεξ/σία 15 Ιανουαρίου 2013 από realez

[defacer]

Η υλοποίηση αυτή της interval έχει πολλά θέματα.

 

1. Κατά τη διάρκεια του traversal φτιάχνεις μια linked list με τους κόμβους που έχουν τιμή μέσα στο διάστημα, αλλά αυτή τη λίστα την εμφανίζεις σε κάθε κόμβο. Γιατί; Είτε φτιάχνεις τη λίστα και την εμφανίζεις μία φορά (μόλις τελειώσει ολόκληρο το traversal) είτε εμφανίζεις κάθε ένα κόμβο που κάνει match επιτόπου αλλά μόνο του.

 

2. Το || στη συνθήκη είναι λάθος και έπρεπε να είναι && (προφανές).

 

3. To segfault γίνεται επειδή δεν κάνεις κανέναν έλεγχο αν το temp2 είναι null αλλά πας αμέσως και κάνεις cout << temp2->data.

 

O κώδικας που έχεις δώσει στο ideone επίσης σηκώνει πάρα μα πάρα πολλή βελτίωση στο στυλ γραψίματος, τόση που αν δεις το "πώς θα έπρεπε" να είναι νομίζω δε θα το πιστεύεις ότι είναι "ο ίδιος κώδικας". Παρόλα αυτά επειδή δε θέλω να σε αποσπάσω από το ζουμί της υπόθεσης (το BST) δε θα αρχίσω τα κατεβατά. Απλά δίνω μια version της interval, απο κει και πέρα αν θέλεις μπορείς να πιάσεις την κάθε μία function ξεχωριστά και να τη δεις σαν εργασία "βελτιώστε αυτό τον κώδικα" (και σα σχέδιο και σαν κατασκευή):

 

 

 

void interval(TreeNode *t, int min, int max)
{
        if (t == NULL) {
                return;
        }


        interval(t->left, min, max);
        if (t->item >= min && t->item <= max) {
        cout << t->item << endl;
        }
        interval(t->right, min, max);
}

[realez]

Κατάλαβα τα λάθοι μου... Όντως ο κώδικας είναι πολύ κακογραμμένος τόσο που ακόμα και εγώ μπορώ να το καταλάβω

Σε ευχαριστώ πάρα πολύ για τη βοήθεια σου. Τώρα μένει μόνο το σουλούπωμα

[realez]

Τελικά εκεί που νόμιζα πως ήταν έυκολο δε μου λειτουργεί η συνάρτηση rotate.(rotateright για πχ έχω και rotate left). Έχω βάλει κάποιες σημειώσεις ρωτήστε με ότι θέλετε.

 

>TreeNode* rotateRight(TreeNode *root, int x)
{  //ψάχνει το ζητούμενο int χ και όταν το βρει αποθηκεύει στο curr  τη θέση του και στο  parent  τη θέση του γονιού του.
    bool found = false;
    if(root == NULL)
    {
        cout<<"to dentro einai keno"<<endl;
        return root;
    }
    TreeNode *curr;
    TreeNode *parent;
    parent = root;
    curr = root;
    while(curr!=NULL)
    {
        if(curr->item == x)
        {
            found = true;
            break;
        }
        else
        {
            parent = curr;
            if(x > curr->item)
            {
                curr = curr-> right;
            }
            else
            {
                curr = curr-> left;
            }
        }
    }
    if(!found)
    {
        cout<<"De vrethike to stoixeio pou zhthsate"<<endl;
        return root;
    }// μέχρι εδώ είναι ο κώδικας που ψάχνει το στοιχείο.
    if(curr->left != NULL) //εδώ ξεκινάει ο κώδικας της περιστροφής
    {
       TreeNode *tmp;  // δημιουργία ενός δείκτη σε TreeNode
       tmp = curr->left; //Βάζει τον tmp να δείχνει στο αριστερό παιδί του στοιχείου που ψάχναμε.
       curr->left = tmp->right; // Βάζει το στοιχείο που ψάχναμε να δείχνει στο δεξί παιδί του tmp
       tmp->right = curr; // Το δεξί παιδί του tmp είναι πλέον το στοιχείο που ψάχναμε.
       if(parent == root)//αμα εδώ βάλω μόνο root = tmp; και βγάλω τα υπόλοιπα if λειτουργεί αλλά
       {                         //μόνο αν το χ(curr) είναι η ρίζα
           root = tmp;
       }                              
       else if(parent->left == curr)
       {
           parent->left = tmp;
       }
       else
       {
           parent->right = tmp;
       }
    }
    else
    {
        cout<<"den einai efikth h deksia peristrofh"<<endl;
    }
    return root;
}