Cây liên tục (Continuous Tree) trong C++

Một Cây liên tục được định nghĩa là cây mà trên bất kỳ đường đi nào từ nút gốc đến nút lá, giá trị hoặc trọng số của các nút sao cho hiệu tuyệt đối giữa nút cha và tất cả các nút con trực tiếp của nó luôn là 1.

Nếu chúng ta chọn bất kỳ nút nào trên đường đi từ gốc đến lá, thì

|trọng số nút - trọng số nút con trái| = |trọng số nút con trái - trọng số nút| = 1, điều này đúng cho nút con phải như nhau

|trọng số nút - trọng số nút con phải| = |trọng số nút con phải - trọng số nút| = 1

Sơ đồ

Hãy hiểu qua ví dụ.

Cây dưới đây là liên tục vì hiệu tuyệt đối giữa nút cha và nút con luôn là 1.

Cây dưới đây không đủ điều kiện là Cây liên tục.

Thuật toán kiểm tra cây có liên tục không

• Nếu root là NULL, trả về 1.
• Nếu là nút lá, trả về 1 vì cây đã liên tục trên đường đi đó.
• Nếu cây con trái rỗng, kiểm tra tính liên tục của nút hiện tại với nút con phải (tính hiệu tuyệt đối trọng số) và tiếp tục đệ quy cho cây con phải.
• Nếu cây con phải rỗng, kiểm tra tính liên tục của nút hiện tại với nút con trái (tính hiệu tuyệt đối trọng số) và tiếp tục đệ quy cho cây con trái.
• Ngược lại, tính hiệu tuyệt đối với trọng số nút con trái và phải và tiếp tục đệ quy cho cả hai cây con.

Mã giả

// Hàm kiểm tra cây có liên tục hay không
struct btreeNode { 
    int data; 
    btreeNode* left, * right; 
}; 

int isContinuous(btreeNode *root) { 
    // nếu nút là NULL trả về 1, điều kiện thoát
    if (root == NULL) 
        return 1; 
    // nếu nút lá được đạt thì cây phải liên tục trên đường đi này
    if (root->left == NULL && root->right == NULL) 
        return 1; 
    // nếu không có con trái
    if (root->left == NULL) 
        return (abs(root->data - root->right->data) == 1) && isContinuous(root->right); 
    // nếu không có con phải
    if (root->right == NULL) 
        return (abs(root->data - root->left->data) == 1) && isContinuous(root->left); 
    // tính hiệu tuyệt đối
    return abs(root->data - root->left->data) == 1 && abs(root->data - root->right->data) == 1 && 
           isContinuous(root->left) && isContinuous(root->right); 
}