พิมพ์เส้นทางจากรากถึงใบพร้อมตำแหน่งสัมพัทธ์ใน C++

ในปัญหานี้ เราจะได้รับ Binary Tree และต้องพิมพ์เส้นทางทั้งหมดจาก รากถึงใบของต้นไม้ พร้อมเพิ่ม underscore " _ " เพื่อแสดงตำแหน่งสัมพัทธ์ของโหนด

ตัวอย่างเพื่อความเข้าใจ

Input -

Output -

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

เพื่อแก้ปัญหานี้ เราจะใช้แนวคิดของ vertical order ขององค์ประกอบของต้นไม้

จากนั้นเราจะพิมพ์เส้นทางจากรากถึงใบ

อัลกอริทึม

ขั้นตอนที่ 1: ท่อง Binary Tree ด้วย preorder traversal และคำนวณ horizontal distance ตามลำดับ Horizontal distance ของรากคือ 0 และประมวลผลตามแผนภาพด้านบน
ขั้นตอนที่ 2: และเมื่อท่องถึงโหนดใบ ให้พิมพ์เส้นทางพร้อม underscore " _ " ที่ท้าย

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

#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;
}

ผลลัพธ์

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