In tất cả các đường dẫn từ gốc đến lá với các vị trí tương đối trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Và chúng ta phải in tất cả các con đường từ gốc đến lá của cây. Ngoài ra, thêm dấu gạch dưới “_” để hiển thị vị trí tương đối của các nút.

Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -

Đầu vào -

Đầu ra -

Để giải quyết vấn đề này, chúng ta sẽ sử dụng khái niệm về thứ tự dọc của các nguyên tố của cây.

In tất cả các đường dẫn từ gốc đến lá với các vị trí tương đối trong C ++

Dựa trên điều này, chúng tôi sẽ in đường dẫn từ gốc đến lá.

Thuật toán

Step 1: Traverse the binary tree using preorder traversal. And on traversal calculate the horizontal distance based on the order. The horizontal distance of root is 0 and processed as the above diagram.
Step 2: And on traversing to the leaf node, print the path with an underscore “_” at the end.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
#define MAX_PATH_SIZE 1000
struct Node{
   char data;
   Node *left, *right;
};
Node * newNode(char data){
   struct Node *temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
struct PATH{
   int horizontalDistance;
   char key;
};
void printPath(vector < PATH > path, int size){
   int minimumhorizontalDistance = INT_MAX;
   PATH p;
   for (int it=0; it<size; it++){
      p = path[it];
      minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance);
   }
   for (int it=0; it < size; it++){
      p = path[it];
      int noOfUnderScores = abs(p.horizontalDistance -minimumhorizontalDistance);
      for (int i = 0; i < noOfUnderScores; i++) cout<<"_ ";
         cout<<p.key<<endl;
   }
   cout<<"\nNext Path\n";
}
void printAllRtLPaths(Node *root, vector < PATH > &AllPath, int horizontalDistance, int order ){
   if(root == NULL)
      return;
   if (root->left == NULL && root->right == NULL){
      AllPath[order] = (PATH { horizontalDistance, root->data });
      printPath(AllPath, order+1);
      return;
   }
   AllPath[order] = (PATH { horizontalDistance, root->data });
   printAllRtLPaths(root->left, AllPath, horizontalDistance-1, order+1);
   printAllRtLPaths(root->right, AllPath, horizontalDistance+1, order+1);
}
void printRootToLeafPath(Node *root){
   if (root == NULL)
      return;
   vector<PATH> Allpaths(MAX_PATH_SIZE);
   printAllRtLPaths(root, Allpaths, 0, 0);
}
int main(){
   Node *root = newNode('3');
   root->left = newNode('9');
   root->right = newNode('4');
   root->left->left = newNode('1');
   root->left->right = newNode('7');
   root->right->left = newNode('6');
   root->right->right = newNode('2');
   printRootToLeafPath(root);
   return 0;
}

Đầu ra

_ _ 3
_ 9
1
Next Path
_ 3
9
_ 7
Next Path
3
_ 4
6
Next Path
3
_ 4
_ _ 2