In tất cả đường đi từ gốc đến lá với vị trí tương đối trong C++

Cho một cây nhị phân. In tất cả đường đi từ gốc đến lá. Thêm dấu gạch dưới "_" để hiển thị vị trí tương đối của các nút.

Ví dụ:

Đầu vào:

Đầu ra:

_ _ 3 _ 9 1 _3 9 _7 3 _ 4 _ _ 2 3 9 4 1 7 6 2 3 _ 4 6

Giải pháp: Sử dụng thứ tự dọc (vertical order) của các phần tử cây.

Dựa trên đó, in đường đi từ gốc đến lá.

Thuật toán

Bước 1: Duyệt cây nhị phân theo tiền thứ tự (preorder). Tính khoảng cách ngang (horizontal distance): gốc là 0, con trái giảm 1, con phải tăng 1.
Bước 2: Khi đến nút lá, in đường đi với dấu "_" ở cuối.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;
#define MAX_PATH_SIZE 1000
struct Node{
    char data;
    Node *left, *right;
};
Node * newNode(char data){
    struct Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
struct PATH{
    int horizontalDistance;
    char key;
};
void printPath(vector< PATH > path, int size){
    int minimumhorizontalDistance = INT_MAX;
    PATH p;
    for (int it = 0; it < size; it++){
        p = path[it];
        minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance);
    }
    for (int it = 0; it < size; it++){
        p = path[it];
        int noOfUnderScores = abs(p.horizontalDistance - minimumhorizontalDistance);
        for (int i = 0; i < noOfUnderScores; i++) cout << "_ ";
        cout << p.key << endl;
    }
    cout << "\nNext Path\n";
}
void printAllRtLPaths(Node *root, vector< PATH > &AllPath, int horizontalDistance, int order ){
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL){
        AllPath[order] = (PATH { horizontalDistance, root->data });
        printPath(AllPath, order + 1);
        return;
    }
    AllPath[order] = (PATH { horizontalDistance, root->data });
    printAllRtLPaths(root->left, AllPath, horizontalDistance - 1, order + 1);
    printAllRtLPaths(root->right, AllPath, horizontalDistance + 1, order + 1);
}
void printRootToLeafPath(Node *root){
    if (root == NULL) return;
    vector<PATH> Allpaths(MAX_PATH_SIZE);
    printAllRtLPaths(root, Allpaths, 0, 0);
}
int main(){
    Node *root = newNode('3');
    root->left = newNode('9');
    root->right = newNode('4');
    root->left->left = newNode('1');
    root->left->right = newNode('7');
    root->right->left = newNode('6');
    root->right->right = newNode('2');
    printRootToLeafPath(root);
    return 0;
}

Kết quả

_ _ 3 _ 9 1 Next Path _ 3 9 _ 7 Next Path 3 _ 4 6 Next Path 3 _ 4 _ _ 2