Drucken Sie in der Sprache C die rechte Ansicht des Binärbaums

Die Aufgabe besteht darin, den rechten Knoten des angegebenen Binärbaums zu drucken. Zuerst fügt der Benutzer Daten ein, um einen Binärbaum zu erstellen, und druckt dann eine rechte Ansicht des resultierenden Baums.

Das obige Bild zeigt einen Binärbaum, der mit den Knoten 10, 42, 93, 14, 35, 96, 57 und 88 erstellt wurde, wobei die Knoten auf der rechten Seite des Baums ausgewählt und angezeigt werden. Beispielsweise sind 10, 93, 57 und 88 die Knoten ganz rechts im Binärbaum.

Beispiel

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

Jeder Knoten hat zwei Zeiger, einen linken Zeiger und einen rechten Zeiger. Gemäß dieser Frage muss das Programm nur den richtigen Knoten durchlaufen. Daher muss das linke Kind des Knotens nicht berücksichtigt werden.

In der rechten Ansicht werden alle Knoten gespeichert, die der letzte Knoten ihrer Ebene sind. Daher können wir einfach rekursive Methoden verwenden, um Knoten so zu speichern und darauf zuzugreifen, dass zuerst der rechte Teilbaum und dann der linke Teilbaum durchlaufen wird. Immer wenn das Programm erkennt, dass die Ebene eines Knotens größer ist als die Ebene des vorherigen Knotens, wird der vorherige Knoten angezeigt, da er der letzte Knoten in seiner Ebene ist.

Der folgende Code zeigt die C-Sprachimplementierung des angegebenen Algorithmus.

Die chinesische Übersetzung des Algorithmus

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

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

Wenn wir das obige Programm ausführen, wird die folgende Ausgabe generiert.

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

Das obige ist der detaillierte Inhalt vonDrucken Sie in der Sprache C die rechte Ansicht des Binärbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!