โปรแกรม C พิมพ์ Leaf Nodes ของ Binary Tree ที่ระดับที่กำหนด

โจทย์

พิมพ์ Leaf Nodes (โหนดใบ) ของ Binary Tree ที่ระดับ (level) ที่ผู้ใช้ระบุ k

Leaf Node คืออะไร?

โหนดที่ไม่มีลูก (left == NULL และ right == NULL)

ตัวอย่าง

Tree:
        11
       /  \
     22    33
    /      \
  66        44
 /  \
88   77

Level 4: 88, 77 (ทั้งคู่เป็น leaf nodes)

อัลกอริทึม

1. โครงสร้างโหนด struct node {int data; struct node *left, *right;}
2. ฟังก์ชัน New(data) สร้างโหนด
3. ฟังก์ชัน leaf(root, level): if root==NULL return; if level==1 และ root->left==NULL && root->right==NULL print root->data; else if level>1 เรียก leaf(left, level-1) และ leaf(right, level-1)
4. main(): สร้าง tree กำหนด level=4 เรียก leaf(root, level)

โค้ดภาษา C

#include <stdio.h>
#include <stdlib.h>

struct node {
    struct node* left;
    struct node* right;
    int data;
};

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

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

ผลลัพธ์

leaf nodes are: 88 77