Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để in đường dẫn dài nhất tồn tại từ một nút lá đến một nút lá khác trong một cây nhị phân nhất định.
Nói cách khác, chúng ta phải in tất cả các nút xuất hiện trong đường kính của cây Nhị phân. Ở đây, đường kính (hoặc chiều rộng) cho một cây nhị phân cụ thể được định nghĩa là số nút trong đường dẫn dài nhất từ nút cuối này đến nút cuối khác.
Để giải quyết điều này, chúng tôi tính toán đường kính của cây nhị phân bằng cách sử dụng hàm chiều cao. Sau đó, chúng tôi tìm thấy con đường dài nhất trong phần bên trái của cây nhị phân và phần bên phải. Sau đó, cuối cùng để in các nút theo đường kính, chúng tôi in các nút phần bên trái, nút gốc và sau đó là các nút phần bên phải.
Ví dụ
#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;
} Đầu ra
97 84 45 22 57 26