Quelle est la structure de stockage liée d’un arbre binaire ?

La structure de stockage liée d'un arbre binaire fait référence à l'utilisation d'une liste chaînée pour représenter un arbre binaire, c'est-à-dire à l'utilisation d'une liste chaînée pour indiquer la relation logique entre les éléments. La structure de stockage liée d'un arbre binaire a généralement deux formes de stockage : une liste chaînée binaire et une liste chaînée triplet.

L'environnement d'exploitation de ce tutoriel : système Windows 7, version c99, ordinateur Dell G3.

La structure de stockage liée d'un arbre binaire utilise une liste chaînée pour représenter un arbre binaire, c'est-à-dire qu'une liste chaînée est utilisée pour indiquer la relation logique entre les éléments. Il existe généralement deux formulaires de stockage :

• Chaque nœud de la liste chaînée se compose de trois champs en plus du champ de données, il existe également deux champs de pointeur, qui sont utilisés pour donner l'enfant gauche et l'enfant droit du nœud. respectivement. L'adresse de stockage où il se trouve.

• Chaque nœud de la liste chaînée se compose de quatre champs En plus du champ de données, il existe également trois champs de pointeur, qui sont utilisés pour donner les adresses de stockage de l'enfant gauche, de l'enfant droit et du nœud parent.

La structure de stockage chaînée d'un arbre binaire (explication détaillée en langage C)

Figure 1 Diagramme schématique d'un arbre binaire ordinaire

Comme le montre la figure 1, il s'agit d'un arbre binaire ordinaire S'il est chaîné Pour stocker, il vous suffit de partir du nœud racine de l'arborescence et de stocker chaque nœud et ses enfants gauche et droit dans une liste chaînée. Par conséquent, la structure de stockage en chaîne correspondant à la figure 1 est représentée sur la figure 2 :

Figure 2 Diagramme schématique de la structure de stockage en chaîne d'un arbre binaire

Comme le montre la figure 2, lorsque le stockage en chaîne d'arbres binaires est utilisé, la structure de nœuds se compose de trois parties (comme le montre la figure 3) :

• Pointeur vers le nœud enfant gauche (Lchild) ;

• Données stockées dans le nœud (data);

• Pointeur vers le nœud enfant droit (Rchild);

Figure 3 Structure de nœud d'arbre binaire

Le code en langage C représentant la structure de nœud est :

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

Le code en langage C correspondant à la structure de stockage en chaîne dans la figure 2 est :

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}

Résultat de sortie du programme :

4

En fait, le chaîne de l'arbre binaire Il existe beaucoup plus de structures de stockage que celle illustrée à la figure 2. Par exemple, dans certains scénarios réels, l'opération de « recherche du nœud parent d'un nœud » peut être effectuée. Dans ce cas, un champ de pointeur peut être ajouté à la structure de nœud pour que chaque nœud pointe vers son nœud parent, comme indiqué. dans la figure 4. :

Figure 4 La structure de stockage liée d'un arbre binaire personnalisé

Une telle structure de liste chaînée est généralement appelée liste chaînée ternaire.

En utilisant la liste chaînée à trois volets présentée dans la figure 4, nous pouvons facilement trouver le nœud parent de chaque nœud. Par conséquent, lors de la résolution de problèmes pratiques, l’utilisation d’une structure de liste chaînée appropriée pour stocker les arbres binaires peut obtenir deux fois le résultat avec la moitié de l’effort.

Recommandations associées : "Tutoriel vidéo sur le langage C"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!