Διάσχιση δυαδικού δέντρου!!

Βρήκες ή ψάχνεις κάτι ενδιαφέρον για τους τομείς των Μαθηματικών, της Φυσικής ή της Πληροφορικής; Για πέρνα να τα πούμε...

Συντονιστές: kostas213, markelos, Tulis

morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Καλησπερα σε ολους! Ειμαι καινουρια στο forum και θα ηθελα να κανω μια ερωτηση. Πως μπορω εχοντας τα κλειδια ενος δυαδικου δεντρου σε προδιαταξη να το σχεδιασω?Εχω κανει αρκετα παραδειγματα αλλα δεν ειμαι σιγουρη για τον τροπο. Για παραδειγμα εχω τα εξης κλειδια:85, 43, 93, 35,1, 3,91, 35,12,42, 34,32,85,77,80,70,28,79,9 σε προδιαταξη και θελω να σχεδιασω αυτο το δεντρο. Οποιαδηποτε βοηθεια ειναι παραπανω απο ευπροσδεκτη!!
Laplace
Δημοσιεύσεις: 128
Εγγραφή: Πέμ Ιαν 18, 2007 12:39 pm

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από Laplace »

Ενα δυαδικό δέντρο το αναπαριστάς με τη δομή δεδομένων σωρό.Δεν χρειάζεσαι δείκτες για να κάνεις τη διάσχιση. Πχ αν έχεις ένα δυαδικό δέντρο με στοιχεία 1,2,5,10,3,7,11 θα αναπαρασταθεί |1|2|5|10|3|7|11| όπου 1 είναι η ρίζα του δέντρου και τα άλλα τα φύλα.Σε βάθος n έχεις πλήθος φύλλων 2^n. Δηλαδή σε βάθος 2 στο παράδειγμα που έκανα έχει 2^2 (4 στοιχεία) , τα τελευταία 4 του πίνακα (10,3,7,11). Τώρα αν το πρόβλημα σου ζητάει και ταξινόμηση επειδή ισχύει η σχέση της διάταξης σωρού δηλαδή, για κάθε στοιχείο v σε έναν κόμβο i, το στοιχείο w στο γονέα του i ικανοποιεί τη σχέση key(w) <= key(v) εφάρμοσε μέθοδο heapify-up ή heapify-down για το δέντρο μέχρι να ταξινομηθεί ολόκληρο.Οι μέθοδοι υπάρχουν και στη wikipedia.
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Επειδη μπερδευτηκα λιγο, πρακτικα αυτο το δεντρο για παραδειγμα πως θα μπορουσα να το φτιαξω??Δεν πρεπει να ξεκινησω με το πρωτο κλειδι σαν ριζα, και στη συνεχεια ακολουθωντας την προδιαταξη, δλδ ριζα αριστερο υποδεντρο δεξι να το φτιαξω?
Τα αριστερα παιδια εχουν κλειδι μικροτερο της ριζας και τα δεξια μεγαλυτερο?Σορυ αν σε κουραζω και ευχαριστω πολυ!
Laplace
Δημοσιεύσεις: 128
Εγγραφή: Πέμ Ιαν 18, 2007 12:39 pm

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από Laplace »

Η ρίζα είναι το μικρότερο στοιχείο και οι απόγονοι έχουν μεγαλύτερο κλειδί από τον πρόγονό τους. Στα φύλλα σε ένα επίπεδο δεν παίζει ρόλο από οτι θυμάμαι η διάταξη(μικρότερο,μεγαλύτερο κλπ) . Αυτή είναι και η ιδιότητα του δέντρου.Οι απόγονοι έχουν μεγαλύτερα κλειδιά από τους προγόνους.Π.χ. σε αυτό (85, 43, 93, 35,1, 3,91, 35,12,42, 34,32,85,77,80,70,28,79,9) η ρίζα είναι το 1.Για βάθος n=1 τα φύλλα ειναι 3,9 (βάλτα όπως θες). Για n=2 τα 2^2=4 φύλλα ειναι 12,28,32,34 .Για n=3 τα 2^3 φύλλα είναι ... Κατάλαβες νομίζω πώς πάει. Αυτό εννοείς?
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Ναι, καταλαβα πως δημιουργειται το δεντρο ευχαριστω!Αλλα αν το διατρεξω σε προδιαταξη, η ακολουθια των κλειδιων δεν θα ειναι αυτη που εχω. Εγω θα ηθελα αν γινεται εχοντας αυτη την ακολουθια που γραφω να φτιαξω το δεντρο, δλδ εχοντας σαν ριζα το 85 κοκ.
Άβαταρ μέλους
LocknLoad
Forum Administrator
Forum Administrator
Δημοσιεύσεις: 2250
Εγγραφή: Κυρ Οκτ 07, 2007 5:34 pm

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από LocknLoad »

Πρωτα θα τους ταξινομησεις. Μετα θα κανεις divide and conquer και θα βαζεις τα "μεσαια"
πχ
13,20,7,9,1,15,10
θα τα κανεις:
1,7,9,10,13,15,20
το μεσαιο ειναι το 10 το οποιο θα ειναι η ριζα και θα εχεις 1,7,9 και 13,15,20
Παλι τα μεσαια κτλ
στο τελος θα εχεις

Κώδικας: Επιλογή όλων

     10
  7     15
1  9  13  20
Καταλαβες?
Ναι, [you] σε παρακολουθώ!

Εικόνα


@[you]
Εικόνα
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Ναι, ναι ευχαριστω πολυ!!
Άβαταρ μέλους
theos
Δημοσιεύσεις: 762
Εγγραφή: Κυρ Νοέμ 05, 2006 4:53 am
Real Name: Αριστοτέλης-Εμμανουήλ Θάνος-Φίλης (Μάνος) ge04017
Gender: Male
Τοποθεσία: Alwaysland

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από theos »

morgana23 έγραψε:Καλησπερα σε ολους! Ειμαι καινουρια στο forum και θα ηθελα να κανω μια ερωτηση. Πως μπορω εχοντας τα κλειδια ενος δυαδικου δεντρου σε προδιαταξη να το σχεδιασω?Εχω κανει αρκετα παραδειγματα αλλα δεν ειμαι σιγουρη για τον τροπο. Για παραδειγμα εχω τα εξης κλειδια:85, 43, 93, 35,1, 3,91, 35,12,42, 34,32,85,77,80,70,28,79,9 σε προδιαταξη και θελω να σχεδιασω αυτο το δεντρο. Οποιαδηποτε βοηθεια ειναι παραπανω απο ευπροσδεκτη!!
Η πρώτη τιμή γίνεται ρίζα. Για τη δεύτερη συγκρίνεις με τη ρίζα και αν είναι μεγαλύτερη τη βάζεις δεξί παιδί, αλλιώς αριστερό. Στο νιοστό βήμα συγκρίνεις αρχικά με τη ρίζα και ακολουθείς τον κανόνα: Αν είναι μεγαλύτερο συγκρίνω με τη ρίζα του δεξιού υποδέντρου αλλιώς με του αριστερού μέχρι να φτάσω στα φύλλα όπου και τοποθετώ την τιμή.

Ο αλγόριθμος αυτός στη χειρότερη περίπτωση σου δίνει 1+2+3+4+...+n=(n+1)*n/2 συγκρίσεις, όπου n ο αριθμός των στοιχείων που έχεις. Τελικά θα έχεις πολυπλοκότητα Ο(n^2)

Όμως, δεν είμαι σίγουρος ότι κατάλαβα τι ακριβώς θέλεις να κάνεις. Δώσε ένα παράδειγμα με την τελική λύση και εξήγησε τι εννοείς λέγοντας "προδιάταξη"
Λογική είναι η τέχνη να κάνεις λάθος με αυτοπεποίθηση!!!
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Ναι, και εγω αυτο τον τροπο ηξερα για να φτιαχνω δεντρα αλλα δεν ημουν σιγουρη για το αν ειναι σωστος. Για να γινω πιο συγκεκριμενη, επισυναπτω ενα screenshot με ενα παραδειγμα. Οπως θα δεις, στο σχημα φαινεται ενα δεντρο και απο κατω η προδιαταξη του. Εγω θελω να κανω το αναποδο, δλδ δοσμενης της προδιαταξης να σχεδιασω το δεντρο.
Συνημμένα
1.JPG
Άβαταρ μέλους
theos
Δημοσιεύσεις: 762
Εγγραφή: Κυρ Νοέμ 05, 2006 4:53 am
Real Name: Αριστοτέλης-Εμμανουήλ Θάνος-Φίλης (Μάνος) ge04017
Gender: Male
Τοποθεσία: Alwaysland

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από theos »

Μια χαρά σωστός είναι ο τρόπος και σου είπα και την πολυπλοκότητά του παραπάνω. Στο παράδειγμα που δίνεις όμως, ξεκινάς να βάζεις δεξιά της ρίζας το μεγαλύτερο και μετά μπαίνουν τα μεγαλύτερα αριστερά. Δεν ξέρω που το βρήκες το applet (και όχι πως έχει και κανένα σπουδαίο πρόβλημα), απλώς μου φαίνεται πιο "ωραίο" στο μάτι να μπαίνουν όλα τα μεγαλύτερα δεξιά ή όλα αριστερά.

Σε τέτοιου είδους προβλήματα, πάντως, υπάρχουν πολλά διαφορετικά πράγματα που μπορείς να κάνεις, και είναι όλα σωστά. Πχ αυτό που σου είπε παραπάνω ο laplace και αυτό που σου είπε ο locknload είναι σωστότατα. Το θέμα είναι τι θέλεις εσύ να κάνεις ;)
Λογική είναι η τέχνη να κάνεις λάθος με αυτοπεποίθηση!!!
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Το applet το βρηκα εδω:http://nova.umuc.edu/~jarc/idsv/lesson1.html αν θελεις να το δεις. Ευχαριστω πολυ, μου εφυγε ενα αγχος γιατι εχοντας σαν οδηγο αυτο το applet μπερδευομουν χειροτερα.. :e_wink:
jimer
Δημοσιεύσεις: 15
Εγγραφή: Τετ Ιουν 18, 2008 3:47 pm
Real Name: Dimitris
Gender: Male
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από jimer »

Από ότι κατάλαβα αυτό που θέλεις είναι από την προδιάταξη(pre order) να βγάλεις το αρχικό δέντρο. Κάτι τέτοιο δεν γίνεται γιατί μία preorder μπορεί να σου δώσει πολλά πιθανά δέντρα.
Συγκεκριμένα η διέλευση preorder σου τυπώνει κόμβους έτσι ώστε κάθε κόμβος προηγείται των παιδιών του (συνήθως με προτεραιότητα στα αριστερά παιδιά).
Οπότε στο παράδειγμα που δίνεις θα μπορούσε π.χ. το δέντρο να είναι:
ρίζα 85->43->93->35... δηλαδή ένα δέντρο που ο ένας κόμβος είναι κάτω από τον άλλον (δεν έχεις κανένα περιορισμό να είναι πλήρες δυαδικό το δέντρο σου,στο παράδειγμα δεν είναι).Μπορείς να βρεις και άλλα παραδείγματα ακριβώς με την ίδια preorder.
Γενικά μια διέλευση δέντρου απλώς διαβάζει (εκτυπώνει/επεξεργάζεται) τους κόμβους οπότε δεν έχει καμία σχέση η διάταξη.
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Οκ καταλαβα..Απλα ειχα μπερδευτει αλλα τωρα ενταξει!Ευχαριστω!
Laplace
Δημοσιεύσεις: 128
Εγγραφή: Πέμ Ιαν 18, 2007 12:39 pm

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από Laplace »

Δεν ξεκαθάρισες απλά τί ζητάει το πρόβλημα.Δηλαδή, πιο εξειδικευμένα αν το κάνεις αυτό σε java συνήθως σου δίνει το δέντρο σε μορφή πίνακα γειτνίασης δλδ int A[] ={10,5,4,15,12,7,8...} και να πρέπει εσύ να το υλοποιήσεις. Ε,τότε π.χ. μπορείς να κανεις μια quicksort/ bubblesort στα στοιχεία του πίνακα και ύστερα να κάνεις την υλοποίηση και τέλειωσες 2)Άλλη λύση φτιάχνεις το δέντρο με τα στοιχεία ανακατεμένα όπως στα δίνει.Δηλαδή,αρχικά φτιάχνεις έναν κόμβο του δέντρου που έχει 2 απογόνους left,right.
//η κλάση treenode με τον constructor.
public class TreeNode {
TreeNode left;
TreeNode right;

String name;

public TreeNode(String parName) {
name = parName;
}
}

Μετά σε μια άλλη κλάση φτιάχνεις το δέντρο :

public class Tree {
TreeNode root; //φτιάχνω τη ρίζα τύπου TreeNode

/**
*/
public Tree() { //constructor
root = null;
}

Και για να τρέξει κάνω και μια κλάση TreeDemo που έχει τη main και την υλοποίηση του δέντρου :

package dsalg.lab05.tree;

public class TreeDemo {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Tree fam = new Tree(); //φτιάχνει ένα δέντρο με όνομα fam

fam.root = new TreeNode("Maria"); //φτιάχνω τη ρίζα
fam.root.left = new TreeNode("Giannis"); //φτιάχνω τον αριστερό απόγονο της ρίζας Γιάννη
fam.root.right = new TreeNode("Eleni"); // φτιάχνωο τον αριστερό απόγονο της ρίζας Ελένη

TreeNode father = fam.root.left; //φτιάχνω νέο κόμβο τύπου TreeNode father
TreeNode mother = fam.root.right; //φτιάχνω ακόμα 1 κόμβο τύπου TreeNode mother

father.left = new TreeNode("Giwrgos"); //φτιάχνω το left
father.right = new TreeNode("Maria"); // φτιάχνω το right φύλλο με όνομα Μαρία

mother.left = new TreeNode("Nasos");
mother.right = new TreeNode("Xristina");

TreeNode grandFather1 = father.left;
TreeNode grandMother1 = father.right;

TreeNode grandFather2 = mother.left;
TreeNode grandMother2 = mother.right;

// ...

System.out.println("Tree node count: " + fam.nodeCount());
}

}

η Υλοποιηση δέντρου μοιάζει πολλή με διπλά συνδεδεμένη λίστα.Τώρα θα ψάξω αν θες και κώδικα ταξινόμησης, γιατί αφού το φτιάξεις πρέπει να κάνεις heapify-up ή heapify-down για να ταξινομηθεί ώστε να είναι όντως δέντρο αν χρησιμοποιήσεις τη 2η μέθοδο.
morgana23
Δημοσιεύσεις: 10
Εγγραφή: Παρ Ιουν 26, 2009 1:57 am
Real Name: katerina
Gender: Female
Facebook ID: 0

Re: Διάσχιση δυαδικού δέντρου!!

Δημοσίευση από morgana23 »

Αυτο που ηθελα ηταν δοσμενης της preorder ενος δεντρου, να μπορω να το φτιαξω. Καταλαβα πως πρεπει να γινει, θα παρω το πρωτο στοιχειο σαν ριζα, θα συγκρινω το δευτερο με τη ριζα, αν ειναι μεγαλυτερο θα παει δεξια και αν ειναι μικροτερο αριστερα κοκ..Σωστός δεν ειναι αυτος ο τροπος?
Απάντηση

Επιστροφή στο “Ζητήματα Μαθηματικών - Φυσικής - Πληροφορικής”