หาความห่างจากรูทไปยังโหนดที่กำหนดในต้นไม้ไบนารีด้วย C++

พิจารณาว่ามีต้นไม้ไบนารีที่มีโหนดอยู่บ้าง เราต้องหาความห่างระหว่างรูทและอีกโหนดหนึ่ง u สมมติว่าต้นไม้เป็นแบบด้านล่าง:

ตอนนี้ ระยะห่างระหว่าง (root, 6) = 2 ความยาวเส้นทางคือ 2 ระยะห่างระหว่าง (root, 8) = 3 เป็นต้น

เพื่อแก้ปัญหานี้ เราจะใช้วิธีแบบเรียกซ้ำ (Recursive) เพื่อค้นหาโหนดในต้นไม้ย่อยซ้ายและขวา และอัปเดตความยาวสำหรับแต่ละระดับ

ตัวอย่าง

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

int getDistance(Node *root, int x) {
    if (root == NULL)
        return -1;
    int dist = -1;
    if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
        return dist + 1;
    return dist;
}

int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);
    root->right->left->right = getNode(8);
    cout << "Distance from root to node 6 is: " << getDistance(root, 6);
    cout << "\nDistance from root to node 8 is: " << getDistance(root, 8);
}

ผลลัพธ์

Distance from root to node 6 is: 2
Distance from root to node 8 is: 3