ความกว้างสูงสุดของไบนารีทรีใน C++

คำชี้แจงปัญหา

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

พิจารณาใต้ต้นไม้ −

 10 / \ 7 4 / \ \ 9 2 1 / \ 2 51. ความกว้างที่ระดับ 1:12. ความกว้างที่ระดับ 2:23. ความกว้างที่ระดับ 3:34. ความกว้างที่ระดับ 4:2สำหรับคำตอบข้างต้นคือ 3.

อัลกอริทึม

ตัวอย่าง

#include ใช้เนมสเปซ std;struct node { สาธารณะ:ข้อมูล int; โหนด* ซ้าย; โหนด* ขวา;};int getWidth (โหนด* รูท ระดับ int);ความสูงของ int (โหนด* โหนด);โหนด* โหนดใหม่(ข้อมูล int);int getMaxWidth (โหนด* รูท){ int maxWidth =0; ความกว้างภายใน; int ชั่วโมง =ความสูง(ราก); int ฉัน; สำหรับ (i =1; i <=h; ++i) { width =getWidth(root, i); ถ้า (ความกว้าง> maxWidth) { maxWidth =ความกว้าง; } } ส่งคืน maxWidth;}int getWidth (โหนด * root ระดับ int) { if (root ==NULL) { ส่งคืน 0; } ถ้า (ระดับ ==1) { กลับ 1; } else if (ระดับ> 1) { ส่งคืน getWidth(root->left, ระดับ - 1) + getWidth(root->right, ระดับ - 1); }} ความสูง int (โหนด * โหนด) { ถ้า (โหนด ==NULL) { กลับ 0; } int lHeight =ความสูง (โหนด -> ซ้าย); int rHeight =ความสูง (โหนด -> ขวา); ผลตอบแทน (lHeight> rHeight)? (lHeight + 1):(rHeight + 1);}node* newNode(ข้อมูล int){ โหนด* โหนด =โหนดใหม่(); โหนด -> data =data; โหนด -> ซ้าย =NULL; โหนด -> ขวา =NULL; return(Node);}int main(){ โหนด *root =newNode(10); root->left =newNode(7); root->right =newNode(4); root->left->left =newNode(9); root->left->right =newNode(2); root->right->right =newNode(1); root->right->right->left =newNode (2); รูท->ขวา->ขวา->ขวา =newNode(5); cout<<"ความกว้างสูงสุด =" < 
ผลลัพธ์
 
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 
ความกว้างสูงสุด =3