In các mã lá ở cấp độ nhất định bằng ngôn ngữ C

Nhiệm vụ liên quan đến việc in các nút lá của cây nhị phân ở mức k nhất định được người dùng chỉ định.

Các nút lá là các nút kết thúc có con trỏ trái và phải là NULL, có nghĩa là nút cụ thể đó không phải là nút cha.

Ví dụ

Input : 11 22 33 66 44 88 77
Output : 88 77

Ở đây, k đại diện cho cấp độ của cây cần được in. Cách tiếp cận được sử dụng ở đây là duyệt qua mọi nút và kiểm tra xem nút đó có bất kỳ con trỏ nào không. Ngay cả khi có một con trỏ có nghĩa là trái hoặc phải hoặc cả hai ngoài nút cụ thể đó không thể là nút lá.

Duyệt qua từng nút một cách đệ quy bằng cách sử dụng kỹ thuật thứ tự mức trong đó các nút được duyệt qua mức khôn ngoan bắt đầu từ Trái → gốc → phải.

Đoạn mã dưới đây cho thấy cách triển khai c của thuật toán đã cho

Thuật toán

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 leaf(struct node* root, int level)
      IF root = NULL
         Exit
      End
      IF level = 1
         IF root->left == NULL && root->right == NULL
            Print root->data
         End
      End
      ELSE IF level>1
         Call leaf(root->left, level - 1)
         Call leaf(root->right, level - 1)
      End
   Step 4-> In main()
      Set level = 4
      Call New passing value user want to insert as struct node* root = New(1)
      Call leaf(root,level)
STOP

Ví dụ

include<stdio.h>
#include<stdlib.h>
//structre of a node defined
struct node {
   struct node* left;
   struct node* right;
   int data;
};
//structure to create a new node
struct node* New(int data) {
   struct node* temp = (struct node*)malloc(sizeof(struct node));
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
//function to found leaf node
void leaf(struct node* root, int level) {
   if (root == NULL)
      return;
   if (level == 1) {
      if (root->left == NULL && root->right == NULL)
      printf("%d\n",root->data);
   } else if (level > 1) {
      leaf(root->left, level - 1);
      leaf(root->right, level - 1);
   }
}
int main() {
   printf("leaf nodes are: ");
   struct node* root = New(11);
   root->left = New(22);
   root->right = New(33);
   root->left->left = New(66);
   root->right->right = New(44);
   root->left->left->left = New(88);
   root->left->left->right = New(77);
   int level = 4;
   leaf(root, level);
   return 0;
}

Đầu ra

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau.

leaf nodes are: 88 77