สมมุติว่าให้ต้นไม้ไบนารีหนึ่งต้น มีโหนดลีฟในระดับต่างๆ มีตัวชี้อีกตัวหนึ่งซึ่งชี้ไปที่โหนด เราต้องหาระยะห่างจากโหนดปลายสุดที่ใกล้ที่สุดจากโหนดปลายแหลม พิจารณาว่าต้นไม้มีลักษณะดังนี้ −
โหนดปลายสุดคือ 2, -2 และ 6 หากตัวชี้ชี้ไปที่โหนด -5 โหนดที่ใกล้ที่สุดจาก -5 จะอยู่ที่ระยะ 1
ในการแก้ปัญหานี้ เราจะสำรวจทรีย่อยที่รูทด้วยโหนดที่กำหนด และค้นหาลีฟที่ใกล้ที่สุดในทรีย่อย จากนั้นเก็บระยะทาง ตอนนี้กำลังสำรวจต้นไม้โดยเริ่มจากราก ถ้าโหนด x มีอยู่ในทรีย่อยด้านซ้าย ให้ค้นหาในทรีย่อยด้านขวา และในทางกลับกัน
ตัวอย่าง
#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
