Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

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

🌈个人主页：Είναι ο σερβιτόρος
🌈C语言笔记专栏：Γλώσσα Γ σημειώσεις
🌈C++笔记专栏： Σημειώσεις C++
🌈初阶数据结构笔记专栏： Σημειώσεις στοιχειωδών δομών δεδομένων

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. Έννοια και δομή δέντρου

Το δέντρο είναι μια μη γραμμική δομή δεδομένων, η οποία αποτελείται απόn(n>=0)Οι περιορισμένοι κόμβοι σχηματίζουν ένα σύνολο με ιεραρχική σχέση Ωστόσο, το δέντρο έχει μικρή αξία στην πράξη, αλλά το δυαδικό δέντρο έχει μεγαλύτερη πρακτική αξία (ο λόγος για τον οποίο αυτό το σύνολο ονομάζεται δέντρο είναι ότι έχει τη ρίζα προς τα πάνω και τα φύλλα. στραμμένο προς τα κάτω Μοιάζει πολύ με δέντρο)

• Υπάρχει ένας ειδικός κόμβος που ονομάζεται ριζικός κόμβος.
• Εκτός από τον ριζικό κόμβο, οι υπόλοιποι κόμβοι χωρίζονται σεM(M>0)ασύνδετα σύνολαT1、T2、....、Tm, κάθε σετ των οποίωνTi(1<=i<=m) Είναι ένα άλλο υποδέντρο με δομή παρόμοια με αυτή ενός δέντρου. Ο ριζικός κόμβος κάθε υποδέντρου έχει έναν και μόνο έναν προκάτοχο και μπορεί να έχει 0 ή περισσότερους διαδόχους.
• Τα δέντρα ορίζονται αναδρομικά και ταυτόχρονα χρειάζεται προσοχή.σε δομή δέντρουΔεν μπορεί να υπάρξει τομή μεταξύ υποδέντρων, διαφορετικά δεν θα είναι δομή δέντρου

1.1 Σχετικές έννοιες των δέντρων

• Βαθμός κόμβου: Ο αριθμός των υποδέντρων που περιέχονται σε έναν κόμβο ονομάζεται βαθμός του κόμβου όπως φαίνεται στο παραπάνω σχήμα: Το Α είναι 6
• Κόμβος φύλλων ή τερματικός κόμβος: Οι κόμβοι με βαθμό 0 ονομάζονται κόμβοι φύλλων Όπως φαίνεται στο παραπάνω σχήμα: Κόμβοι όπως B, C, H, I... είναι κόμβοι φύλλων.
• Μη τερματικός κόμβος ή κόμβος διακλάδωσης: Ένας κόμβος του οποίου ο βαθμός δεν είναι 0 Όπως φαίνεται στο παραπάνω σχήμα: κόμβοι όπως D, E, F, G... είναι κόμβοι διακλάδωσης.
• Γονικός κόμβος ή γονικός κόμβος: Εάν ένας κόμβος περιέχει θυγατρικούς κόμβους, τότε αυτός ο κόμβος ονομάζεται γονικός κόμβος του θυγατρικού του κόμβου
• θυγατρικός κόμβος ή θυγατρικός κόμβος: Ο ριζικός κόμβος του υποδέντρου που περιέχεται από έναν κόμβο ονομάζεται θυγατρικός κόμβος του κόμβου
• Αδελφικός κόμβος: Οι κόμβοι με τον ίδιο μητρικό κόμβο ονομάζονται αδελφικοί κόμβοι όπως φαίνεται παραπάνω: Ο Β και ο Γ είναι κόμβοι αδελφοί.
• βαθμός δέντρου: Σε ένα δέντρο, ο βαθμός του μεγαλύτερου κόμβου ονομάζεται βαθμός του δέντρου όπως φαίνεται παραπάνω: ο βαθμός του δέντρου είναι 6
• Επίπεδο κόμβου: Ξεκινώντας από τον ορισμό της ρίζας, η ρίζα είναι το πρώτο επίπεδο, οι θυγατρικοί κόμβοι της ρίζας είναι το δεύτερο επίπεδο κ.ο.κ.
• ύψος ή βάθος δέντρου: Το μέγιστο επίπεδο κόμβων στο δέντρο όπως φαίνεται παραπάνω: το ύψος του δέντρου είναι 4
• κόμβος εξάδελφος: Οι κόμβοι των οποίων οι γονείς βρίσκονται στο ίδιο επίπεδο είναι ξαδέλφια ο ένας του άλλου όπως φαίνεται στο παραπάνω σχήμα: Το H και το I είναι αδελφοί κόμβοι ο ένας του άλλου.
• Πρόγονος του κόμβου: Όλοι οι κόμβοι στα κλαδιά από τη ρίζα στον κόμβο όπως φαίνεται στο παραπάνω σχήμα: Ο A είναι ο πρόγονος όλων των κόμβων
• απόγονοι : Κάθε κόμβος στο υποδέντρο που έχει ρίζες σε έναν συγκεκριμένο κόμβο ονομάζεται απόγονος αυτού του κόμβου.Όπως φαίνεται παραπάνω: όλοι οι κόμβοι είναι απόγονοι του Α
• δάσος: Ένα σύνολο m (m>0) ασύνδετων δέντρων ονομάζεται δάσος.

2. Αποθηκευτική αναπαράσταση δέντρου

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

Ακολουθούν διάφορες μέθοδοι που βασίζονται σε προηγούμενες γνώσεις:

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

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

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

3. Έννοια δυαδικού δέντρου

Ένα δυαδικό δέντρο είναι ένα πεπερασμένο σύνολο κόμβων Αυτό το σύνολο μπορεί να έχει δύο καταστάσεις:

1. άδειο δέντρο
2. Αποτελείται από έναν ριζικό κόμβο συν δύο δυαδικά δέντρα που ονομάζονται αριστερό υποδέντρο και δεξί υποδέντρο (το υποδέντρο μπορεί να είναι ένα κενό δέντρο)

Από το σχήμα μπορούν να εξαχθούν δύο συμπεράσματα:

1. Δεν υπάρχει κόμβος με βαθμό μεγαλύτερο από 2 σε ένα δυαδικό δέντρο

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

Ειδοποίηση: Για κάθε δυαδικό δέντρο, αποτελείται από τις ακόλουθες καταστάσεις (Το άδειο δέντρο είναι πιο εύκολο να ξεχαστεί)

3.1 Δυαδικό δέντρο στην πραγματικότητα (πρέπει να υποκλιθείτε πολλές φορές όταν το δείτε)

4. Ειδικό δυαδικό δέντρο

• πλήρες δυαδικό δέντρο :Ένα δυαδικό δέντρο είναι ένα πλήρες δυαδικό δέντρο εάν ο αριθμός των κόμβων σε κάθε επίπεδο φτάσει το μέγιστο. Με άλλα λόγια, το επίπεδο ενός δυαδικού δέντρου είναι Κ και ο συνολικός αριθμός κόμβων είναι 2^κ-1, τότε είναι ένα πλήρες δυαδικό δέντρο
• πλήρες δυαδικό δέντρο : Ένα πλήρες δυαδικό δέντρο είναι μια πολύ αποτελεσματική δομή δεδομένων Ένα πλήρες δυαδικό δέντρο προέρχεται από ένα πλήρες δυαδικό δέντρο. Για ένα δυαδικό δέντρο με ύψος K και n κόμβους, ονομάζεται πλήρες δυαδικό δέντρο εάν και μόνο εάν κάθε κόμβος αντιστοιχεί ένα προς ένα με τους κόμβους που αριθμούνται από το 1 έως το n στο πλήρες δυαδικό δέντρο με ύψος K.

Για να συνοψίσουμε εν συντομία:

• Κάθε επίπεδο ενός πλήρους δυαδικού δέντρου είναι γεμάτο

• Εάν το ύψος ενός πλήρους δυαδικού δέντρου είναι n, τότε τα πρώτα n-1 επίπεδα είναι γεμάτα, αλλά το τελευταίο επίπεδο μπορεί να μην είναι πλήρες.Πρέπει όμως να είναι συνεχής από αριστερά προς τα δεξιά

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

• Ένα πλήρες δυαδικό δέντρο είναι απαραίτητη και επαρκής προϋπόθεση για ένα πλήρες δυαδικό δέντρο

4.1 Καταστάσεις που δεν ανήκουν σε ένα πλήρες δυαδικό δέντρο

Αυτό είναι ένα συνηθισμένο δυαδικό δέντρο, το οποίο δεν είναι συνεχές από αριστερά προς τα δεξιά.

5. Δομή αποθήκευσης δυαδικού δέντρου

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

5.1 Διαδοχική αποθήκευση

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

5.2 Τακτική σχέση συνδρομής μεταξύ γονικών και θυγατρικών κόμβων (σημαντικό)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Δεν κάνει διάκριση μεταξύ αριστερών και δεξιών παιδιών)

• Όσον αφορά το τρίτο σημείο, βάσει προσωπικού συλλογισμού,leftchildΟ δείκτης χωρίζεται σεleftchild- 1και1,Γιαleftchild-1Γιαparentεγγραφείτε δύο φορές, για(child - 1) / 2Ο χειριστής θαleftchildΒγάλτε το ως1Μερικώς διαιρούμενο με το 2, ο ακέραιος αριθμός είναι 0,leftchild -1Μέρος του μπορεί να θεωρηθεί ωςleftchild,καιrightchild与leftchild相差1,επειδήrightchild = leftchild - 1και από τα παραπάνωleftchild - 1 ~= leftchild, μπορεί να συναχθεί ότιrightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Αποθήκευση αλυσίδας

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

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 Περίληψη

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

ο λόγος είναι:

1. Πρώτα απ 'όλα, πρέπει να γνωρίζουμε ότι το δυαδικό δέντρο έχει τη δική του ειδική λογική δομή. Διαφέρει από άλλες δομές δεδομένων και είναι κατάλληλο για προσθήκη, διαγραφή, έλεγχο και τροποποίηση δεδομένων σωρού, επειδή καταναλώνει πολύ χώρο και τη λογική. είναι πιο σύνθετη.Εάν μια τόσο πολύπλοκη δομή χρησιμοποιείται για την αποθήκευση δεδομένων, δεν είναι χωρίς μεγάλη αξία. , θα ήταν καλύτερο να χρησιμοποιήσετε έναν διαδοχικό πίνακα για την αποθήκευση δεδομένων από την αρχή. Ταυτόχρονα, σε γενικές γραμμές, η δομή ενός δυαδικού δέντρου είναι αναδρομική και είναι πιο ενοχλητικό να το εφαρμόσουμε μη αναδρομικά.
2. Η πυκνότητα των στοιχείων αποθήκευσης σε ένα συνηθισμένο δυαδικό δέντρο μπορεί να είναι πολύ χαμηλή και η συνεχής δομή αποθήκευσης θα προκαλέσει μεγάλη σπατάλη χώρου.
3. Ο σωρός ταξινομείται σύμφωνα με την "ιδιότητα heap", η οποία καθορίζει τη θέση του κόμβου στο δέντρο (εξηγείται στην εισαγωγή του σωρού παρακάτω)

---

Το παραπάνω είναι όλο το περιεχόμενο αυτού του άρθρου Σας ευχαριστούμε όλους για την ανάγνωση! Εδώ είναι οι σημειώσεις του Dian Xiaoer για τις στοιχειώδεις δομές δεδομένων.