Tìm khoảng cách từ gốc đến nút đã cho trong cây nhị phân trong C ++

Hãy xem xét chúng ta có một cây nhị phân với vài nút. Chúng ta phải tìm khoảng cách giữa nút gốc và một nút khác u. giả sử cái cây như sau:

Bây giờ khoảng cách giữa (gốc, 6) =2, độ dài đường dẫn là 2, khoảng cách giữa (gốc, 8) =3, v.v.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp đệ quy để tìm kiếm nút ở các cây con bên trái và bên phải, đồng thời cập nhật độ dài cho mỗi cấp độ.

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

Đầu ra

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