Μενού

Δομή Δυαδικών Δέντρων Στο C ++

binary tree data structure c

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

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

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

Έτσι, ένα τυπικό δυαδικό δέντρο θα έχει τα ακόλουθα στοιχεία:

  • Ένα αριστερό υπόστρωμα
  • Ένας ριζικός κόμβος
  • Ένα σωστό υποδένδρο

=> Προσέξτε την πλήρη λίστα των μαθημάτων C ++ σε αυτήν τη σειρά.

Δυαδικό δέντρο σε C ++

Τι θα μάθετε:

Δυαδικό δέντρο σε C ++

Μια εικονική αναπαράσταση ενός δυαδικού δέντρου φαίνεται παρακάτω:

Εικονογραφική αναπαράσταση δυαδικού δέντρου

Σε ένα δεδομένο δυαδικό δέντρο, ο μέγιστος αριθμός κόμβων σε οποιοδήποτε επίπεδο είναι 2l-1όπου «l» είναι ο αριθμός επιπέδου.

Έτσι, στην περίπτωση του ριζικού κόμβου στο επίπεδο 1, ο μέγιστος αριθμός κόμβων = 21-1= 20= 1

Καθώς κάθε κόμβος σε ένα δυαδικό δέντρο έχει το πολύ δύο κόμβους, οι μέγιστοι κόμβοι στο επόμενο επίπεδο θα είναι, 2 * 2l-1.

το καλύτερο δωρεάν πρόγραμμα λήψης mp3 για Android

Δεδομένου ενός δυαδικού δέντρου βάθους ή ύψους h, ο μέγιστος αριθμός κόμβων σε ένα δυαδικό δέντρο ύψους h = 2η- 1.

Ως εκ τούτου, σε ένα δυαδικό δέντρο ύψους 3 (φαίνεται παραπάνω), ο μέγιστος αριθμός κόμβων = 23-1 = 7.

Τώρα ας συζητήσουμε τους διάφορους τύπους δυαδικών δέντρων.

Τύποι δυαδικού δέντρου

Ακολουθούν οι πιο συνηθισμένοι τύποι δυαδικών δέντρων.

# 1) Πλήρες δυαδικό δέντρο

Ένα δυαδικό δέντρο στο οποίο κάθε κόμβος έχει 0 ή 2 παιδιά ονομάζεται πλήρες δυαδικό δέντρο.

Πλήρες δυαδικό δέντρο

Παρακάτω φαίνεται ένα πλήρες δυαδικό δέντρο στο οποίο μπορούμε να δούμε ότι όλοι οι κόμβοι του εκτός από τους κόμβους φύλλων έχουν δύο παιδιά. Αν το L είναι ο αριθμός των κόμβων των φύλλων και το «l» είναι ο αριθμός των εσωτερικών ή των μη-φύλλων κόμβων, τότε για ένα πλήρες δυαδικό δέντρο, L = l + 1.

# 2) Πλήρες δυαδικό δέντρο

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

Πλήρες δυαδικό δέντρο

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

# 3) Τέλειο δυαδικό δέντρο

Ένα δυαδικό δέντρο ονομάζεται τέλειο όταν όλοι οι εσωτερικοί κόμβοι του έχουν δύο παιδιά και όλοι οι κόμβοι των φύλλων βρίσκονται στο ίδιο επίπεδο.

Τέλειο δυαδικό δέντρο

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

Ένα τέλειο δυαδικό δέντρο ύψους h έχει 2η- 1 αριθμός κόμβων.

# 4) Ένα εκφυλισμένο δέντρο

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

Ένα εκφυλισμένο δέντρο

Το δέντρο που φαίνεται παραπάνω είναι ένα εκφυλισμένο δέντρο. Όσον αφορά την απόδοση αυτού του δέντρου, τα εκφυλισμένα δέντρα είναι τα ίδια με τις συνδεδεμένες λίστες.

# 5) Ισορροπημένο δυαδικό δέντρο

Ένα δυαδικό δέντρο στο οποίο το βάθος των δύο υποδέντρων κάθε κόμβου δεν διαφέρει ποτέ περισσότερο από 1 ονομάζεται ισορροπημένο δυαδικό δέντρο.

Ισορροπημένο δυαδικό δέντρο

Το δυαδικό δέντρο που φαίνεται παραπάνω είναι ένα ισορροπημένο δυαδικό δέντρο καθώς το βάθος των δύο υποδένδρων κάθε κόμβου δεν υπερβαίνει το 1. Τα δέντρα AVL τα οποία θα συζητήσουμε στα επόμενα σεμινάρια μας είναι ένα κοινό ισορροπημένο δέντρο.

Αναπαράσταση δυαδικού δέντρου

Ένα δυαδικό δέντρο εκχωρείται μνήμη με δύο τρόπους.

# 1) Διαδοχική αναπαράσταση

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

Γενικά, εάν ένας κόμβος αποθηκεύεται στο iουτοποθεσία, στη συνέχεια, το αριστερό και το δεξί παιδί αποθηκεύεται σε θέση 2i και 2i + 1 αντίστοιχα.

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

Δείγμα δυαδικού δέντρου

Η διαδοχική αναπαράσταση του παραπάνω δυαδικού δέντρου έχει ως εξής:

διαδοχική αναπαράσταση του δυαδικού δέντρου

Στην παραπάνω αναπαράσταση, βλέπουμε ότι το αριστερό και το δεξί παιδί κάθε κόμβου αποθηκεύονται στις θέσεις 2 * (node_location) και 2 * (node_location) +1 αντίστοιχα.

Για παράδειγμα, η θέση του κόμβου 3 στον πίνακα είναι 3. Έτσι, το αριστερό παιδί θα τοποθετηθεί σε 2 * 3 = 6. Το δεξί του παιδί θα βρίσκεται στη θέση 2 * 3 +1 = 7. Όπως μπορούμε να δούμε στον πίνακα, τα παιδιά από τα 3 που είναι 6 και 7 τοποθετούνται στη θέση 6 και 7 στη συστοιχία.

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

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

# 2) Αναπαράσταση συνδεδεμένης λίστας

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

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

Αναπαράσταση συνδεδεμένης λίστας

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

  • Αριστερός δείκτης
  • Μέρος δεδομένων
  • Δεξί δείκτη

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

Εφαρμογή δυαδικού δέντρου σε C ++

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

#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

Δυαδικό δέντρο διέλευσης

Έχουμε ήδη συζητήσει διασταυρώσεις στο βασικό μας φροντιστήριο για τα δέντρα. Σε αυτήν την ενότητα, ας εφαρμόσουμε ένα πρόγραμμα που εισάγει κόμβους στο δυαδικό δέντρο και επίσης επιδεικνύει και τις τρεις διασταυρώσεις, δηλαδή inorder, preorder και postorder, για ένα δυαδικό δέντρο.

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(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 bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

Παραγωγή:

Διαδρομή εσωτερικού:

A B C D E F G

Διαδρομή αλληλογραφίας:

G F E D C B A

Προπαραγγελία διέλευσης:

A B C D E F G

Εφαρμογές δυαδικού δέντρου

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

Μερικές από τις σημαντικές εφαρμογές των δυαδικών δέντρων παρατίθενται παρακάτω:

  • Δυαδικά δέντρα αναζήτησης: Τα δυαδικά δέντρα χρησιμοποιούνται για την κατασκευή ενός δέντρου δυαδικής αναζήτησης που χρησιμοποιείται σε πολλές εφαρμογές αναζήτησης όπως σύνολα και χάρτες σε πολλές βιβλιοθήκες γλωσσών.
  • Hash δέντρα: Χρησιμοποιείται για την επαλήθευση κατακερματισμού κυρίως σε εξειδικευμένες εφαρμογές υπογραφής εικόνας.
  • Πλήθος: Οι σωροί χρησιμοποιούνται για την εφαρμογή ουρών προτεραιότητας που χρησιμοποιούνται για δρομολογητές, προγραμματιστές επεξεργαστές στο λειτουργικό σύστημα κ.λπ.
  • Κωδικοποίηση Huffman: Το δέντρο κωδικοποίησης Huffman χρησιμοποιείται σε αλγόριθμους συμπίεσης (όπως συμπίεση εικόνας) καθώς και σε κρυπτογραφικές εφαρμογές.
  • Σύνταξη δέντρου: Οι μεταγλωττιστές συχνά κατασκευάζουν δέντρα σύνταξης που δεν είναι παρά δυαδικά δέντρα για την ανάλυση των εκφράσεων που χρησιμοποιούνται στο πρόγραμμα.

συμπέρασμα

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

Τα δυαδικά δεδομένα δέντρων μπορούν επίσης να διασταυρωθούν χρησιμοποιώντας τεχνικές inorder, preorder και postorder traversal που έχουμε δει στο προηγούμενο σεμινάριό μας. Στη μνήμη, ένα δυαδικό δέντρο μπορεί να αναπαρασταθεί χρησιμοποιώντας μια συνδεδεμένη λίστα (μη συνεχόμενη μνήμη) ή πίνακες (διαδοχική αναπαράσταση).

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

=> Δείτε τα καλύτερα εκπαιδευτικά σεμινάρια C ++ εδώ.

τύπος δοκιμών στη μηχανική λογισμικού

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

^