พิมพ์โหนดของ Binary Tree ตามลำดับที่กลายเป็น Leaf Node ใน C++

กำหนด Binary Tree เราต้องพิมพ์โหนดใบ (leaf nodes) แล้วลบโหนดใบเหล่านั้นออก แล้วทำซ้ำจนไม่มีโหนดเหลือในต้นไม้

ตัวอย่าง

ดังนั้นผลลัพธ์ควรเป็น:

6 7 9 13 14 3 4 2 1

แนวทาง

เราใช้แนวทาง DFS (Depth First Search)

กำหนดค่าเริ่มต้นเป็นศูนย์ให้ทุกโหนด แล้วกำหนดค่าให้โหนดทุกตัวเป็น max(ค่าของลูกทั้งสอง) + 1

อัลกอริทึม

START
ขั้นตอนที่ 1: กำหนด struct Node พร้อม data, order, *left, *right
ขั้นตอนที่ 2: ฟังก์ชัน newNode(int data, int order) สร้างโหนดใหม่
ฟังก์ชัน postod(struct Node* node, vector<pair<int, int> >& v)
    ขั้นตอนที่ 1: ถ้า node == NULL RETURN
    ขั้นตอนที่ 2: เรียก postod(node->left, v)
    ขั้นตอนที่ 3: เรียก postod(node->right, v)
    ขั้นตอนที่ 4: ถ้า node->right == NULL && node->left == NULL
        SET node->order = 1
        v.push_back(make_pair(node->order, node->data))
    ELSE
        node->order = max((node->left)->order, (node->right)->order) + 1
        v.push_back(make_pair(node->order, node->data))
    END IF
ฟังก์ชัน printLeafNodes(int n, vector<pair<int, int> >& v)
    ขั้นตอนที่ 1: sort(v.begin(), v.end())
    ขั้นตอนที่ 2: วนลูป i = 0 ถึง n-1
        ถ้า v[i].first == v[i+1].first พิมพ์ v[i].second
        ไม่เช่นนั้น พิมพ์ v[i].second พร้อมขึ้นบรรทัดใหม่
    END FOR
ใน main()
    ขั้นตอนที่ 1: สร้าง ROOT NODE struct Node* root = newNode(8, 0)
    ขั้นตอนที่ 2: กำหนด n = 9
    ขั้นตอนที่ 3: เรียก postod(root, v)
    ขั้นตอนที่ 4: เรียก printLeafNodes(n, v)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    int order;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int data, int order) {
    struct Node* node = new Node;
    node->data = data;
    node->order = order;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

void postod(struct Node* node, vector<pair<int, int> >& v) {
    if (node == NULL)
        return;
    postod(node->left, v);
    postod(node->right, v);
    if (node->right == NULL && node->left == NULL) {
        node->order = 1;
        v.push_back(make_pair(node->order, node->data));
    } else {
        node->order = max((node->left)->order, (node->right)->order) + 1;
        v.push_back(make_pair(node->order, node->data));
    }
}

void printLeafNodes(int n, vector<pair<int, int> >& v) {
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        if (v[i].first == v[i + 1].first)
            cout << v[i].second << " ";
        else
            cout << v[i].second << "\n";
    }
}

int main() {
    struct Node* root = newNode(1, 0);
    root->left = newNode(2, 0);
    root->right = newNode(3, 0);
    root->left->left = newNode(4, 0);
    root->left->right = newNode(6, 0);
    root->right->left = newNode(14, 0);
    root->right->right = newNode(9, 0);
    root->left->left->left = newNode(7, 0);
    root->left->left->right = newNode(13, 0);
    int n = 9;
    vector<pair<int, int> > v;
    postod(root, v);
    printLeafNodes(n, v);
    return 0;
}

ผลลัพธ์

6 7 9 13 14 3 4 2 1