Condivisione della tecnologia

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

1. Concetto e struttura di albero

1.1 Il concetto di albero

l'albero è unnon lineare Una struttura dati, che è un insieme di relazioni gerarchiche composte da n (n>=0) nodi limitati.FascioSi chiama albero perché sembra un albero capovolto, cioè con le radici rivolte verso l'alto e le foglie rivolte verso il basso.

• Nodo radice: il nodo radice non ha un nodo predecessore.
• Ad eccezione del nodo radice, i restanti nodi sono suddivisi in sottoalberi con 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.
• Pertanto, l'albero èdefinizione ricorsivaDi.

1.2 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 è 4;
• Nodo foglia o nodo terminale: I nodi con grado 0 sono chiamati nodi foglia; Come mostrato nella figura sopra: I nodi B, F, G, D e H sono nodi foglia.
• Nodo non terminale o nodo ramo: Un nodo il cui grado non è 0; Come mostrato nella figura sopra: i nodi A, C ed E 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 è 4;
• Livello del nodo: A partire dalla definizione della radice, la radice è il 1° livello, i nodi figli della radice sono il 2° livello e così via;
• altezza o profondità dell'albero: Il livello massimo di nodi nell'albero; come mostrato sopra: l'altezza dell'albero è 3
• nodo cugino: I nodi i cui genitori sono sullo stesso livello sono cugini tra loro come mostrato nella figura sopra: F e G 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 alberi disgiunti è detto foresta;

1.3 Rappresentazione dell'albero

La struttura ad albero è più complicata della tabella lineare ed è più problematica memorizzarla e rappresentarla.È necessario salvare sia l'intervallo di valori che la relazione tra nodi e nodi., infatti, esistono molti modi per rappresentare gli alberi, come ad esempio:Notazione genitore, notazione figlio, notazione genitore figlio e notazione fratello figlioAspettare.

Nel processo di introduzione della seguente struttura di archiviazione, prendiamo come esempio il seguente albero.

1.3.1 Rappresentanza dei genitori

Assumiamo che i nodi dell'albero siano memorizzati in un insieme di spazi continui e allo stesso tempoIn ciascun nodo è collegato un indicatore per indicare la posizione del nodo principale nell'elenco collegato. . In altre parole, oltre a sapere chi è, ogni nodo sa anche dove si trovano i suoi genitori.

Tra questi, data è il campo dati, che memorizza le informazioni sui dati del nodo. E parent è un campo puntatore che memorizza gli indici dei genitori del nodo nell'array.
Quello che segue è il codice di definizione della struttura del nodo per la nostra rappresentazione principale.

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
	TElemType data;	//结点数据
	int parent;	//双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
	TreeNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Con una tale struttura di archiviazione, possiamo facilmente trovare i suoi nodi genitori in base al puntatore genitore del nodo The utilizzatoLa complessità temporale è 0(1) , finché il genitore diventa -1, indicando che la radice del nodo dell'albero è stata trovata. Ma se vogliamo sapere quali sono i figli del nodo, scusate, attraversate l'intera struttura.

1.3.2 Rappresentanza dei fratelli minori

Proprio ora abbiamo studiato la struttura di archiviazione dell'albero dal punto di vista dei genitori e dal punto di vista del bambino. E se guardassimo i fratelli dei nodi dell'albero Naturalmente, per una struttura gerarchica come un albero, studiamo solo i nodi fratelli dei nodi. Non è possibile. Dopo l'osservazione, abbiamo scoperto che per ogni albero, il primo figlio del suo nodo è unico se esiste, e anche il suo fratello destro è unico se esiste. Pertanto, impostiamo due puntatori, che puntano al primo figlio del nodo e al fratello destro del nodo.

/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
	TElemtype data;
	struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
1
2
3
4
5
6

1.4 Applicazioni pratiche degli alberi

2. Concetto e struttura di albero binario

2.1 Concetto

Un albero binario è un insieme finito di nodi, che è:

• o vuoto
• È costituito da un nodo radice più due alberi binari, noti anche come sottoalbero sinistro e sottoalbero destro.

Come si può vedere dall'immagine qui sopra:

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 èalbero ordinato

Nota: qualsiasi albero binario è composto dalle seguenti situazioni:

2.2 Alberi binari speciali

1. albero binario completo: un albero binario,Se il numero di nodi in ogni strato raggiunge il massimo, l'albero binario è un albero binario completo. . Vale a dire, se il numero di livelli di un albero binario è K e il numero totale di nodi è 2^k-1, allora è un albero binario completo.
2. albero binario completo: Un albero binario completo è una struttura dati molto efficiente.Gli alberi binari completi derivano da alberi binari completi . Un albero binario con n nodi di profondità K è detto albero binario completo se e solo se ciascun nodo corrisponde biunivocamente ai nodi numerati da 1 a n nell'albero binario completo di profondità K. A cui prestare attenzioneUn albero binario completo è un tipo speciale di albero binario completo.
   

2.3 Proprietà degli alberi binari

1. Se il numero di livelli del nodo radice specificato è 1, allora il fileCi sono al massimo 2^(i-1) sullo strato i-esimo nodi
2. Se il numero di livelli del nodo radice è specificato su 1, alloraIl numero massimo di nodi di un albero binario con profondità h è 2^h-1
3. Per qualsiasi albero binario, seIl numero di nodi foglia di grado 0 è n0, e il numero di nodi foglia di grado 2 è n2, quindi n0=n2 +1
4. Se il numero di livelli del nodo radice è specificato su 1,La profondità di un albero binario completo con n nodi, h=log (n+1) (ps: log è in base 2, n+1 è logaritmo)
5. Per un albero binario completo con n nodi, se tutti i nodi sono numerati a partire da 0 in ordine di matrice dall'alto al basso, da sinistra a destra, allora per il nodo con numero di serie i:
   • Se i>0, il numero genitore del nodo nella posizione i: (i-1)/2; i=0, i è il numero del nodo radice, non esiste un nodo genitore
   • Se 2i+1, 2i+1>=n altrimenti non c'è il figlio sinistro
   • Se 2i+2, 2i+2>=n altrimenti non esiste il figlio destro

2.4 Struttura di memorizzazione dell'albero binario

Gli alberi binari possono generalmente essere memorizzati utilizzando due strutture:Una struttura sequenziale, una struttura a catena.

1. memorizzazione sequenziale
   È necessario utilizzare l'archiviazione della struttura sequenzialevettorePer archiviare, generalmente utilizzare un arrayAdatto solo per rappresentare alberi binari completi , perché non è un albero binario completo e ci sarebbe uno spreco di spazio. In realtà, solo l'heap utilizza gli array per l'archiviazione.La memorizzazione sequenziale degli alberi binari è fisicamente un array e logicamente un albero binario.
   2. Stoccaggio a catena
   La struttura di archiviazione collegata di un albero binario si riferisce a,Utilizzare un elenco collegato per rappresentare un albero binario , cioè utilizzare catene 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 trova il figlio sinistro e si trovano rispettivamente il figlio destro del nodo. **Le strutture di catena sono divise in catene binarie e catene triforcate Attualmente studiamo generalmente le catene binarie.
   

3. Struttura sequenziale e implementazione dell'albero binario

Gli alberi binari ordinari non sono adatti per l'archiviazione in array perché potrebbe esserci molto spazio sprecato.EGli alberi binari completi sono più adatti per l'archiviazione di strutture sequenziali .In realtà, di solitoUn heap (un albero binario) utilizza una serie di strutture sequenziali da archiviare, va notato che l'heap qui e l'heap nello spazio degli indirizzi del processo virtuale del sistema operativo sono due cose diverse Una è una struttura dati e l'altra è una segmentazione dell'area che gestisce la memoria nel sistema operativo.
Per implementazioni e applicazioni specifiche, consultare:[Struttura dei dati] 08. Heap e applicazioni heap

4. Struttura a catena dell'albero binario e sua implementazione

4.1 Attraversamento dell'albero binario

Il modo più semplice per apprendere una struttura ad albero binario è attraversarlo.cosiddettoL'attraversamento dell'albero binario (Traversal) consiste nell'eseguire operazioni corrispondenti sui nodi dell'albero binario in sequenza secondo determinate regole e ciascun nodo viene utilizzato solo una volta . Le operazioni eseguite accedendo ai nodi dipendono dal problema specifico dell'applicazione. L'attraversamento è una delle operazioni più importanti su un albero binario ed è anche la base per altre operazioni su un albero binario.

4.1.1 Attraversamento del preordine

//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

La figura seguente mostra il processo ricorsivo:

4.1.2 Attraversamento in ordine

//左子树 根 右子树
void InOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Quello che segue è il processo ricorsivo:

4.1.3 Attraversamento postordine

//左子树 右子树 根
void PostOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Quello che segue è il processo ricorsivo:

4.2.4 Attraversamento dell'ordine di livello

Attraversamento dell'ordine di livello: oltre all'attraversamento dell'ordine di preordine, dell'attraversamento in ordine e dell'attraversamento post-ordine, l'attraversamento dell'ordine di livello può essere eseguito anche su alberi binari. Supponiamo che il numero di livello del nodo radice dell'albero binario sia 1. L'attraversamento dell'ordine dei livelli inizia dal nodo radice dell'albero binario, prima visita il nodo radice del primo livello, quindi visita i nodi del secondo livello da sinistra a destra, quindi il terzo livello I nodi del livello e così via.Il processo di visita dei nodi dell'albero strato per strato dall'alto verso il basso e da sinistra a destra è l'attraversamento dell'ordine dei livelli.。
Illustrazione:

Qui interveniamo nella coda per eseguire l'attraversamento in preordine dell'albero binario.

// 层序遍历
void LevelOrder(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			printf("NULL ");
		}
		else
		{
			printf("%d ", front->val);
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.1 Creazione e distruzione di alberi binari

Per creare e distruggere un albero binario, usiamoAttraversamento dell'albero binarioPer esempio.

//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{ 
    if(*i<n&&arr[*i]=='#')
    {
        (*i)++;
        return NULL;
    }
    
    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
    newnode->left=NULL;
    newnode->right=NULL;

    newnode->val=arr[(*i)++];
    newnode->left=Creat(arr,n,i);
    newnode->right=Creat(arr,n,i);
    
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    TreeDestroy(root->left);
    TreeDestroy(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11

4.3 Altre operazioni sugli alberi binari

Le seguenti operazioni vengono tutte eseguite secondo l'idea di attraversamento.

// 二叉树节点个数
int TreeSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8
9

// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{

	if (root == NULL)
	{
		return NULL;
	}
	//相等就返回
	if (root->val == x)
		return root;
	//找左子树
	pTreeNode left=TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//找右子树
	pTreeNode right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//都没找到
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//二叉树的高度
int TreeHeight(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	int max_left = TreeHeight(root->left) ;
	int max_right = TreeHeight(root->right);
	return max_left > max_right ? max_left + 1 : max_right + 1;
}
1
2
3
4
5
6
7
8
9
10
11

//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36