In đường đi gốc-đến-lá ngắn nhất đầu tiên trong cây nhị phân (C++)

Cho cây nhị phân, chương trình tìm đường đi ngắn nhất từ gốc đến lá trong nhiều đường đi có thể.

Vì duyệt cây từ trái sang phải, nếu có nhiều đường đi ngắn nhất thì chương trình in đường đi ngắn nhất đầu tiên được duyệt (bên trái).

Dùng hàng đợi (queue) duyệt theo cấp độ (Level order traversal), đường có ít cấp độ nhất sẽ được in trước vì đó là đường ngắn nhất từ gốc đến lá.

Các đường đi từ gốc đến lá:

10 → 3 (đây là đường ngắn nhất) 
10 → 211 → 100 
10 → 211 → 146

Ví dụ

Input: 10 3 211 100 146 
Output: 10 3

Thuật toán

Bước 1: Tạo cấu trúc nút: struct node { node *left, *right; int data; }
Bước 2: Hàm tạo nút newnode(int data) trả về node*
Bước 3: Hàm tính đường đi path(int data, unordered_map<int,int> prnt)
    NẾU prnt[data] == data TRẢ VỀ
    path(prnt[data], prnt)
    IN prnt[data]
Bước 4: Hàm tìm đường trái left(Node* root)
    TẠO queue<Node*> que, que.push(root)
    leaf = -1, temp = NULL
    TẠO unordered_map<int, int> prnt, prnt[root->data] = root->data
    WHILE !que.empty()
        temp = que.front(), que.pop()
        NẾU !temp->left && !temp->right
            leaf = temp->data, BREAK
        NGƯỢC LẠI
            NẾU temp->left: que.push(temp->left), prnt[temp->left->data] = temp->data
            NẾU temp->right: que.push(temp->right), prnt[temp->right->data] = temp->data
    path(leaf, prnt), IN leaf
Bước 5: Trong main(): tạo cây, gọi left(root)

Ví dụ mã C++

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

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

Node* newnode(int data) { 
    Node* temp = new Node; 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 

void path(int data, unordered_map<int, int> prnt) { 
    if (prnt[data] == data) return; 
    path(prnt[data], prnt); 
    cout << prnt[data] << " "; 
} 

void left(Node* root) { 
    queue<Node*> que; 
    que.push(root); 
    int leaf = -1; 
    Node* temp = NULL; 
    unordered_map<int, int> prnt; 
    prnt[root->data] = root->data; 
    while (!que.empty()) { 
        temp = que.front(); 
        que.pop(); 
        if (!temp->left && !temp->right) { 
            leaf = temp->data; 
            break; 
        } else { 
            if (temp->left) { 
                que.push(temp->left); 
                prnt[temp->left->data] = temp->data; 
            } 
            if (temp->right) { 
                que.push(temp->right); 
                prnt[temp->right->data] = temp->data; 
            } 
        } 
    } 
    path(leaf, prnt); 
    cout << leaf << " "; 
} 

int main() { 
    Node* root = newnode(90); 
    root->left = newnode(21); 
    root->right = newnode(32); 
    root->left->left = newnode(45); 
    root->right->left = newnode(52); 
    root->right->right = newnode(27); 
    root->left->left->left = newnode(109); 
    root->left->left->right = newnode(101); 
    root->right->right->left = newnode(78); 
    left(root); 
    return 0; 
}

Kết quả

Chạy chương trình cho kết quả:

90 32 52