ให้เราพิจารณาว่าเรามีโหนดรูทของไบนารีทรี ภารกิจคือการค้นหาและส่งคืนผลรวมของการเอียงของทุกโหนด
เอียง ของไบนารีทรีไม่ได้เป็นเพียงการสร้างไบนารีทรีโดยการค้นหาความแตกต่างที่แน่นอนของโหนดย่อยในทรีย่อยด้านซ้ายและทรีย่อยด้านขวาในแต่ละระดับ ในระดับใดระดับหนึ่ง โหนดที่ไม่มีโหนดย่อย เราเพียงแค่เอียงโดยแทนที่โหนดนั้นเป็นศูนย์
ตัวอย่าง
ป้อนข้อมูล
เอาต์พุต:15
คำอธิบาย: การหาความเอียงในทุกระดับของไบนารีทรีที่กำหนด
ความเอียงของโหนด 3 =0
ความเอียงของโหนด 5 =0
ความเอียงของโหนด 7 =0
ความเอียงของโหนด 2 =abs(3-5)=2
ความเอียงของโหนด 9 =abs(0-7)=7
ความเอียงของโหนด 4 =abs((3+5+2)- (9+7))=6
ผลรวมของการเอียงของโหนดทั้งหมดคือ =2+7+6=15
แนวทางในการแก้ปัญหานี้
วิธีง่ายๆ ในการแก้ปัญหานี้คือการใช้การข้ามผ่าน Post Order Breadth First Search
ขณะสำรวจต้นไม้ไบนารี เราจะพยายามหาผลรวมของโหนดทั้งหมดของทรีย่อยทางซ้าย และทรีย่อยทางขวา เมื่อพบผลรวมแล้ว เราจะพบความเอียงของโหนดทั้งหมดโดยการคำนวณผลต่างสัมบูรณ์ของผลรวมด้านซ้ายและผลรวมด้านขวาของทรีย่อย
- ใช้ไบนารีทรี ซึ่งจะเป็นอินพุต
- ฟังก์ชันจำนวนเต็ม sumNodes(treenode*node) รับโหนดรูทของทรีและคืนค่าผลรวมของทรีย่อยด้านซ้ายและทรีย่อยด้านขวา
- ฟังก์ชันจำนวนเต็ม findTilt(treenode*root) รับโหนดรูทเป็นพารามิเตอร์อินพุตและส่งกลับผลรวมของการเอียงของโหนดทั้งหมด
ตัวอย่าง
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int sumNodes(treenode * root, int & sum) {
if (root == NULL) return 0;
int lsum = sumNodes(root -> left, sum);
int rsum = sumNodes(root -> right, sum);
sum += abs(lsum - rsum);
return lsum + rsum + root -> data;
}
int findTilt(treenode * root) {
int sum = 0;
if (root == NULL) {
return 0;
}
sumNodes(root, sum);
return sum;
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(9);
root -> left -> right = createNode(5);
root -> left -> left = createNode(3);
root -> right -> right = createNode(7);
cout << findTilt(root) << endl;
return 0;
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
15
ในไบนารีทรีที่กำหนด ผลรวมของการเอียงของโหนดทั้งหมดในทุกระดับของทรีคือ 15
