Εύρεση κάθε path από το root μέχρι τα φύλλα ενός δέντρου (Java)

[kymagr]

Γειά σας, θέλω τη βοήθειά σας γιατί έχω κολλήσει σε κάποιο σημείο στο πρόγραμμα που φτιάχνω σε Java. Έχω μία δική μου δομή Tree με δικά μου TreeNodes. Τα TreeNodes αποτελούνται από τα εξής πεδία:

private int level;

private String label = null;

private String data = null;

private TreeNode parent = null;

private Vector <TreeNode> children = null;

 

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

 

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

 

Ευχαριστώ πολύ.

[ΠάρηςΓ]

Ειναι διαδυκο το δεντρο η όχι;

 

---------- Το μήνυμα προστέθηκε στις 16:16 ----------

 

Σαν πρωτη σκεψη θα δοκίμαζα breadth first διασχηση. Εαν κατα τη διασχιση έβρισα ενα κομβο που εχει null children θα το προσθετα σε μια λιστα

[kymagr]

Δυστυχώς ξέχασα να το αναφέρω, δεν είναι δυαδικό το δέντρο. Επίσης δεν έχουν όλοι οι κόμβοι τον ίδιο αριθμό παιδιών.

 

Σαν πρωτη σκεψη θα δοκίμαζα breadth first διασχηση. Εαν κατα τη διασχιση έβρισα ενα κομβο που εχει null children θα το προσθετα σε μια λιστα

 

Αυτό που δοκίμασα ήταν η depth first διάσχηση αλλά δε μου έβγαλε αυτό ακριβώς που ήθελα. Θα το σκεφτώ αυτό που πρότεινες να δω αν μου κάνει. Σε πρώτη φάση χρησιμοποιώ τη breath first διάσχηση για να αριθμήσω το δέντρο κατά συγκεκριμένο τρόπο.

[ΠάρηςΓ]

Δε χρειάζεται αριθμηση. Απλα θα περασει ο αλγοριθμος απο ολους τους κομβους μια φορα και θα ελεγχεις εαν ο κομβος ειναι κενος.

Γραψε οτι εχεις κανει η στειλτο μου καπως

[kymagr]

Δε χρειάζεται αριθμηση. Απλα θα περασει ο αλγοριθμος απο ολους τους κομβους μια φορα και θα ελεγχεις εαν ο κομβος ειναι κενος.

Γραψε οτι εχεις κανει η στειλτο μου καπως

 

Την αρίθμηση απλά την κάνω γιατί τη χρειάζομαι κάπου αλλού. Δεν την κάνω για να βρω το path.

 

Ωραία, όταν βρίσκω κάποιο κόμβο που δεν έχει παιδιά, θα παίρνω το path προς τα πίσω μέχρι να φτάσω στο getParent() == null;

[ΠάρηςΓ]

Αναλογα την προσεγκιση σου.Δηλαδη με πιο τροπο τραβερσάρεις το δεντρο.

Κοιτα σιγουρα υπάρχουν πολλοι τροποι αλλα αυτος που μπορω να σκεφτω τωρα ειναι breadth φιρστ. Ισως να υπαρχει και πολυ ταχυτερος..

 

1.Βαζεις σε μια FIFO αρχικα την αρχη του δεντρου.Που δεν εχει παρεντ δλδ.

2.Οσο η ΦΙΦΟ δεν ειναι κενη

2_1 Σβησε το πρωτο στοιχείο της ΦΙΦΟ και βαλτο καπου a=πρωτοστοιχειο

2_2 Βαλε ολα τα παιδιά του στη φιφο.

2_3 Εαν δεν εχει παιδια απλα βαλτο σε ενα βεκτορ

2_4 Αρχη του λουπ

 

Τελος θα εχεις το βεκτορ με ολα τα φυλα που δεν εχουν απογονους

[kymagr]

Αυτό σκέφτηκα και εγώ γράφοντας το τελευταίο μήνυμα, αλλά μετά έφυγα και δεν μπόρεσα να γράψω άλλο. Νομίζω ότι δε χρειάζεται να κρατήσω κάπου το πρώτο στοιχείο της δομής αν αυτό έχει παιδιά (στο βήμα 2_1 που περιγράφεις). Αν έχει πολύ απλά μπαίνουν τα παιδιά του στη δομή, αν όχι θα πάει στο vector που θα κρατάω τα φύλλα του δέντρου. Θα το γράψω σε κώδικα τώρα και αν θέλεις τον κάνω και copy - paste εδω αν έχεις να σχολιάσεις κάτι.

[ΠάρηςΓ]

Πως θα ελεγνξεις και πως θα αναφερθεις σε αυτο αν δε το κρατήσεις καπου;

Γραψε κωδικα και βλέπουμε

[kymagr]

Ο κώδικας βάσει του οποίου του δίνεις ένα node στο δέντρο και σου επιστρέφει όλα τα full paths των φύλλων που βρίσκονται από αυτό το node και κάτω περιέχοντας τη διαδρομή από το root μέχρι το κάθε φύλλο.

 

>
   private Vector <Vector<TreeNode>> findFullPaths(TreeNode node) {
       
       // vector that keeps a full path
       Vector <TreeNode> path;

       // vector that keeps all full paths
       Vector <Vector<TreeNode>> paths = new Vector<Vector<TreeNode>> ();

       // vector that keeps the leaves nodes of tree
       Vector <TreeNode> leaves = new Vector <TreeNode> ();

       // creates an empty queue
       LinkedList <TreeNode> queue = new LinkedList <TreeNode> ();

       // enqueues node
       queue.add(node);

       // finds leaf nodes of tree
       while (!queue.isEmpty()) {
           // dequeues the first node of the queue
           node = queue.removeFirst();
           // gets number of node's children
           int children = node.getNumOfChildren();
           // if node has not any child
           if (children == 0) {
               // adds node into leaves vector
               leaves.add(node);
           } else {
               // enqueues each node's child
               for (int i=0; i< children; i++) {
                   queue.add(node.getChildAt(i));
               }
           }
       }
       
       // gets the number of leaves, that is the number of unique paths
       int numOfPaths = leaves.size();

       // initializes paths vector
       for (int i=0; i<numOfPaths; i++) {
           // gets a leaf from leaves vector
           node = leaves.get(i);
           // gets the level of this node
           int level = node.getLevel();
           // creates a new path with such nodes as the level of current node
           path = new Vector <TreeNode> (level);
           // adds current node at right position into path
           path.add(--level, node);
           // while parent is not null
           while ((node = node.getParent()) != null) {
               // adds node into path
               path.add(--level, node);
           }
           // adds a full path into paths vector
           paths.add(path);
       }

       return paths;
   }

[ΠάρηςΓ]

Mια χαρα μου φαινεται

[kymagr]

Και μένα μου φαίνεται εντάξει, δεν το έχω τεστάρει ακόμα. Θα το κάνω αύριο και αν είναι θα ξαναγράψω. Σ' ευχαριστώ πολύ για τη βοήθειά σου!!!! Καλό βράδυ...