Imprimer la vue gauche de l'arbre binaire en langage C-C++-php.cn

Imprimer la vue gauche de l'arbre binaire en langage C

WBOY

Libérer： 2023-09-03 13:25:05

avant

1448 Les gens l'ont consulté

La tâche consiste à imprimer le nœud gauche de l'arbre binaire donné. Tout d'abord, l'utilisateur insérera des données, générant ainsi un arbre binaire, puis imprimera la vue gauche de l'arbre résultant.

Chaque nœud peut avoir au maximum 2 nœuds enfants, ce programme doit donc itérer uniquement le pointeur gauche associé au nœud

Si le pointeur gauche n'est pas nul, cela signifie qu'il aura des données ou un pointeur associé, sinon ce sera la gauche enfant à imprimer et à afficher en sortie.

Exemple

Input : 1 0 3 2 4
Output : 1 0 2

Copier après la connexion

Imprimer la vue gauche de larbre binaire en langage C

Ici, le nœud orange représente la vue gauche de l'arbre binaire.

Dans le graphique donné, le nœud avec les données 1 est le nœud racine, il sera donc imprimé, au lieu d'aller au nœud enfant gauche, il imprimera 0, puis il ira à 3 et imprimera son nœud enfant gauche, Cela fait 2.

Nous pouvons utiliser une méthode récursive pour stocker les niveaux des nœuds et les transférer à plusieurs reprises vers

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

algorithm

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 new_data
      Declare temp variable of node using malloc
      Set temp->data = new_data
      Set temp->left = temp->right = NULL
      return temp
   Step 3 -> declare function void left_view(struct node* root, int level, int* highest_level)
      IF root = NULL
         Exit
      End
      IF *highest_level < level
         Print root->data
         Set *highest_level = level
      End
      Recursively call left_view(root->left, level + 1, highest_level)
      Recursively call left_view(root->right, level + 1, highest_level)
   Step 4 -> Declare Function void left(struct node* root)
      Set int highest_level = 0
      Call left_view(root, 1, &highest_level)
   Step 5-> In main()
      Call New passing value user want to insert as struct node* root = New(1)
      Call left(root)
STOP

Copier après la connexion

Exemple

#include <stdio.h>
#include <stdlib.h>
//create a structure of a node
struct node {
   int data;
   struct node *left, *right; //this pointer will point to the nodes attached with a node
};
struct node* New(int new_data) {
   struct node* temp = (struct node*)malloc(sizeof(struct node));
   //allocating memory to a pointer    dynamically
   temp->data = new_data;
   temp->left = temp->right = NULL;
   return temp;
}
void left_view(struct node* root, int level, int* highest_level) {
   if (root == NULL) //if there is no node that means no data
   return;
   // this function will retrun the root node if there is only root node in a tree
   if (*highest_level < level) {
      printf("%d\t", root->data);
      *highest_level = level;
   }
   // Recursive function
   left_view(root->left, level + 1, highest_level);
   left_view(root->right, level + 1, highest_level);
}
void left(struct node* root) {
   int highest_level = 0;
   left_view(root, 1, &highest_level);
}
int main() {
   printf("left view of a binary tree is : ");
   struct node* root = New(1);
   root->left = New(0);
   root->right = New(3);
   root->right->left = New(2);
   root->right->right = New(4);
   left(root);
   return 0;
}

Copier après la connexion