การท่องต้นไม้แบบทวิภาคแบบแนวทแยง (Diagonal Traversal) ใน C++

แนวคิด

Diagonal Traversal: ท่องโหนดที่อยู่บนเส้นทแยงเดียวกัน (ความชัน -1) กลุ่มโหนดตามระยะห่างแนวทแยง (Diagonal Distance)

อัลกอริธึม

• ใช้ Map: Key = diagonal depth, Value = vector ของค่าโหนด
• Inorder traversal: ไปซ้าย depth+1, ไปขวา depth คงเดิม
• พิมพ์แต่ละ diagonal ตามลำดับ depth

โปรแกรมตัวอย่าง

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void traverseDiagonal(Node* root, int depth, map<int, vector<int>>& m) {
    if (root) {
        m[depth].push_back(root->data);
        traverseDiagonal(root->left, depth + 1, m);
        traverseDiagonal(root->right, depth, m);
    }
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(4);
    root->left->right = new Node(6);
    root->right->right = new Node(17);
    root->right->right->left = new Node(16);
    
    map<int, vector<int>> m;
    traverseDiagonal(root, 0, m);
    
    for (auto& p : m) {
        for (int val : p.second) cout << val << " ";
        cout << endl;
    }
    return 0;
}

ผลลัพธ์

10 15 17 
5 6 16 
4