Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม C

พิมพ์ไบนารีทรีที่สมบูรณ์แบบระดับกลางโดยไม่ต้องค้นหาความสูงในภาษาซี


โปรแกรมควรพิมพ์ระดับกลางของไบนารีทรีเช่น ถ้าไบนารีทรีมี 4 ระดับกว่าโปรแกรมจะต้องพิมพ์โหนดระดับ 2 แต่ความต้องการในที่นี้คือการคำนวณระดับโดยไม่ค้นหาความสูง

ต้นไม้ไบนารีที่สมบูรณ์แบบคือต้นไม้ที่โหนดภายในต้องมีลูกสองคน และโหนดที่ปล่อยทั้งหมดควรอยู่ที่ระดับหรือความลึกเท่ากัน

พิมพ์ไบนารีทรีที่สมบูรณ์แบบระดับกลางโดยไม่ต้องค้นหาความสูงในภาษาซี

ที่นี่

  • โหนดภายใน 21 และ 32 ทั้งคู่มีลูก

  • โหนดลีฟคือ 41, 59, 33 และ 70 ทั้งหมดอยู่ในระดับเดียวกัน

เนื่องจากมีคุณสมบัติตรงตามข้อกำหนดทั้งสองจึงเป็นต้นไม้ไบนารีที่สมบูรณ์แบบ

ตัวอย่าง

Input : 12 21 32 41 59 33 70
Output : 21 32

วิธีการที่ใช้ในที่นี้เหมือนกับการค้นหาองค์ประกอบตรงกลางของรายการที่เชื่อมโยงโดยการตรวจสอบตัวชี้ซ้ายและขวาของโหนด ไม่ว่าจะเป็น NULL หรือ NOT NULL โดยการเรียกใช้ฟังก์ชันแบบเรียกซ้ำ

โค้ดด้านล่างแสดงการใช้งาน c ของอัลกอริทึมที่กำหนด

อัลกอริทึม

START
   Step 1 -> create node variable of type structure
      Declare int key
      Declare pointer of type node using *left, *right
   Step 2 -> create function for inserting node with parameter as value
      Declare temp variable of node using malloc
      Set temp->data = value
      Set temp->left = temp->right = NULL
      return temp
   step 3 - > Declare Function void middle(struct Node* a, struct Node* b)
      IF a = NULL||b = NULL
         Return
      IF ((b->left == NULL) && (b->right == NULL))
         Print a->key
         Return
      End
      Call middle(a->left, b->left->left)
      Call middle(a->right, b->left->left)
   Step 4 -> Declare Function void mid_level(struct Node* node)
      Call middle(node, node)
   Step 5 -> In main()
      Call New passing value user want to insert as struct Node* n1 = New(13);
      Call mid_level(n1)
STOP

ตัวอย่าง

#include <stdio.h>
#include<stdlib.h>
struct Node {
   int key;
   struct Node* left, *right;
};
struct Node* New(int value) {
   struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
   temp->key = value;
   temp->left = temp->right = NULL;
   return (temp);
}
void middle(struct Node* a, struct Node* b) {
   if (a == NULL || b == NULL)
      return;
   if ((b->left == NULL) && (b->right == NULL)) {
      printf("%d ",a->key);
      return;
   }
   middle(a->left, b->left->left);
   middle(a->right, b->left->left);
}
void mid_level(struct Node* node) {
   middle(node, node);
}
int main() {
   printf("middle level nodes are : ");
   struct Node* n1 = New(13);
   struct Node* n2 = New(21);
   struct Node* n3 = New(44);
   struct Node* n4 = New(98);
   struct Node* n5 = New(57);
   struct Node* n6 = New(61);
   struct Node* n7 = New(70);
   n2->left = n4;
   n2->right = n5;
   n3->left = n6;
   n3->right = n7;
   n1->left = n2;
   n1->right = n3;
   mid_level(n1);
}

ผลลัพธ์

หากเรารันโปรแกรมด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

middle level nodes are : 21 44