โปรแกรม C++ หาใบไม้ที่ใกล้ที่สุดใน Binary Tree

สมมติว่ามี binary tree หนึ่งต้น มีโหนดใบอยู่ที่ระดับต่างๆ อีกตัวชี้หนึ่งกำหนดชี้ไปยังโหนดหนึ่ง เราต้องหาระยะทางไปยังโหนดใบที่ใกล้ที่สุดจากโหนดที่ชี้ไป พิจารณาต้นไม้ดังนี้:

ที่นี่โหนดใบคือ 2, -2 และ 6 หากตัวชี้ชี้ไปที่โหนด -5 โหนดที่ใกล้ที่สุดจาก -5 จะอยู่ที่ระยะ 1

เพื่อแก้ปัญหานี้ เราจะเดินทางผ่านต้นไม้ย่อยที่รากอยู่กับโหนดที่กำหนด และหาใบที่ใกล้ที่สุดในต้นไม้ย่อย แล้วเก็บระยะทาง ตอนนี้เดินทางต้นไม้เริ่มจากราก หากโหนด x อยู่ในต้นไม้ย่อยซ้าย ให้ค้นหาในต้นไม้ย่อยขวา และในทางกลับกัน

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

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
};

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

void getLeafDownward(Node *root, int level, int *minDist) {
    if (root == NULL)
        return ;
    if (root->left == NULL && root->right == NULL) {
        if (level < (*minDist))
            *minDist = level;
        return;
    }
    getLeafDownward(root->left, level+1, minDist);
    getLeafDownward(root->right, level+1, minDist);
}

int getFromParent(Node * root, Node *x, int *minDist) {
    if (root == NULL)
        return -1;
    if (root == x)
        return 0;
    int l = getFromParent(root->left, x, minDist);
    if (l != -1) {
        getLeafDownward(root->right, l+2, minDist);
        return l+1;
    }
    int r = getFromParent(root->right, x, minDist);
    if (r != -1) {
        getLeafDownward(root->left, r+2, minDist);
        return r+1;
    }
    return -1;
}

int minimumDistance(Node *root, Node *x) {
    int minDist = INT8_MAX;
    getLeafDownward(x, 0, &minDist);
    getFromParent(root, x, &minDist);
    return minDist;
}

int main() {
    Node* root = getNode(4);
    root->left = getNode(2);
    root->right = getNode(-5);
    root->right->left = getNode(-2);
    root->right->right = getNode(6);
    Node *x = root->right;
    cout << "Closest distance of leaf from " << x->data << " is: " << minimumDistance(root, x);
}

ผลลัพธ์

Closest distance of leaf from -5 is: 1