Μενού

Δέντρα σε C ++: Βασική ορολογία, τεχνικές διέλευσης και τύποι δέντρων C ++

  • Κύριος
  • Αλλα
  • Δέντρα σε C ++: Βασική ορολογία, τεχνικές διέλευσης και τύποι δέντρων C ++

trees c basic terminology

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Αυτός ο σε βάθος οδηγός για τα δέντρα C ++ εξηγεί τους τύπους δέντρων, τις τεχνικές διασταύρωσης δέντρων και τη βασική ορολογία με εικόνες και παραδείγματα προγραμμάτων:

Σε αυτήν τη σειρά C ++, μέχρι στιγμής έχουμε δει τη γραμμική δομή δεδομένων τόσο στατικής όσο και δυναμικής φύσης. Τώρα θα προχωρήσουμε με τη μη γραμμική δομή δεδομένων. Η πρώτη δομή δεδομένων σε αυτήν την κατηγορία είναι 'Δέντρα'.

Τα δέντρα είναι μη γραμμικές ιεραρχικές δομές δεδομένων. Ένα δέντρο είναι μια συλλογή κόμβων που συνδέονται μεταξύ τους μέσω «άκρων» που είναι κατευθυνόμενες ή μη κατευθυνόμενες. Ένας από τους κόμβους ορίζεται ως 'Root node' και οι υπόλοιποι κόμβοι ονομάζονται θυγατρικοί κόμβοι ή οι φύλλο κόμβων του ριζικού κόμβου.

Γενικά, κάθε κόμβος μπορεί να έχει όσα παιδιά αλλά μόνο έναν γονικό κόμβο.

=> Ρίξτε μια ματιά στην Ολόκληρη Σειρά Εκπαίδευσης C ++

Δέντρο σε C ++

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

Τι θα μάθετε:

Δέντρα σε C ++

Δίνεται παρακάτω ένα δέντρο παραδείγματος με τα διάφορα μέρη του.

Δέντρο σε C ++ με τα διάφορα μέρη του

Ας δούμε τους ορισμούς ορισμένων βασικών όρων που χρησιμοποιούμε για δέντρα.

  • Κόμβος ρίζας: Αυτός είναι ο κορυφαίος κόμβος στην ιεραρχία δέντρων. Στο παραπάνω διάγραμμα, ο κόμβος Α είναι ο ριζικός κόμβος. Λάβετε υπόψη ότι ο ριζικός κόμβος δεν έχει γονέα.
  • Κόμβος φύλλων: Είναι ο πιο κάτω κόμβος σε μια ιεραρχία δέντρων. Οι κόμβοι φύλλων είναι οι κόμβοι που δεν έχουν θυγατρικούς κόμβους. Είναι επίσης γνωστοί ως εξωτερικοί κόμβοι. Οι κόμβοι E, F, G, H και C στο παραπάνω δέντρο είναι όλοι οι κόμβοι φύλλων.
  • Υπόγειο: Το δευτερεύον δέντρο αντιπροσωπεύει διάφορους απογόνους ενός κόμβου όταν η ρίζα δεν είναι μηδενική. Ένα δέντρο συνήθως αποτελείται από έναν ριζικό κόμβο και ένα ή περισσότερα δευτερεύοντα δέντρα. Στο παραπάνω διάγραμμα, (B-E, B-F) και (D-G, D-H) είναι υποδέντρα.
  • Γονικός κόμβος: Οποιοσδήποτε κόμβος εκτός από τον ριζικό κόμβο που έχει έναν θυγατρικό κόμβο και μια άκρη προς τα πάνω προς τον γονέα.
  • Κόμβος προγόνου: Είναι οποιοσδήποτε προκάτοχος κόμβος σε μια διαδρομή από τη ρίζα προς αυτόν τον κόμβο. Σημειώστε ότι η ρίζα δεν έχει προγόνους. Στο παραπάνω διάγραμμα, οι Α και Β είναι οι πρόγονοι του Ε.
  • Κλειδί: Αντιπροσωπεύει την τιμή ενός κόμβου.
  • Επίπεδο: Αντιπροσωπεύει τη δημιουργία ενός κόμβου. Ένας ριζικός κόμβος βρίσκεται πάντα στο επίπεδο 1. Οι θυγατρικοί κόμβοι της ρίζας βρίσκονται στο επίπεδο 2, τα εγγόνια της ρίζας βρίσκονται στο επίπεδο 3 και ούτω καθεξής. Γενικά, κάθε κόμβος βρίσκεται σε επίπεδο υψηλότερο από το γονικό του.
  • Μονοπάτι: Η διαδρομή είναι μια ακολουθία διαδοχικών άκρων. Στο παραπάνω διάγραμμα, η διαδρομή προς το Ε είναι A => B-> E.
  • Βαθμός: Ο βαθμός ενός κόμβου δείχνει τον αριθμό των παιδιών που έχει ένας κόμβος. Στο παραπάνω διάγραμμα, ο βαθμός B και D είναι 2 ο καθένας ενώ ο βαθμός C είναι 0.

Τύποι δέντρων C ++

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

Τύποι δέντρων σε C ++

# 1) Γενικό δέντρο

Το γενικό δέντρο είναι η βασική αναπαράσταση ενός δέντρου. Έχει έναν κόμβο και έναν ή περισσότερους θυγατρικούς κόμβους. Ο κόμβος ανώτερου επιπέδου, δηλαδή ο ριζικός κόμβος υπάρχει στο επίπεδο 1 και όλοι οι άλλοι κόμβοι μπορεί να υπάρχουν σε διάφορα επίπεδα.

Ένα Γενικό Δέντρο φαίνεται στο παρακάτω σχήμα.

Γενικά δέντρο

Όπως φαίνεται στο παραπάνω σχήμα, ένα γενικό δέντρο μπορεί να περιέχει οποιονδήποτε αριθμό υποδένδρων. Οι κόμβοι B, C και D υπάρχουν στο επίπεδο 2 και είναι αδελφικοί κόμβοι. Παρομοίως, οι κόμβοι E, F, G και H είναι επίσης αδελφικοί κόμβοι.

Οι κόμβοι που υπάρχουν σε διαφορετικά επίπεδα μπορεί να εμφανίζουν σχέση γονέα-παιδιού. Στην παραπάνω εικόνα, οι κόμβοι B, C και D είναι παιδιά του A. Οι κόμβοι E και F είναι παιδιά του Β, ενώ οι κόμβοι G και H είναι παιδιά του D.

Το γενικό δέντρο παρουσιάζεται παρακάτω χρησιμοποιώντας την εφαρμογή C ++:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Παραγωγή:

Το γενικό δέντρο που δημιουργήθηκε έχει ως εξής:

10

/

20 30

/

40

# 2) Δάση

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

Δάση

πώς να ανοίξετε ένα αρχείο torrent στα παράθυρα

Στο παραπάνω σχήμα, αποκτήσαμε δύο δάση διαγράφοντας τον ριζικό κόμβο Α και τις τρεις άκρες που συνδέουν τον ριζικό κόμβο με τους κόμβους B, C και D.

# 3) Δυαδικό δέντρο

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

Το παρακάτω σχήμα δείχνει ένα δυαδικό δέντρο.

Δυαδικό δέντρο

Στην παραπάνω εικόνα, βλέπουμε ότι οι κόμβοι Α, Β και Δ έχουν δύο παιδιά το καθένα. Ένα δυαδικό δέντρο στο οποίο κάθε κόμβος έχει ακριβώς μηδέν ή δύο παιδιά ονομάζεται πλήρες δυαδικό δέντρο. Σε αυτό το δέντρο, δεν υπάρχουν κόμβοι που έχουν ένα παιδί.

Ένα πλήρες δυαδικό δέντρο έχει ένα δυαδικό δέντρο που είναι πλήρως γεμάτο με εξαίρεση το χαμηλότερο επίπεδο που γεμίζει από αριστερά προς τα δεξιά. Το δυαδικό δέντρο που φαίνεται παραπάνω είναι ένα πλήρες δυαδικό δέντρο.

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

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

Παραγωγή:

Δυαδικό δέντρο δημιουργήθηκε:

5 10 15 20 30 40 45

# 4) Δυαδικό δέντρο αναζήτησης

Το δυαδικό δέντρο που ταξινομείται ονομάζεται δέντρο δυαδικής αναζήτησης. Σε ένα δέντρο δυαδικής αναζήτησης, οι κόμβοι στα αριστερά είναι μικρότεροι από τον ριζικό κόμβο, ενώ οι κόμβοι στα δεξιά είναι μεγαλύτεροι ή ίσοι με τον ριζικό κόμβο.

Ένα παράδειγμα δέντρου δυαδικής αναζήτησης φαίνεται παρακάτω.

Δυαδικό δέντρο αναζήτησης

Στο παραπάνω σχήμα, μπορούμε να δούμε ότι οι αριστεροί κόμβοι είναι όλοι λιγότερο από 20 που είναι το ριζικό στοιχείο. Οι σωστοί κόμβοι, από την άλλη πλευρά, είναι μεγαλύτεροι από τον ριζικό κόμβο. Το δυαδικό δέντρο αναζήτησης χρησιμοποιείται στις τεχνικές αναζήτησης και ταξινόμησης.

# 5) Δέντρο έκφρασης

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

Ένα απλό δέντρο έκφρασης φαίνεται παρακάτω.

Δέντρο έκφρασης

Στο παραπάνω δέντρο δείγματος έκφρασης, αντιπροσωπεύουμε την έκφραση (a + b) / (a-b). Όπως φαίνεται στο παραπάνω σχήμα, οι κόμβοι χωρίς φύλλα του δέντρου αντιπροσωπεύουν τους τελεστές της έκφρασης ενώ οι κόμβοι φύλλων αντιπροσωπεύουν τους τελεστές.

Τα δέντρα έκφρασης χρησιμοποιούνται κυρίως για την επίλυση αλγεβρικών εκφράσεων.

Τεχνικές διέλευσης δέντρων

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

Στην περίπτωση των δέντρων, έχουμε διαφορετικές τεχνικές διασταύρωσης όπως αναφέρονται παρακάτω:

# 1) Με τη σειρά: Σε αυτήν την διασταυρούμενη τεχνική, διασχίζουμε πρώτα το αριστερό υποδένδρο έως ότου δεν υπάρχουν πλέον κόμβοι στο αριστερό υποδένδρο. Μετά από αυτό, επισκέπτουμε τον ριζικό κόμβο και μετά προχωράμε για να διασχίσουμε το σωστό υποδένδρο έως ότου δεν υπάρχουν πλέον κόμβοι για να διασχίσουμε το σωστό υποδένδρο. Έτσι, η σειρά του traversal inOrder είναι αριστερά-> root-> δεξιά.

# 2) Προπαραγγελία: Για την προπαραγγελία τεχνική διέλευσης, επεξεργαζόμαστε πρώτα τον ριζικό κόμβο, μετά διασχίζουμε ολόκληρο το αριστερό υποδένδρο και τέλος, διασχίζουμε το δεξί υποδένδρο. Ως εκ τούτου, η σειρά διέλευσης προπαραγγελίας είναι root-> αριστερά-> δεξιά.

# 3) Παραγγελία: Στην τεχνική μετάβασης μετά την παραγγελία, διασχίζουμε το αριστερό υποδένδρο, στη συνέχεια το δεξί υπόστρωμα και τέλος τον ριζικό κόμβο. Η σειρά του traversal για την τεχνική postorder είναι αριστερή-> δεξιά-> ρίζα.

Εάν το n είναι ο ριζικός κόμβος και τα «l» και «r» είναι αριστερά και δεξιά κόμβοι του δέντρου αντίστοιχα, τότε οι αλγόριθμοι διέλευσης δέντρων είναι οι εξής:

Σε αλγόριθμο σειράς (lnr):

  1. Διασχίστε το αριστερό υποδένδρο χρησιμοποιώντας το inOrder (αριστερό-υποδένδρο).
  2. Επισκεφτείτε τον ριζικό κόμβο (n).
  3. Διασχίστε το δεξί υποδένδρο χρησιμοποιώντας το inOrder (δεξιό-υποδένδρο).

Αλγόριθμος Preorder (nlr):

  1. Επισκεφτείτε τον ριζικό κόμβο (n).
  2. Διασχίστε το αριστερό υποδένδρο χρησιμοποιώντας προπαραγγελία (αριστερό-υποδένδρο).
  3. Διασχίστε το σωστό υποδένδρο χρησιμοποιώντας προπαραγγελία (δεξιό υποδένδρο).

Αλγόριθμος Postorder (lrn):

  1. Διασχίστε το αριστερό υποδένδρο χρησιμοποιώντας postOrder (αριστερό-υποδένδρο).
  2. Διασχίστε το σωστό υποδένδρο χρησιμοποιώντας postOrder (δεξιό-υπόφυλλο).
  3. Επισκεφτείτε τον ριζικό κόμβο (n).

Από τους παραπάνω αλγόριθμους διασταυρούμενων τεχνικών, βλέπουμε ότι οι τεχνικές μπορούν να εφαρμοστούν σε ένα συγκεκριμένο δέντρο με αναδρομικό τρόπο για να επιτευχθεί το επιθυμητό αποτέλεσμα.

Εξετάστε το ακόλουθο δέντρο.

Αλγόριθμος Postorder (lrn)

Χρησιμοποιώντας τις παραπάνω τεχνικές διασταύρωσης, η ακολουθία διασταύρωσης για το παραπάνω δέντρο δίνεται παρακάτω:

  1. Διαδρομή InOrder: 2 3 5 6 10
  2. Διαδρομή PreOrder: 6 3 2 5 10
  3. Διαδρομή μετά την παραγγελία: 2 5 3 10 6

συμπέρασμα

Τα δέντρα είναι μια μη γραμμική ιεραρχική δομή δεδομένων που χρησιμοποιείται σε πολλές εφαρμογές στον τομέα του λογισμικού.

Σε αντίθεση με τις γραμμικές δομές δεδομένων που έχουν μόνο έναν τρόπο διέλευσης της λίστας, μπορούμε να διασχίσουμε δέντρα με διάφορους τρόπους. Σε αυτό το σεμινάριο είχαμε μια λεπτομερή μελέτη τεχνικών διέλευσης και των διαφόρων τύπων δέντρων.

=> Ρίξτε μια ματιά στον οδηγό για αρχάριους C ++ εδώ

Συνιστώμενη ανάγνωση

^