ทรีไบนารีเป็นสตริงพร้อมวงเล็บใน C ++

ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือสร้างโปรแกรมที่จะแปลงไบนารีทรีเป็นสตริงด้วยวงเล็บใน C ++

ค่าของไบนารีทรีเป็นจำนวนเต็มและจะถูกป้อนเข้าสู่โปรแกรมด้วยวิธีการสั่งซื้อล่วงหน้า สตริงควรมีเฉพาะจำนวนเต็มและวงเล็บ () และควรปรับให้เหมาะสมด้วย เช่น ควรกำจัดคู่ที่ว่างทั้งหมด

ต้นไม้ไบนารี เป็นต้นไม้ที่มีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน

ตัวอย่างไบนารีทรี −

การสั่งผ่านล่วงหน้า :[4, 1, 8, 3, 9, 2, 5]

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −

อินพุต

ผลลัพธ์

คำอธิบาย

ราก -> 4()() -> 4(1()())(9) -> 4(1(8()())())(9) -> 4(1(8( 3)())())(9) -> 4(1(8(3)())())(9(2)(5))

ลบวงเล็บว่างทั้งหมด

4(1(8(3)))(9(2)(5))

ตอนนี้ มาแก้ปัญหากัน เราจะทำการสั่งซื้อล่วงหน้าของไบนารีทรี และเราจะใส่วงเล็บไว้ทุกที่ที่จำเป็น นอกจากนี้ เราจะต้องตัดเหล็กจัดฟันคู่พิเศษออกด้วย สำหรับสิ่งนี้ เราจะใช้การเรียกซ้ำไปยังฟังก์ชันที่จะใส่วงเล็บ

เราจะพิมพ์โหนดและเรียกใช้ฟังก์ชันแบบเรียกซ้ำสำหรับทั้งลูกของโหนดด้วยประโยคจนกระทั่งไม่มีลูกเหลือสำหรับโหนดเช่นโหนดปลายสุด

ขณะเรียกใช้ฟังก์ชันสำหรับโหนดย่อยของโหนด เราจะพบหนึ่งใน 4 กรณีนี้ −

กรณีที่1 − เมื่อโหนดมีโหนดย่อยทั้งสองอยู่ เราจะใส่วงเล็บสำหรับทั้งชายด์และใส่ค่าไว้ในวงเล็บและเรียกโหนดย่อยถ้ามี

ตัวอย่าง − จากตัวอย่างข้างต้นสำหรับโหนดรูท 4 โดยที่โหนดย่อยทั้งสองมีอยู่ 4(1)(9)

กรณีที่ 2 − เมื่อโหนดมีลูกคนซ้ายเท่านั้น เราจะใส่ลูกด้านซ้ายลงในวงเล็บ เนื่องจากไม่มีลูกที่ถูกต้องอยู่ในวงเล็บเหลี่ยมจะถูกตัดออก และเรียกเฉพาะทรีย่อยย่อยของเด็กถ้ามี

ตัวอย่าง − จากตัวอย่างข้างต้นสำหรับโหนดที่มีค่า 1 โดยที่โหนดย่อยด้านซ้ายเท่านั้นที่มีอยู่ 4(1(8()())))(9)

กรณีที่ 3 − เมื่อโหนดมีชายด์ด้านขวาเท่านั้น เราจะใส่วงเล็บว่างสำหรับเด็กด้านซ้าย และมูลค่าของลูกที่เหมาะสมจะถูกวางและจะเรียกต้นไม้ย่อยถ้ามี

กรณีที่ 4 − เมื่อโหนดไม่มีลูก (โหนดใบ) เราจะไม่ใส่วงเล็บและใส่แต่ความคุ้มค่า

ตัวอย่าง − จากตัวอย่างด้านบนสำหรับโหนดที่มีค่า 5 ซึ่งไม่มีชายด์ 4(1(8(3)))(9(2)(5()())))

โปรแกรมแปลงไบนารีทรีเป็นสตริงด้วยวงเล็บ

//โปรแกรมแปลงไบนารีทรีเป็นสตริงด้วยวงเล็บ

ตัวอย่าง

#include ใช้เนมสเปซ std;struct Node { ข้อมูล int; โหนด *ซ้าย *ขวา;};โหนด* insertNode(ข้อมูล int){ โหนด* โหนด =(โหนด*)malloc(ขนาดของ(โหนด)); โหนด -> data =data; โหนด -> ซ้าย =โหนด -> ขวา =NULL; return (node);} เป็นโมฆะ ConveryBinaryTreeToString (โหนด * root, string&str) { if (root ==NULL) ส่งคืน; str.push_back(root->data + '0'); ถ้า (!root->left &&!root->right) กลับมา; str.push_back('('); ConveryBinaryTreeToString(root->left, str); str.push_back(')'); if (root->right) { str.push_back('('); ConveryBinaryTreeToString(root->right, str); str.push_back(')'); }}int main() { struct Node* root =insertNode(4); root->left =insertNode(1); root->right =insertNode(9); root->left->left =insertNode(8); root->left->left->left =insertNode(3); root->right->left =insertNode (2); รูท->ขวา->ขวา =insertNode(5); สตริง binaryTreeString =""; ConveryBinaryTreeToString (รูท, binaryTreeString); cout<<"สตริงที่มีการสั่งจองล่วงหน้าของไบนารีทรีที่มีวงเล็บคือ:"< 
ผลลัพธ์
 
สตริงที่มีการสั่งจองล่วงหน้าของไบนารีทรีที่มีวงเล็บคือ:4(1(8(3)))(9(2)(5))