Giả sử chúng ta có một cây nhị phân đặc biệt, có các nút lá được kết nối để tạo thành một danh sách liên kết kép hình tròn. Chúng ta phải tìm chiều cao của nó. Vì vậy, con trỏ bên trái của lá ngoài cùng bên trái sẽ hoạt động như con trỏ trước của danh sách được liên kết kép hình tròn và con trỏ bên phải của nó sẽ hoạt động như con trỏ tiếp theo của danh sách được liên kết.
Trong trường hợp này, chiến lược tìm độ cao tương tự như cây tìm kiếm nhị phân thông thường. Chúng tôi tính toán đệ quy chiều cao của các cây con bên trái và bên phải của một nút và gán chiều cao cho nút là tối đa của hai con + 1. Nhưng ở đây các lá là các phần tử của danh sách liên kết đôi hình tròn. Vì vậy, đối với một nút là nút lá, chúng tôi kiểm tra xem nút bên trái của bên phải đang trỏ đến nút và bên trái của nút bên phải đang trỏ đến chính nút đó.
Ví dụ
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
bool isLeafNode(Node* node) {
return node->left && node->left->right == node && node->right && node->right->left == node;
}
int findHeight(Node* node) {
if (node == NULL)
return 0;
if (isLeafNode(node))
return 1;
return 1 + max(findHeight(node->left), findHeight(node->right));
}
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->left->left->left = getNode(6);
Node *L1 = root->left->left->left;
Node *L2 = root->left->right;
Node *L3 = root->right;
L1->right = L2, L2->right = L3, L3->right = L1;
L3->left = L2, L2->left = L1, L1->left = L3;
cout << "Height of tree is: " << findHeight(root);
} Đầu ra
Height of tree is: 4