ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อพิมพ์เส้นทางที่ยาวที่สุดจากโหนดปลายสุดไปยังโหนดปลายสุดอื่นในไบนารีทรีที่กำหนด
กล่าวอีกนัยหนึ่ง เราต้องพิมพ์โหนดทั้งหมดที่ปรากฏในเส้นผ่านศูนย์กลางของต้นไม้ไบนารี ในที่นี้ เส้นผ่านศูนย์กลาง (หรือความกว้าง) สำหรับไบนารีทรีหนึ่งๆ ถูกกำหนดให้เป็นจำนวนโหนดในเส้นทางที่ยาวที่สุดจากโหนดปลายด้านหนึ่งไปยังอีกโหนดหนึ่ง
เพื่อแก้ปัญหานี้ เราคำนวณเส้นผ่านศูนย์กลางของไบนารีทรีโดยใช้ฟังก์ชันความสูง จากนั้นเราจะพบเส้นทางที่ยาวที่สุดในส่วนด้านซ้ายของไบนารีทรีและส่วนด้านขวา จากนั้นในที่สุด เพื่อพิมพ์โหนดที่มีเส้นผ่านศูนย์กลาง เราพิมพ์โหนดส่วนด้านซ้าย โหนดรูท และโหนดส่วนด้านขวา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* create_node(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){
if (root == NULL)
return 0;
int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
if (ans < 1 + left_tree_height + right_tree_height){
ans = 1 + left_tree_height + right_tree_height;
k = root;
lh = left_tree_height;
rh = right_tree_height;
}
return 1 + max(left_tree_height, right_tree_height);
}
void print_roottonode(int ints[], int len, int f){
int i;
if (f == 0){
for (i = len - 1; i >= 0; i--) {
printf("%d ", ints[i]);
}
}
else if (f == 1) {
for (i = 0; i < len; i++) {
printf("%d ", ints[i]);
}
}
}
void print_pathr(Node* node, int path[], int pathLen, int max, int& f){
if (node == NULL)
return;
path[pathLen] = node->data;
pathLen++;
if (node->left == NULL && node->right == NULL) {
if (pathLen == max && (f == 0 || f == 1)) {
print_roottonode(path, pathLen, f);
f = 2;
}
}
else {
print_pathr(node->left, path, pathLen, max, f);
print_pathr(node->right, path, pathLen, max, f);
}
}
void calc_diameter(Node* root){
if (root == NULL)
return;
int ans = INT_MIN, lh = 0, rh = 0;
int f = 0;
Node* k;
int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
int lPath[100], pathlen = 0;
print_pathr(k->left, lPath, pathlen, lh, f);
printf("%d ", k->data);
int rPath[100];
f = 1;
print_pathr(k->right, rPath, pathlen, rh, f);
}
int main(){
struct Node* root = create_node(12);
root->left = create_node(22);
root->right = create_node(33);
root->left->left = create_node(45);
root->left->right = create_node(57);
root->left->right->left = create_node(26);
root->left->right->right = create_node(76);
root->left->left->right = create_node(84);
root->left->left->right->left = create_node(97);
calc_diameter(root);
return 0;
} ผลลัพธ์
97 84 45 22 57 26
