δημιουργία δυαδικου δεντρου αναζητησης

[kathrin28]

θα παρακαλουσα οποιος μπορει να με βοηθησει στη δημιουργία ενός δυαδικού δέντρου αναζητησης.

προδιατεταγμένη:E C D F A B H I G

ενδοδιατεταγμένη C A F E H I B G

να γίνουν και οι δύο διατάξεις σε ένα δέντρο

έχω βρει τη ρίζα του δέντρου έχω φτοάξει το αριστερό υπόδεντρο έχω βρει ότι το Β είναι η ρίζα του δεξιού υπόδεντρου δεν μπορώ να διατάξω το H I G.με μπερδεύει η ενδοδιατεταγμένη

[Apanepai]

Αυτό εδώ το Java Applet θα σε βοηθήσει να κατανοήσεις τα πράγματα με μερικά πειράματα.

 

http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html

 

 

Επειδή παίρνει ως τιμές μόνο ακέραιους κάνε μία αντιστοίχιση για το κάθε γράμμα που έχεις.

 

Για περισσότερες λεπτομέρειες πρέπει να κοιτάξεις και την ανάλογη θεωρία (google it).

[chigal]

Είσαι σίγουρη για την εκφώνηση?

 

inorder traversal ενός δυαδικού δέντρου αναζήτησης δίνει πάντα τα περιεχόμενα ταξινομημένα (δηλαδή θα έπρεπε να είναι A B C D E F G H I), οπότε το δεύτερο ερώτημα δεν έχει νόημα.

 

Ούτε η πρώτη σειρά βγάζει σωστό δέντρο αναζήτησης.

[kathrin28]

Είσαι σίγουρη για την εκφώνηση?

 

inorder traversal ενός δυαδικού δέντρου αναζήτησης δίνει πάντα τα περιεχόμενα ταξινομημένα (δηλαδή θα έπρεπε να είναι A B C D E F G H I), οπότε το δεύτερο ερώτημα δεν έχει νόημα.

 

Ούτε η πρώτη σειρά βγάζει σωστό δέντρο αναζήτησης.

 

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

[chigal]

Α, είναι και οι δύο για το ίδιο δέντρο, δεν το είχα προσέξει.

Οκ, οπότε όπως είπες, δουλεύεις με τον ίδιο τρόπο για να τοποθετήσεις τα H, I, G.

Το Η είναι μικρότερο του Β, άρα γίνεται ρίζα του αριστερού υποδέντρου του Β.

Το I είναι επίσης μικρότερο του Β, αλλά μεγαλύτερο του Ι άρα γίνεται δεξί παιδί του Η.

Τέλος το G είναι μεγαλύτερο του Β, άρα πάει δεξιά.

[kathrin28]

Α, είναι και οι δύο για το ίδιο δέντρο, δεν το είχα προσέξει.

Οκ, οπότε όπως είπες, δουλεύεις με τον ίδιο τρόπο για να τοποθετήσεις τα H, I, G.

Το Η είναι μικρότερο του Β, άρα γίνεται ρίζα του αριστερού υποδέντρου του Β.

Το I είναι επίσης μικρότερο του Β, αλλά μεγαλύτερο του Ι άρα γίνεται δεξί παιδί του Η.

Τέλος το G είναι μεγαλύτερο του Β, άρα πάει δεξιά.

 

πως κρίνω ότι το Η είναι μικρότερο από το Β;

[chigal]

Απο το inorder traversal: D C A F E H I B G

 

Γνωρίζουμε ότι αυτή τη σειρά τα δίνει ταξινομημένα από μικρότερο προς μεγαλύτερο. Αφού το Η εμφανίζεται πριν το Β, θα είναι μικρότερο.

 

Πιστεύω για τη συγκεκριμένη μορφή άσκησης βοηθά να αναθέσεις νούμερα στα γράμματα:

D=1, C=2, A=3, κτλ.

 

Μετά, μετέφρασε το E C D F A B H I G με βάση αυτή την αντιστοιχία (δηλαδή 5 2 1 κτλ) , φτιάξε το δέντρο με τη διαδικασία που ξέρεις χρησιμοποιώντας τα νούμερα, και μετά "μετέφρασέ" τα πάλι σε γράμματα. Έτσι, αντί να σκέφτεσαι "α, το Η είναι μικρότερο του Β" (πράγμα που δείχνει ανάποδο), θα σκέφτεσαι "το 6 είναι μικρότερο του 8".