Chương trình C++ kiểm tra cây nhị phân có phải cây AVL hay không

Cây AVL là cây tìm kiếm nhị phân tự cân bằng (self-balancing BST) nơi độ chênh lệch chiều cao giữa cây con trái và phải không quá 1 đối với mọi nút.

Đây là chương trình C++ kiểm tra xem một cây nhị phân cho trước có phải cây AVL hay không.

Thuật toán

Bắt đầu hàm AVL() trả về true nếu cây là AVL, ngược lại false.
  nếu (root == NULL)
    trả về 1
  leftheight = height(root->left)
  rightheight = height(root->right)
  nếu (abs(leftheight - rightheight) <= 1 && AVL(root->left) && AVL(root->right))
    trả về 1
  trả về 0
Kết thúc

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

class nod { // khai báo nút
public:
    int data;
    nod* l;
    nod* r;
};

nod* newNod(int d) { // tạo nút mới
    nod* Nod = new nod();
    Nod->data = d;
    Nod->l = NULL;
    Nod->r = NULL;
    return Nod;
}

int max(int x, int y) { // trả về max của hai giá trị
    return (x >= y) ? x : y;
}

int height(nod* node) { // lấy chiều cao: số nút trên đường đi dài nhất từ gốc đến lá
    if (node == NULL)
        return 0;
    return 1 + max(height(node->l), height(node->r));
}

bool AVL(nod *root) {
    int lh, rh;
    if (root == NULL)
        return 1;
    lh = height(root->l); // chiều cao bên trái
    rh = height(root->r); // chiều cao bên phải
    if (abs(lh - rh) <= 1 && AVL(root->l) && AVL(root->r))
        return 1;
    return 0;
}

int main() {
    // nhập các nút của cây
    nod *root = newNod(7);
    root->l = newNod(6);
    root->r = newNod(12);
    root->l->l = newNod(4);
    root->l->r = newNod(5);
    root->r->r = newNod(13);
    if (AVL(root))
        cout << "Cây là cây AVL" << endl;
    else
        cout << "Cây KHÔNG phải cây AVL" << endl;

    nod *root1 = newNod(7);
    root1->l = newNod(6);
    root1->r = newNod(12);
    root1->l->l = newNod(4);
    root1->l->r = newNod(5);
    root1->r->r = newNod(13);
    root1->r->r->r = newNod(26);
    if (AVL(root1))
        cout << "Cây là cây AVL" << endl;
    else
        cout << "Cây KHÔNG phải cây AVL" << endl;
    return 0;
}

Kết quả

Cây là cây AVL
Cây KHÔNG phải cây AVL