Condivisione della tecnologia

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

Questo articolo inizierà con i concetti relativi agli alberi e agli alberi binari per aiutarci a conoscere meglio gli alberi binari.

🌈个人主页：E' il cameriere
🌈C语言笔记专栏：Appunti sul linguaggio C
🌈C++笔记专栏： Note sul C++
🌈初阶数据结构笔记专栏： Cenni elementari sulla struttura dei dati

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

1. Concetto e struttura dell'albero

L'albero è una struttura dati non lineare, composta dan(n>=0)I nodi limitati formano un insieme con una relazione gerarchica. Tuttavia, l'albero ha poco valore nella pratica, ma l'albero binario ha un valore pratico maggiore (il motivo per cui questo insieme è chiamato albero è che ha la radice rivolta verso l'alto e le foglie. rivolto verso il basso. Sembra molto simile a un albero)

• Esiste un nodo speciale chiamato nodo radice. Il nodo radice non ha nodi predecessori.
• Ad eccezione del nodo radice, i restanti nodi sono suddivisi inM(M>0)insiemi disgiuntiT1、T2、....、Tm, ciascun set dei qualiTi(1<=i<=m) È un altro sottoalbero con una struttura simile a quella di un albero. Il nodo radice di ogni sottoalbero ha uno ed un solo predecessore e può avere 0 o più successori.
• Gli alberi sono definiti in modo ricorsivo e allo stesso tempo è necessario prestare attenzione.nella struttura ad alberoNon può esserci intersezione tra sottoalberi, altrimenti non sarà una struttura ad albero

1.1 Concetti correlati agli alberi

• Grado del nodo: Il numero di sottoalberi contenuti in un nodo è chiamato grado del nodo come mostrato nella figura sopra: A è 6
• Nodo foglia o nodo terminale: I nodi con grado 0 sono chiamati nodi foglia; Come mostrato nella figura sopra: Nodi come B, C, H, I... sono nodi foglia.
• Nodo non terminale o nodo ramo: Un nodo il cui grado non è 0; Come mostrato nella figura sopra: i nodi come D, E, F, G... sono nodi di diramazione.
• Nodo genitore o nodo genitore: Se un nodo contiene nodi figli, allora questo nodo è chiamato nodo genitore del suo nodo figlio. Come mostrato nella figura sopra: A è il nodo genitore di B
• nodo figlio o nodo figlio: Il nodo radice del sottoalbero contenuto da un nodo è chiamato nodo figlio del nodo; Come mostrato nella figura sopra: B è il nodo figlio di A
• Nodo fratello: I nodi con lo stesso nodo genitore sono chiamati nodi fratelli come mostrato sopra: B e C sono nodi fratelli.
• grado dell'albero: In un albero, il grado del nodo più grande è chiamato grado dell'albero come mostrato sopra: il grado dell'albero è 6;
• Livello del nodo: Partendo dalla definizione della radice, la radice è il primo livello, i nodi figli della radice sono il secondo livello e così via.
• altezza o profondità dell'albero: Il livello massimo di nodi nell'albero; come mostrato sopra: l'altezza dell'albero è 4
• nodo cugino: I nodi i cui genitori sono sullo stesso livello sono cugini tra loro come mostrato nella figura sopra: H e I sono nodi fratelli l'uno dell'altro;
• Antenato del nodo: Tutti i nodi sui rami dalla radice al nodo; come mostrato nella figura sopra: A è l'antenato di tutti i nodi
• discendenti : Qualsiasi nodo nel sottoalbero radicato in un determinato nodo è chiamato discendente di quel nodo.Come mostrato sopra: tutti i nodi sono discendenti di A
• foresta: Un insieme di m (m>0) alberi disgiunti è detto foresta.

2. Rappresentazione dell'immagazzinamento dell'albero

Poiché la struttura ad albero è più complessa della tabella lineare, il metodo di memorizzazione è più macchinoso. È necessario salvare sia l'intervallo di valori che la relazione tra i nodi.

Ecco diversi metodi basati sulle conoscenze precedenti:

• Ogni bambino ha un indirizzo e può memorizzare dati tramite un array di puntatori (lo spazio è fisso e ci sono costi e problemi di spazio quando si richiede nuovo spazio)
• Per l'ottimizzazione del primo metodo, l'array di puntatori viene utilizzato come tabella di sequenza per memorizzare i figli, risolvendo il problema dello spazio fisso.
• Soluzione comunemente consigliata: metodo del figlio sinistro e del fratello destro (il fratello maggiore prende il secondo figlio e il secondo figlio prende il terzo figlio, quindi entrambi i genitori non devono essere stanchi)

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

Naturalmente, i metodi di cui sopra non sono limitati e ci sono anche espressioni genitore, espressioni figlio, espressioni genitore figlio ed espressioni fratello figlio, ecc.Qui comprenderemo brevemente quelli più comunemente utilizzatirappresentanza del fratello minore

3. Concetto di albero binario

Un albero binario è un insieme finito di nodi. Questo insieme può avere due situazioni:

1. albero vuoto
2. È costituito da un nodo radice più due alberi binari chiamati sottoalbero sinistro e sottoalbero destro (il sottoalbero può essere un albero vuoto)

Dalla figura si possono trarre due conclusioni:

1. In un albero binario non esistono nodi con grado maggiore di 2

2. I sottoalberi di un albero binario possono essere divisi in sottoalberi sinistro e destro e l'ordine non può essere invertito, quindi l'albero binario è un albero ordinato.

Avviso: Per qualsiasi albero binario, è composto dalle seguenti situazioni (La situazione dell’albero vuoto è più facile da dimenticare)

3.1 Albero binario nella realtà (devi inchinarti più volte quando lo vedi)

4. Albero binario speciale

• albero binario completo :Un albero binario è un albero binario completo se il numero di nodi in ogni strato raggiunge il massimo. In altre parole, il livello di un albero binario è K e il numero totale di nodi è 2^K-1, allora è un albero binario completo
• albero binario completo : Un albero binario completo è una struttura dati molto efficiente. Un albero binario completo è derivato da un albero binario completo. Per un albero binario con altezza K e n nodi, è detto albero binario completo se e solo se ciascun nodo corrisponde uno a uno con i nodi numerati da 1 a n nell'albero binario completo con altezza K.

Per riassumere brevemente:

• Ogni livello di un albero binario completo è pieno

• Se l'altezza di un albero binario completo è n, allora i primi n-1 livelli sono pieni, ma l'ultimo livello potrebbe non essere pieno.Ma deve essere continuo da sinistra a destra

• Un albero binario completo è una struttura dati molto efficiente e un albero binario completo è un tipo speciale di albero binario completo.

• Un albero binario completo è una condizione necessaria e sufficiente per un albero binario completo

4.1 Situazioni che non appartengono ad un albero binario completo

Questo è un albero binario ordinario, che non è continuo da sinistra a destra.

5. Struttura di memorizzazione dell'albero binario

Gli alberi binari possono generalmente essere memorizzati in due strutture, una è una struttura sequenziale e l'altra è una struttura a catena.

5.1 Archiviazione sequenziale

L'archiviazione della struttura sequenziale consiste nell'utilizzare gli array per archiviare,Generalmente gli array sono adatti solo per rappresentare alberi binari completi. , perché se l'albero binario non è pieno, ci sarà uno spreco di spazio. In realtà, solo l'heap utilizzerà gli array per l'archiviazione. La memorizzazione sequenziale di alberi binari è fisicamente un array e logicamente un albero binario. Per risolvere la domanda successiva, dobbiamo utilizzare la combinazione di un array fisico e di un albero binario logicamente.

5.2 La relazione regolare dei pedici tra nodi genitore e figlio (importante)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Non distingue tra bambini di destra e di sinistra)

• Per quanto riguarda il terzo punto, sulla base di un ragionamento personale,leftchildIl pedice è suddiviso inleftchild- 1E1,perleftchild-1perparentpedice due volte, per(child - 1) / 2L'operatore lo faràleftchildTiralo fuori come1Parzialmente diviso per 2, il numero intero è 0,leftchild -1Una parte di esso può essere vista comeleftchild,Erightchild与leftchild相差1,Perchérightchild = leftchild - 1e attraverso sopraleftchild - 1 ~= leftchild, si può dedurre cherightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Stoccaggio a catena

La struttura di archiviazione collegata di un albero binario significa che viene utilizzata una lista collegata per rappresentare un albero binario, ovvero viene utilizzata una catena per indicare la relazione logica degli elementi. Il metodo usuale prevede che ciascun nodo nell'elenco collegato sia costituito da tre campi, il campo dati e i campi del puntatore sinistro e destro. I puntatori sinistro e destro vengono utilizzati per fornire gli indirizzi di archiviazione dei punti di collegamento dove si trovano il figlio sinistro e il figlio destro del nodo si trovano rispettivamente.Le strutture a catena sono divise in catene binarie e catene triforcate. Al momento, nei nostri studi utilizziamo generalmente catene binarie. Successivamente, quando impareremo strutture di dati di ordine elevato come gli alberi rosso-neri, verranno utilizzate le catene triforcate.

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 Riepilogo

L'archiviazione della struttura sequenziale viene archiviata tramite array.In generale, gli array sono adatti solo per alberi binari completi. Gli alberi binari non completi non sono adatti per l'archiviazione di strutture di array. Gli alberi binari ordinari sono adatti solo per l'archiviazione di strutture a catena. . Ma in realtà, gli array vengono utilizzati per l'archiviazione solo quando vengono utilizzati gli heap e la maggior parte di essi viene archiviata tramite strutture a catena.

il motivo è:

1. Innanzitutto dobbiamo sapere che l'albero binario ha una sua struttura logica speciale, diversa dalle altre strutture dati ed è adatta per aggiungere, cancellare, controllare e modificare i dati dell'heap, perché lo spazio aperto consuma molto spazio e. la logica è più complessa.Se per archiviare i dati viene utilizzata una struttura così complessa, non è senza molto valore. , sarebbe meglio utilizzare una tabella sequenziale per memorizzare i dati dall'inizio. Allo stesso tempo, in generale, la struttura di un albero binario è ricorsiva ed è più problematica implementarla in modo non ricorsivo.
2. La densità degli elementi di memorizzazione in un albero binario ordinario può essere molto bassa e la struttura di memorizzazione continua causerà molto spreco di spazio.
3. L'heap è ordinato in base all'"attributo heap", che determina la posizione del nodo nell'albero (spiegato nell'introduzione dell'heap di seguito)

---

Quanto sopra è tutto il contenuto di questo articolo. Grazie a tutti per aver letto! Ecco gli appunti di Dian Xiaoer sulle strutture dati elementari. Spero che ti saranno utili per imparare le strutture dati elementari!