โปรแกรม C พิมพ์ระดับกลางของ Perfect Binary Tree โดยไม่หาความสูง

Perfect Binary Tree

ต้นไม้ไบนารีที่สมบูรณ์: โหนดภายในทุกตัวมีลูก 2 ตัว และโหนดใบ (leaf) ทุกตัวอยู่ระดับเดียวกัน

โจทย์

พิมพ์โหนดที่ระดับกลางของ Perfect Binary Tree โดยไม่คำนวณความสูง (height) ของต้นไม้

ตัวอย่าง

Input: 13 (root), 21, 44 (level 1), 98, 57, 61, 70 (level 2 - leaves)
Output: 21 44  (ระดับกลาง)

วิธีการ

ใช้หลักการเดียวกับการหาโหนดกลางของ Linked List (Slow/Fast pointer) แต่มาปรับ용กับ Tree:

• ส่ง pointer 2 ตัว a และ b เริ่มที่ root เดียวกัน
• a เดินทีละ 1 ระดับ (a->left, a->right)
• b เดินทีละ 2 ระดับ (b->left->left, b->right->right)
• เมื่อ b ถึง leaf (left และ right เป็น NULL) a จะอยู่ที่ระดับกลาง

อัลกอริทึม

1. โครงสร้างโหนด struct Node {int key; struct Node *left, *right;}
2. ฟังก์ชัน New(value) สร้างโหนด
3. ฟังก์ชัน middle(a, b): if a==NULL||b==NULL return; if b->left==NULL && b->right==NULL print a->key, return; middle(a->left, b->left->left); middle(a->right, b->right->right)
4. ฟังก์ชัน mid_level(node): เรียก middle(node, node)
5. main(): สร้าง Perfect Binary Tree เรียก mid_level(root)

โค้ดภาษา C

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

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);
    return 0;
}

ผลลัพธ์

middle level nodes are : 21 44