สมมติว่าเรามีไบนารีทรีแบบพิเศษ ซึ่งโหนดลีฟเชื่อมต่อกันเพื่อสร้างรายการที่เชื่อมโยงเป็นวงกลมแบบทวีคูณ เราต้องหาความสูงของมัน ดังนั้นตัวชี้ด้านซ้ายของลีฟส่วนใหญ่จะทำหน้าที่เป็นตัวชี้ก่อนหน้าของรายการที่เชื่อมโยงแบบวงกลมเป็นสองเท่า และตัวชี้ด้านขวาจะทำหน้าที่เป็นตัวชี้ถัดไปของรายการที่เชื่อมโยง
ในกรณีนี้ กลยุทธ์การค้นหาความสูงจะคล้ายกับแผนผังการค้นหาไบนารีปกติ เราคำนวณความสูงของทรีย่อยด้านซ้ายและขวาของโหนดซ้ำๆ และกำหนดความสูงให้กับโหนดเป็นค่าสูงสุดของโหนดลูกทั้งสอง + 1 แต่ในที่นี้ ใบไม้เป็นองค์ประกอบของรายการที่เชื่อมโยงเป็นวงกลมแบบทวีคูณ ดังนั้นสำหรับโหนดที่จะเป็นโหนดปลายสุด เราตรวจสอบว่าโหนดทางซ้ายชี้ไปที่โหนดและทางขวาชี้ไปที่โหนดเองหรือไม่
ตัวอย่าง
#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);
} ผลลัพธ์
Height of tree is: 4
