2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
l'arbre est unnon linéaire Une structure de données, qui est un ensemble de relations hiérarchiques composées de n (n>=0) nœuds limités.PaquetOn l'appelle un arbre parce qu'il ressemble à un arbre à l'envers, ce qui signifie qu'il a les racines pointées vers le haut et les feuilles pointées vers le bas.
- 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 en sous-arbres 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.
- L’arbre est doncdéfinition récursivede.
La structure arborescente est plus compliquée que le tableau linéaire, et il est plus difficile de la stocker et de la représenter.Il est nécessaire de sauvegarder à la fois la plage de valeurs et la relation entre les nœuds et les nœuds., en fait, il existe de nombreuses façons de représenter les arbres, telles que :Notation parent, notation enfant, notation parent enfant et notation frère enfantattendez.
Dans le processus d'introduction de la structure de stockage suivante, nous prenons l'arbre suivant comme exemple.
Nous supposons que les nœuds de l'arbre sont stockés dans un ensemble d'espaces continus, et en même tempsDans chaque nœud, un indicateur est attaché pour indiquer la position de son nœud parent dans la liste chaînée. . Autrement dit, en plus de savoir de qui il s’agit, chaque nœud sait également où se trouvent ses parents.
Parmi eux, data est le champ de données, qui stocke les informations de données du nœud. Et parent est un champ de pointeur qui stocke les indices des parents du nœud dans le tableau.
Ce qui suit est le code de définition de la structure des nœuds pour notre représentation parent.
/*树的双亲表示法结点结构定义*/
#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;
Avec une telle structure de stockage, on peut facilement retrouver ses nœuds parents en fonction du pointeur parent du nœud utilisé.La complexité temporelle est 0(1) , jusqu'à ce que parent soit -1, indiquant que la racine du nœud de l'arborescence a été trouvée. Mais si nous voulons savoir quels sont les enfants du nœud, désolé, veuillez parcourir toute la structure.
Nous venons d'étudier la structure de stockage de l'arbre du point de vue des parents et du point de vue de l'enfant. Et si nous regardions les frères des nœuds de l'arbre ? Bien sûr, pour une structure hiérarchique comme un arbre, nous étudions uniquement les frères ? frères des nœuds. Ce n'est pas possible. Après observation, nous avons constaté que pour tout arbre, le premier enfant de son nœud est unique s'il existe, et son frère droit est également unique s'il existe. Par conséquent, nous définissons deux pointeurs, pointant vers le premier enfant du nœud et le frère droit du nœud.
/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
TElemtype data;
struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
Un arbre binaire est un ensemble fini de nœuds, qui est :
- ou vide
- Il se compose d’un nœud racine et de deux arbres binaires, également appelés sous-arbre gauche et sous-arbre droit.
Comme on peut le voir sur la photo ci-dessus :
- Il n'y a aucun nœud de degré supérieur à 2 dans un arbre binaire
- 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 estarbre commandé
Remarque : Tout arbre binaire est composé des situations suivantes :
Les arbres binaires peuvent généralement être stockés à l'aide de deux structures :Une structure séquentielle, une structure en chaîne.
2. Stockage en chaîne
Les arbres binaires ordinaires ne conviennent pas au stockage dans des tableaux car ils peuvent gaspiller beaucoup d'espace.etLes arbres binaires complets sont plus adaptés au stockage de structures séquentielles .En réalité, nous avons habituellementUn tas (un arbre binaire) utilise un tableau de structures séquentielles pour stocker, il convient de noter que le tas ici et le tas dans l'espace d'adressage du processus virtuel du système d'exploitation sont deux choses différentes. L'une est une structure de données et l'autre est une segmentation de zone qui gère la mémoire dans le système d'exploitation.
Pour une mise en œuvre et une application spécifiques, veuillez consulter :[Structure des données] 08. Applications tas et tas
Le moyen le plus simple d’apprendre une structure arborescente binaire est de la parcourir.soi-disantLa traversée d'un arbre binaire (Traversal) consiste à effectuer les opérations correspondantes sur les nœuds de l'arbre binaire en séquence selon certaines règles, et chaque nœud n'est utilisé qu'une seule fois. . Les opérations effectuées en accédant aux nœuds dépendent du problème d'application spécifique. Le parcours est l'une des opérations les plus importantes sur un arbre binaire et constitue également la base d'autres opérations sur un arbre binaire.
//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
La figure ci-dessous montre le processus récursif :
//左子树 根 右子树
void InOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
Voici le processus récursif :
//左子树 右子树 根
void PostOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
Voici le processus récursif :
Parcours par ordre de niveau : en plus du parcours par ordre de niveau, du parcours par ordre dans l'ordre et du parcours par ordre de niveau, le parcours par ordre de niveau peut également être effectué sur des arbres binaires. Supposons que le numéro de niveau du nœud racine de l'arbre binaire soit 1. Le parcours par ordre de niveau commence à partir du nœud racine de l'arbre binaire. Il visite d'abord le nœud racine du premier niveau, puis visite les nœuds du second. niveau de gauche à droite, puis le troisième niveau Les nœuds du calque, et ainsi de suite,Le processus de visite des nœuds de l'arborescence couche par couche de haut en bas et de gauche à droite est un parcours par ordre de couche.。
Illustration:
Ici, nous intervenons dans la file d'attente pour effectuer un parcours de pré-ordre de l'arbre binaire.
// 层序遍历
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);
}
Pour créer et détruire un arbre binaire, nous utilisonsParcours d'arbre binairePar exemple.
//二叉树的创建
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;
}
//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
if(root==NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
Les opérations suivantes sont toutes réalisées selon l'idée de parcours.
// 二叉树节点个数
int TreeSize(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
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);
}
// 二叉树第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);
}
// 二叉树查找值为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;
}
//二叉树的高度
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;
}
//判断是否是完全二叉树
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;
}
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
