Διασχιση δυαδικου δεντρου

[miss_kathy]

Καλησπερα σε ολους!Ηθελα να κανω μια ερωτηση σχετικα με αλγοριθμους και

συγκεκριμενα σχετικα με τη διασχιση δυαδικων δεντρων. Ξερει κανεις με ποιο τροπο θα μπορουσα εχοντας τα κλειδια του δεντρου σε προδιαταξη να το σχεδιασω?Δεν ξερω βεβαια αν ρωταω στο σωστο μερος γιατι προκειται για αλγοριθμους..Αν μπορει καποιος να βοηθησει θα του ειμαι υποχρεη.Ευχαριστω!

[Blondeamon]

Θα τρέξεις την pre-order στο δέντρο που έχεις και θα προσθέτεις κλαδί κλαδί τους κόμβους σου.

 

Δεν εξηγείς πολλά, για δώσε περισσότερες λεπτομέρειες.

[miss_kathy]

Για παραδειγμα εχω την ακολουθια κλειδιων 85, 43, 93, 35,1, 3,91, 35,12,42, 34,32,85,77,80,70,28,79,9 και θελω να σχεδιασω το δεντρο σε προδιαταξη. Πως θα το κανω?

[Blondeamon]

Nα κατσεις να διαβάσεις

 

Ειναι απο τα πιο βασικα και ευκολα της θεωριας Διακριτων μαθηματικων.

[miss_kathy]

Ξερω πως να κανω προδιαταξη σε ενα δεντρο, δεν ειναι τιποτα αλλα αυτο που δεν ξερω ειναι πως οταν εχω την προδιαταξη να σχεδιαζω το δεντρο,δεν ειμαι δλδ σιγουρη οτι το κανω σωστα.Εχω διαβασει ολο το βιβλιο των δομων και δε λεει τιποτα και στο νετ δεν εχει κατι διαφωτιστικο. Αν μπορεις να βοηθησεις εχει καλως. Ευχαριστω.

[Technology fan]

με την ακριβώς αντίστροφη διαδικασία λογικά

[miss_kathy]

Τι εννοεις?Δηλαδη εσυ πως θα το σχεδιαζες?

[ΠάρηςΓ]

Πρέπει να υπάρχει καποιος κανονας για το δέντρο αλλιως δε ξερω πως μπορεί να βγει.

Δηλαδή μπορεί να ειναι δυαδικό,αναζητησης κατι τετοιο.

[narcotic]

Να έχεις στο μυαλό σου τα εξής.

 

Προδιατεταγμενη (preorder) -> ΚΑΔ

Ενδοδιατεταγμενη (inorder) -> ΑΚΔ

Μεταδιατεταγμενη (postorder) -> ΑΔΚ

 

οπου

 

K: επίσκεψη κόμβου (ρίζας)

A: διαδρομή αριστερού υποδεντρου

Δ: διαδρομή δεξιού υποδεντρου

 

Mε αυτο το τροπο κανεις σαρωση των δεντρων.

 

πχ

 

>         M
      /   \
    E       T
  /   \    / 
 A     Z  R
           \                            
            S

 

ΑΚΔ σαρωση (inorder)

 

ΑΕΖ Μ RST

(Α) (Κ) (Δ)

 

ΑΔΚ σαρωση (postorder)

 

AZE SRT M

(Α) (Δ) (Κ)

 

ΚΑΔ σαρωση (preorder)

 

M EAZ TRS

(K) (A) (Δ)

 

Για το ανάποδο (αν έχεις δηλαδή τα κλειδιά) κανεις ακριβώς το αντίθετο η λογική παραμένει η ίδια.

[parsifal]

Εδώ: http://ar.answers.yahoo.com/question/index?qid=20080210084032AAKQzdp

 

ένας τυπάς αναπτύσσει μία μεθοδολογία για την, ανάποδη από το traversal, διαδικασία που θέλεις (να ζωγραφίσεις το δέντρο από δοθέν key sequence). Απ' ό,τι κατάλαβα όμως, πρέπει να σου δίνονται οι ακολουθίες από 2 τουλάχιστον τρόπους διάσχισης για να λυθεί το πρόβλημα. Εσύ διαθέτεις μόνο την ακολουθία που προκύπτει από preorder διάσχιση. Έτσι, το μόνο σίγουρο είναι ότι η ρίζα είναι το 85 και δε μπορείς να προχωρήσεις παρακάτω. Αν κατάλαβα καλά δηλαδή...

[ΠάρηςΓ]

Εμένα μου μοιαζει για δεντρο αναζήτησης.

[narcotic]

Εμένα μου μοιαζει για δεντρο αναζήτησης.

 

Από όσο μπορώ να θυμηθώ όταν σου δίνει κάποια κλειδιά και θες να δημιουργήσεις δέντρο το δέντρο πρέπει να είναι δυαδικο (bst). Δηλαδη ενα δεντρο που ολα τα περιεχομενα στο αριστερο υποδεντρο ειναι μικροτερα απο το περιεχομενο της ριζας του και στο δεξιο αντιστοιχα μεγαλυτερα απο την ριζα του. Αφού το δημιουργήσεις από τα κλειδιά τότε του κανεις διασχιση ανάλογα με το τι σου έχει ζητήσει.

 

Απλά να εχεις υπόψιν ότι άμα κανεις ενδοδιατεταγμενη διασχιση έχεις το περιεχόμενο του δέντρου σε αύξουσα σειρά (tree sort)

 

Παρολαυτά ένας λίγο πιο έμπειρος σου βγάζει απευθείας το δέντρο από την διασχιση (στο εχω γραψει for dummies σε προηγουμενο ποστ)

[miss_kathy]

Οκ σας ευχαριστω πολυ!!

[karabouzouk...]

Θεωριτική ερώτηση για να μην ανοίξω άλλο topic..

Το βαθος ενώς δέντρου πώς υπολογίζεται σε διαδικά ή όχι δέντρα..? Είναι πάντα το πλύθος των επιπέδων του..?

[ΠάρηςΓ]

Ναι το πλήθος των επιπέδων είναι.

if(!t) return 0;

int hl=Height(t->leftPedi);

int hr=Height(t->reksiopedi);

if(hl>hr) return ++hl;

return hr++