Giả sử, một cây nhị phân được đưa ra. Nó có các nút lá ở các cấp độ khác nhau. Một con trỏ khác được đưa ra, đó là trỏ đến một nút. Chúng ta phải tìm khoảng cách đến nút lá gần nhất tính từ nút nhọn. Hãy coi cái cây giống như bên dưới -
Ở đây các nút lá là 2, -2 và 6. Nếu con trỏ trỏ đến nút -5, Các nút gần nhất từ -5 sẽ ở khoảng cách 1.
Để giải quyết điều này, chúng ta sẽ duyệt qua cây con có gốc với nút đã cho, và tìm lá gần nhất trong cây con, sau đó lưu trữ khoảng cách. Bây giờ đi ngang cây bắt đầu từ gốc, nếu nút x hiện diện trong cây con bên trái, thì hãy tìm kiếm trong cây con bên phải và ngược lại.
Ví dụ
#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);
} Đầu ra
Closest distance of leaf from -5 is: 1