Chúng ta được cho một cây nhị phân. Mục tiêu là tìm chu trình dài nhất trong cây đã cho. Chúng ta sẽ làm điều này bằng cách tìm chiều cao tối đa của cây con trái và cây con phải từ nút gốc và nối các đường đi dài nhất này để nhận được chu trình dài nhất.
Đối với cây trên, chu trình dài nhất là 1-2-3-4-7-6 hoặc 1-6-7-4-3-2-1. Độ dài là 6.
Đầu vào − cây
Đầu ra − Chu trình dài nhất là − 5
Giải thích − Chiều cao tối đa của cây con trái là 3 và của cây con phải là 1. Độ dài chu trình trở thành 3+1+1=5. Chu trình là 1-2-3-4-6 hoặc 1-6-4-3-2.
Đầu vào − cây
Đầu ra − Chu trình dài nhất là − 7
Giải thích − Chiều cao tối đa của cây con trái là 3 và của cây con phải là 3. Độ dài chu trình trở thành 3+3+1=7. Chu trình là 5-4-2-1-8-7-6 hoặc 5-6-7-8-1-2-4-5.
Phương pháp sử dụng trong chương trình dưới đây
- Tạo lớp treenode có thành viên dữ liệu public: int data cho trọng số nút, con trỏ left và right treenode trỏ đến các nút khác.
- Hàm newNode(int data) nhận data làm tham số và tạo nút với con trỏ left, right là NULL.
- Tạo cây bằng cách gọi hàm newnode().
- Hàm maxheight(treenode* root) nhận gốc cây và trả về chiều cao tối đa của cây có gốc tại root.
- Hàm này kiểm tra nếu root là NULL, nghĩa là chiều cao là 0, trả về 0.
- lheight và rheight tính chiều cao cây con trái và phải của nút root, bằng lời gọi đệ quy maxheight(root->left); và maxheight(root->right);
- Trả về giá trị lớn nhất bằng cách so sánh lheight và rheight.
- Trong main, lưu giá trị chiều cao tối đa của cây con trái và phải của nút cây.
- Bây giờ chu trình dài nhất là tổng của maxlheight + maxrheight + 1 để bao gồm chính gốc.
- In độ dài chu trình làm kết quả.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
// Lớp cho cây
class treenode {
public:
int data;
treenode* left;
treenode* right;
};
// Tìm chiều cao tối đa giữa cây con trái và phải của gốc hiện tại
int maxheight(treenode* root) {
if (root == NULL)
return 0;
else {
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
// Tìm chiều cao tối đa
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
// Tạo nút cây
treenode* newNode(int data) {
treenode* Node = new treenode();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
int main() {
treenode* root = newNode(6);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(7);
root->left->right->right->left = newNode(2);
int maxlheight = maxheight(root->left);
int maxrheight = maxheight(root->right);
// Lưu ý: code gốc có dòng trùng lặp maxlheight/maxrheight với maxDepth
cout << "Chu trình dài nhất: " << maxlheight + maxrheight + 1;
return 0;
}
Kết quả
Chu trình dài nhất: 6