โปรแกรม C พิมพ์ Left View ของ Binary Tree

โจทย์

พิมพ์ Left View ของ Binary Tree คือโหนดที่มองเห็นจากด้านซ้าย (โหนดแรกของแต่ละระดับ)

ตัวอย่าง

Input: 1 (root), 0 (left), 3 (right), 2 (left of 3), 4 (right of 3)
Tree:
    1
   / \
  0   3
     / \
    2   4

Output: 1 0 2

วิธีการ

ใช้ Recursive Traversal แบบ Pre-order วิจิต Left subtree ก่อน Right subtree เก็บ highest_level ที่พิมพ์ไปแล้ว ถ้า level ปัจจุบัน > highest_level ให้พิมพ์และอัปเดต

อัลกอริทึม

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

โค้ดภาษา C

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

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

struct node* New(int new_data) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = new_data;
    temp->left = temp->right = NULL;
    return temp;
}

void left_view(struct node* root, int level, int* highest_level) {
    if (root == NULL) return;
    if (*highest_level < level) {
        printf("%d\t", root->data);
        *highest_level = level;
    }
    left_view(root->left, level + 1, highest_level);
    left_view(root->right, level + 1, highest_level);
}

void left(struct node* root) {
    int highest_level = 0;
    left_view(root, 1, &highest_level);
}

int main() {
    printf("left view of a binary tree is : ");
    struct node* root = New(1);
    root->left = New(0);
    root->right = New(3);
    root->right->left = New(2);
    root->right->right = New(4);
    left(root);
    return 0;
}

ผลลัพธ์

left view of a binary tree is : 1 0 2