ในปัญหานี้ เราได้รับไบนารีทรีที่สมบูรณ์ งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของโหนดภาพมิเรอร์ของต้นไม้ไบนารีที่สมบูรณ์ในลักษณะที่ไม่เป็นระเบียบ
ที่นี่ เราต้องหาเส้นทางที่ไม่เป็นระเบียบของต้นไม้ดวงอาทิตย์ด้านซ้าย จากนั้นสำหรับแต่ละโหนด เราจะเพิ่มภาพสะท้อนในกระจกด้วย ซึ่งหมายความว่า หากเราข้ามโหนดลีฟด้านซ้าย เราจะเพิ่มค่าของโหนดลีฟด้านขวาด้วย เนื่องจากเป็นโหนดภาพสะท้อน
คำจำกัดความที่สำคัญบางประการ
สร้างไบนารีทรีที่สมบูรณ์ เป็นไบนารีทรีที่ทุกระดับมีจำนวนโหนดสูงสุด ยกเว้นระดับสุดท้าย
การข้ามผ่านแบบไม่เรียงลำดับ เป็นเทคนิคการข้ามต้นไม้โดยไปที่ทรีย่อยทางซ้ายก่อน เยี่ยมชมรูท และเยี่ยมชมทรีย่อยทางขวา
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
ผลผลิต − 9 9 17 2
คำอธิบาย − การข้ามผ่านที่ไม่เป็นระเบียบของทรีย่อยด้านซ้ายคือ 5-7-8-1
การเพิ่มโหนดทั้งหมดจะเป็นการจำลองภาพ
5 + 4 = 9 7 + 2 = 9 8 + 9 = 17 1 + 1 = 2
เพื่อแก้ปัญหานี้ เราจะสำรวจต้นไม้ไบนารีโดยใช้การข้ามผ่านในลำดับ เราจะใช้สองโหนด โหนดหนึ่งเพื่อสำรวจทรีย่อยด้านซ้าย และอีกโหนดหนึ่งเพื่อไปที่มิเรอร์ของโหนด ตัวอย่างเช่น เรามีรูทโหนดสำหรับทรีย่อยทางซ้าย และสำหรับมัน เราจะมีมิเรอร์รูทที่จะข้ามผ่านอิมเมจมิเรอร์ของมัน
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชัน
#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;
} ผลลัพธ์
Sum of node and mirror image nodes are : 9 9 17 2
