Partage de technologie

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

Cet article commencera par les concepts liés aux arbres et aux arbres binaires pour nous aider à en apprendre davantage sur les arbres binaires.

🌈个人主页：C'est le serveur
🌈C语言笔记专栏：Notes en langage C
🌈C++笔记专栏： Remarques C++
🌈初阶数据结构笔记专栏： Notes sur la structure des données élémentaires

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

1. Concept et structure de l'arborescence

L'arbre est une structure de données non linéaire, composée den(n>=0)Les nœuds limités forment un ensemble avec une relation hiérarchique. Cependant, l'arbre a peu de valeur en pratique, mais l'arbre binaire a une plus grande valeur pratique (la raison pour laquelle cet ensemble est appelé arbre est qu'il a la racine tournée vers le haut et les feuilles). face vers le bas. Cela ressemble beaucoup à un arbre)

• Il existe un nœud spécial appelé nœud racine. Le nœud racine n'a pas de nœud prédécesseur.
• À l'exception du nœud racine, les nœuds restants sont divisés enM(M>0)ensembles disjointsT1、T2、....、Tm, dont chaque ensembleTi(1<=i<=m) C'est un autre sous-arbre avec une structure similaire à celle d'un arbre. Le nœud racine de chaque sous-arbre a un et un seul prédécesseur et peut avoir 0 ou plusieurs successeurs.
• Les arbres sont définis de manière récursive et, en même temps, des précautions doivent être prises.dans l'arborescenceIl ne peut pas y avoir d'intersection entre les sous-arbres, sinon ce ne sera pas une structure arborescente

1.1 Concepts associés aux arbres

• Degré de nœud: Le nombre de sous-arbres contenus dans un nœud est appelé le degré du nœud comme le montre la figure ci-dessus : A vaut 6 ;
• Nœud feuille ou nœud terminal: Les nœuds de degré 0 sont appelés nœuds feuilles ; comme le montre la figure ci-dessus : Les nœuds tels que B, C, H, I... sont des nœuds feuilles.
• Nœud non terminal ou nœud de branche: Un nœud dont le degré n'est pas 0 ; Comme le montre la figure ci-dessus : les nœuds tels que D, E, F, G... sont des nœuds de branche.
• Nœud parent ou nœud parent: Si un nœud contient des nœuds enfants, alors ce nœud est appelé le nœud parent de son nœud enfant. Comme le montre la figure ci-dessus : A est le nœud parent de B ;
• nœud enfant ou nœud enfant: Le nœud racine du sous-arbre contenu par un nœud est appelé nœud enfant du nœud. Comme le montre la figure ci-dessus : B est le nœud enfant de A ;
• Nœud frère: Les nœuds avec le même nœud parent sont appelés nœuds frères, comme indiqué ci-dessus : B et C sont des nœuds frères.
• degré d'arbre: Dans un arbre, le degré du plus grand nœud est appelé degré de l'arbre comme indiqué ci-dessus : le degré de l'arbre est 6 ;
• Niveau du nœud: A partir de la définition de la racine, la racine est le premier niveau, les nœuds enfants de la racine sont le deuxième niveau, et ainsi de suite.
• hauteur ou profondeur de l'arbre: Le niveau maximum de nœuds dans l'arborescence comme indiqué ci-dessus : la hauteur de l'arborescence est de 4 ;
• noeud cousin: Les nœuds dont les parents sont au même niveau sont cousins ​​l'un de l'autre ; comme le montre la figure ci-dessus : H et I sont des nœuds frères l'un de l'autre.
• Ancêtre du nœud: Tous les nœuds sur les branches de la racine au nœud comme le montre la figure ci-dessus : A est l'ancêtre de tous les nœuds ;
• descendance : Tout nœud du sous-arbre enraciné à un certain nœud est appelé descendant de ce nœud.Comme indiqué ci-dessus : tous les nœuds sont des descendants de A
• forêt: Un ensemble de m (m>0) arbres disjoints est appelé une forêt.

2. Représentation de stockage de l'arbre

La structure arborescente étant plus complexe que le tableau linéaire, la méthode de stockage est plus lourde. Il est nécessaire de sauvegarder à la fois la plage de valeurs et la relation entre les nœuds.

Voici plusieurs méthodes basées sur des connaissances antérieures :

• Chaque enfant a une adresse et peut stocker des données via un tableau de pointeurs (l'espace est fixe et il y a des coûts et des problèmes d'espace lors de la demande d'un nouvel espace)
• Pour l'optimisation de la première méthode, le tableau de pointeurs est utilisé comme table de séquence pour stocker les enfants, ce qui résout le problème de l'espace fixe.
• Solution couramment utilisée recommandée : méthode de l'enfant gauche et du frère droit (le frère aîné prend le deuxième enfant et le deuxième enfant prend le troisième enfant, donc les deux parents n'ont pas besoin d'être fatigués)

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

Bien sûr, les méthodes ci-dessus ne sont pas limitées, et il existe également des expressions parent, des expressions enfant, des expressions parent enfant et des expressions frère enfant, etc.Ici, nous comprendrons brièvement les plus couramment utilisésreprésentation du frère enfant

3. Concept d'arbre binaire

Un arbre binaire est un ensemble fini de nœuds. Cet ensemble peut avoir deux situations :

1. arbre vide
2. Il se compose d'un nœud racine plus deux arbres binaires appelés sous-arbre gauche et sous-arbre droit (le sous-arbre peut être un arbre vide)

Deux conclusions peuvent être tirées de la figure:

1. Il n'y a aucun nœud de degré supérieur à 2 dans un arbre binaire

2. Les sous-arbres d'un arbre binaire peuvent être divisés en sous-arbres gauche et droit, et l'ordre ne peut pas être inversé, donc l'arbre binaire est un arbre ordonné.

Avis: Pour tout arbre binaire, il est composé des situations suivantes (La situation de l'arbre vide est la plus facile à oublier)

3.1 Arbre binaire dans la réalité (il faut s'incliner plusieurs fois quand on le voit)

4. Arbre binaire spécial

• arbre binaire complet :Un arbre binaire est un arbre binaire complet si le nombre de nœuds dans chaque couche atteint le maximum. En d’autres termes, le niveau d’un arbre binaire est K et le nombre total de nœuds est 2.^K-1, alors c'est un arbre binaire complet
• arbre binaire complet : Un arbre binaire complet est une structure de données très efficace. Un arbre binaire complet est dérivé d'un arbre binaire complet. Pour un arbre binaire de hauteur K et n nœuds, on parle d'arbre binaire complet si et seulement si chaque nœud correspond biunivoque aux nœuds numérotés de 1 à n dans l'arbre binaire complet de hauteur K.

Pour résumer brièvement:

• Chaque niveau d'un arbre binaire complet est plein

• Si la hauteur d'un arbre binaire complet est n, alors les n-1 premiers niveaux sont pleins, mais le dernier niveau peut ne pas être plein.Mais il faut que ce soit continu de gauche à droite

• Un arbre binaire complet est une structure de données très efficace, et un arbre binaire complet est un type particulier d'arbre binaire complet.

• Un arbre binaire complet est une condition nécessaire et suffisante pour un arbre binaire complet

4.1 Situations n'appartenant pas à un arbre binaire complet

Il s’agit d’un arbre binaire ordinaire, qui n’est pas continu de gauche à droite.

5. Structure de stockage de l'arbre binaire

Les arbres binaires peuvent généralement être stockés dans deux structures, l’une est une structure séquentielle et l’autre est une structure en chaîne.

5.1 Stockage séquentiel

Le stockage de structure séquentielle consiste à utiliser des tableaux pour stocker,Généralement, les tableaux ne conviennent que pour représenter des arbres binaires complets. , car si l'arborescence binaire n'est pas pleine, il y aura une perte d'espace. En réalité, seul le tas utilisera des tableaux pour le stockage. Le stockage séquentiel des arbres binaires est physiquement un tableau et logiquement un arbre binaire. Pour résoudre la question suivante, nous devons utiliser la combinaison physique d'un tableau et logiquement d'un arbre binaire pour résoudre une question.

5.2 La relation régulière des indices entre les nœuds parent et enfant (important)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Ne fait pas de différence entre les enfants de gauche et de droite)

• Concernant le troisième point, basé sur un raisonnement personnel,leftchildL'indice est divisé enleftchild- 1et1,pourleftchild-1pourparentindice deux fois, pour(child - 1) / 2L'opérateur valeftchildRetirez-le comme1Partiellement divisé par 2, l'entier est 0,leftchild -1Une partie peut être considérée commeleftchild,etrightchild与leftchild相差1,parce querightchild = leftchild - 1et par dessusleftchild - 1 ~= leftchild, on peut en déduire querightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Stockage en chaîne

La structure de stockage liée d'un arbre binaire signifie qu'une liste chaînée est utilisée pour représenter un arbre binaire, c'est-à-dire qu'une chaîne est utilisée pour indiquer la relation logique des éléments. La méthode habituelle est que chaque nœud de la liste chaînée se compose de trois champs, le champ de données et les champs de pointeur gauche et droit. Les pointeurs gauche et droit sont utilisés pour donner les adresses de stockage des points de liaison où se trouvent l'enfant gauche et l'enfant droit. du nœud sont situés respectivement.Les structures de chaîne sont divisées en chaînes binaires et chaînes trifurquées.À l'heure actuelle, nous utilisons généralement des chaînes binaires dans nos études. Plus tard, lorsque nous apprendrons les structures de données d'ordre élevé telles que les arbres rouge-noir, les chaînes trifurquées seront utilisées.

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 Résumé

Le stockage de structure séquentielle est stocké via des tableaux.Généralement, les tableaux ne conviennent qu'aux arbres binaires complets. Les arbres binaires non complets ne conviennent pas au stockage de structure de tableau. Les arbres binaires ordinaires ne conviennent qu'au stockage de structure de chaîne. . Mais en réalité, les tableaux ne sont utilisés pour le stockage que lorsque des tas sont utilisés, et la plupart d'entre eux sont stockés via des structures en chaîne.

la raison est:

1. Tout d'abord, nous devons savoir que l'arbre binaire a sa propre structure logique spéciale. Il est différent des autres structures de données et convient pour ajouter, supprimer, vérifier et modifier des données du tas, car l'espace ouvert consomme beaucoup d'espace et. la logique est plus complexe.Si une structure aussi complexe est utilisée pour stocker des données, elle n’est pas sans grande valeur. , il serait préférable d'utiliser un tableau séquentiel pour stocker les données depuis le début. Dans le même temps, d'une manière générale, la structure d'un arbre binaire est récursive et il est plus difficile de la mettre en œuvre de manière non récursive.
2. La densité des éléments de stockage dans un arbre binaire ordinaire peut être très faible et la structure de stockage continue entraînera un gaspillage important d'espace.
3. Le tas est trié selon "l'attribut tas", qui détermine la position du nœud dans l'arborescence (expliqué dans l'introduction du tas ci-dessous)

---

Ce qui précède représente tout le contenu de cet article. Merci à tous d’avoir lu ! Voici les notes de Dian Xiaoer sur les structures de données élémentaires. J'espère qu'elles vous seront utiles dans l'apprentissage des structures de données élémentaires !