In tất cả các nút ở khoảng cách k từ một nút nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp một cây nhị phân, một nút đích và một số nguyên K. Chúng ta phải in tất cả các nút của cây cách nút đích K .

Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút (một / hai / không có).

Hãy lấy một ví dụ để hiểu vấn đề

K =2

Nút mục tiêu:9

Đầu ra -

5 1 3.

Giải thích -

Khoảng cách có thể được thực hiện cho nút cao hơn, thấp hơn hoặc ở cùng một mức. Vì vậy, chúng tôi sẽ trả về các nút tương ứng.

Để giải quyết vấn đề này, chúng ta phải hiểu các loại nút cách nút đích là K.

Từ bài kiểm tra trên, chúng ta có thể thấy k nút ở xa có thể nằm trong cây con của nút đích (5 và 1) hoặc bất kỳ đâu trong cây con tổ tiên của nút đích (3).

Bây giờ, phương pháp để tìm lời giải của trường hợp đầu tiên là đi ngang qua cây con của nút đích và kiểm tra xem khoảng cách của một nút so với mục tiêu có phải là K. Nếu có, hãy in nút đó.

Đối với trường hợp thứ hai, chúng ta phải kiểm tra các nút tổ tiên và cây con của các tổ tiên này cho mục tiêu và in tất cả ở khoảng cách K từ nó.

Chương trình dưới đây sẽ cho thấy việc triển khai giải pháp của chúng tôi -

Ví dụ

#include <iostream>
using namespace std;
struct node {
   int data;
   struct node *left, *right;
};
void printSubtreeNodes(node *root, int k) {
   if (root == NULL || k < 0) return;
   if (k==0){
      cout<<root->data<<"\t";
      return;
   }
   printSubtreeNodes(root->left, k-1);
   printSubtreeNodes(root->right, k-1);
}
int printKNodes(node* root, node* target , int k){
   if (root == NULL) return -1;
   if (root == target){
      printSubtreeNodes(root, k);
      return 0;
   }
   int dl = printKNodes(root->left, target, k);
   if (dl != -1){
      if (dl + 1 == k)
         cout<<root->data<<"\t";
      else
         printSubtreeNodes(root->right, k-dl-2);
      return 1 + dl;
   }
   int dr = printKNodes(root->right, target, k);
      if (dr != -1){
         if (dr + 1 == k)
            cout << root->data << endl;
         else
            printSubtreeNodes(root->left, k-dr-2);
         return 1 + dr;
      }
      return -1;
   }
   node *insertNode(int data){
      node *temp = new node;
      temp->data = data;
      temp->left = temp->right = NULL;
      return temp;      
}
int main(){
   node * root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(9);
   root->left->right = insertNode(4);
   root->right->left = insertNode(8);
   root->right->right = insertNode(10);
   root->right->right->left = insertNode(5);
   root->right->right->right = insertNode(1);
   node * target = root->right;
   int K = 2;
   cout<<"Nodes at distance "<<K<<" from the target node are :\n";
   printKNodes(root, target, K);
   return 0;
}

Đầu ra

Nodes at distance 2 from the target n tode are − 
5 1 3