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

โจทย์

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

ตัวอย่าง

Input: 10 42 93 14 35 96 57 88
Tree:
       10
      /  \
    42    93
   / \   / \
 14  35 96 57
          \
          88

Output: 10 93 57 88

วิธีการ

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

อัลกอริทึม

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

โค้ดภาษา C

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

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

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

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

void right(struct node* root) {
    int level = 0;
    right_view(root, 1, &level);
}

int main() {
    printf("right view of a binary tree is : ");
    struct node* root = New(10);
    root->left = New(42);
    root->right = New(93);
    root->left->left = New(14);
    root->left->right = New(35);
    root->right->left = New(96);
    root->right->right = New(57);
    root->right->left->right = New(88);
    right(root);
    return 0;
}

ผลลัพธ์

right view of a binary tree is : 10 93 57 88