Tổng các nút hình ảnh phản chiếu của một cây nhị phân hoàn chỉnh theo cách nhỏ hơn trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân hoàn chỉnh. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng các nút hình ảnh phản chiếu của một cây nhị phân hoàn chỉnh theo cách nhỏ hơn.

Ở đây, chúng ta phải tìm đường đi ngang nhỏ hơn của cây mặt trời bên trái, và sau đó đối với mỗi nút, chúng ta sẽ thêm hình ảnh phản chiếu với nó. Điều này có nghĩa là nếu chúng ta đi ngang qua nút lá bên trái, chúng ta sẽ thêm giá trị của nút lá bên phải với nó. Vì nó là nút hình ảnh phản chiếu.

Một số định nghĩa quan trọng

Cây nhị phân hoàn chỉnh là một cây nhị phân trong đó tất cả các cấp có số lượng nút cao nhất ngoại trừ cấp cuối cùng.

Inorder traversal là một kỹ thuật duyệt cây, trong đó cây con bên trái được truy cập đầu tiên, gốc được truy cập và cây con bên phải được truy cập.

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

Đầu vào

Đầu ra - 9 9 17 2

Giải thích - Đường đi ngang của cây con bên trái là 5-7-8-1.

Thêm tất cả các nút sẽ phản chiếu hình ảnh.

5 + 4 = 9
7 + 2 = 9
8 + 9 = 17
1 + 1 = 2

Để giải quyết vấn đề này, chúng ta sẽ duyệt cây nhị phân bằng cách sử dụng trình duyệt inorder. Chúng ta sẽ sử dụng hai nút, một nút để đi qua cây con bên trái và nút kia để truy cập nhân bản của nút. Ví dụ, chúng ta có một nút gốc cho cây con bên trái và đối với nó, chúng ta sẽ có mirrorroot sẽ đi ngang qua hình ảnh phản chiếu của nó.

Ví dụ

Chương trình minh họa hoạt động của giải pháp,

#include <iostream>
using namespace std;
typedef struct node {
   int data;
   struct node* left;
   struct node* right;
   node(int d){
      data = d;
      left = NULL;
      right = NULL;
   }
} Node;
void printMirrorSum(Node* root, Node* rootMirror){
   if (root->left == NULL && rootMirror->right == NULL)
      return;
   printMirrorSum(root->left, rootMirror->right);
   cout<<(root->left->data + rootMirror->right->data)<<endl;
   printMirrorSum(root->right, rootMirror->left);
}
int main(){
   Node* root = new Node(1);
   root->left = new Node(7);
   root->right = new Node(2);
   root->left->left = new Node(5);
   root->left->right = new Node(8);
   root->right->left = new Node(9);
   root->right->right = new Node(4);
   cout<<"Sum of node and mirror image nodes are :\n";
   printMirrorSum(root, root);
   if (root)
      cout<<(root->data + root->data);
   return 0;
}

Đầu ra

Sum of node and mirror image nodes are :
9
9
17
2