En langage C, imprimez la vue de droite de l'arbre binaire

La tâche consiste à imprimer le nœud droit de l'arbre binaire donné. L'utilisateur insérera d'abord des données pour créer un arbre binaire, puis imprimera une vue droite de l'arbre résultant.

L'image ci-dessus montre un arbre binaire créé à l'aide des nœuds 10, 42, 93, 14, 35, 96, 57 et 88, avec les nœuds du côté droit de l'arbre sélectionnés et affichés. Par exemple, 10, 93, 57 et 88 sont les nœuds les plus à droite de l'arbre binaire.

Exemple

Input : 10 42 93 14 35 96 57 88
Output : 10 93 57 88

Chaque nœud a deux pointeurs, un pointeur gauche et un pointeur droit. Selon cette question, le programme n'a besoin que de traverser le bon nœud. Par conséquent, l’enfant gauche du nœud n’a pas besoin d’être pris en compte.

La vue de droite stocke tous les nœuds qui sont le dernier nœud de leur niveau. Par conséquent, nous pouvons simplement utiliser des méthodes récursives pour stocker et accéder aux nœuds de telle manière que le sous-arbre droit soit parcouru en premier, puis le sous-arbre gauche. Chaque fois que le programme détecte que le niveau d'un nœud est supérieur au niveau du nœud précédent, le nœud précédent est affiché car ce sera le dernier nœud de son niveau.

Le code ci-dessous montre l'implémentation en langage C de l'algorithme donné

La traduction chinoise de l'algorithme

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *left, *right
   Step 2 -> create function for inserting node with parameter as item
      Declare temp variable of node using malloc
      Set temp->data = item
      Set temp->left = temp->right = NULL
      return temp
   step 3 -> Declare Function void right_view(struct node *root, int level, int *end_level)
      IF root = NULL
         Return
      IF *end_level < level
         Print root->data
         Set *end_level = level
         Call right_view(root->right, level+1, end_level)
         Call right_view(root->left, level+1, end_level)
   Step 4 -> Declare Function void right(struct node *root)
      Set int level = 0
      Call right_view(root, 1, &level)
   Step 5 -> In Main()
      Pass the values for the tree nodes using struct node *root = New(10)
      Call right(root)
STOP

Exemple

est :

Exemple

#include<stdio.h>
#include<stdlib.h>
struct node {
   int data;
   struct node *left, *right;
};
struct node *New(int item) {
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->left = temp->right = NULL;
   return temp;
}
void right_view(struct node *root, int level, int *end_level) {
   if (root == NULL) return;
   if (*end_level < level) {
      printf("%d\t", root->data);
      *end_level = level;
   }
   right_view(root->right, level+1, end_level);
   right_view(root->left, level+1, end_level);
}
void right(struct node *root) {
   int level = 0;
   right_view(root, 1, &level);
}
int main() {
   printf("right view of a binary tree is : ");
   struct node *root = New(10);
   root->left = New(42);
   root->right = New(93);
   root->left->left = New(14);
   root->left->right = New(35);
   root->right->left = New(96);
   root->right->right = New(57);
   root->right->left->right = New(88);
   right(root);
   return 0;
}

Sortie

Si nous exécutons le programme ci-dessus, il générera la sortie suivante.

right view of a binary tree is : 10 93 57 88

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!