ADT Cây nhị phân (Binary Tree) trong Cấu trúc dữ liệu

Khái niệm cơ bản

Cây nhị phân được định nghĩa là cây mà không nút nào có hơn hai nút con. Bậc cao nhất của bất kỳ nút nào là hai. Điều này nghĩa là bậc của cây nhị phân là 0, 1 hoặc 2.

Trong hình trên, cây nhị phân gồm gốc và hai cây con TreeLeft & TreeRight. Tất cả nút bên trái gốc thuộc cây con trái, nút bên phải thuộc cây con phải.

Cài đặt

Cây nhị phân tối đa hai nút con, ta có thể gán con trỏ trực tiếp cho chúng. Khai báo nút cây giống cấu trúc danh sách liên kết đôi: nút là cấu trúc chứa thông tin khóa và hai con trỏ (left, right) đến nút khác.

Khai báo nút cây nhị phân

typedef struct tree_node *tree_ptr;
struct tree_node {
    element_type element1;
    tree_ptr left1;
    tree_ptr right1;
};
typedef tree_ptr TREE;

Các loại Cây nhị phân

Cây nhị phân chặt chẽ (Strictly binary tree)

Là cây nhị phân mà mọi nút đều có 0 hoặc 2 nút con. Không có nút nào chỉ có 1 con.

Cây xiên (Skew tree)

Là cây nhị phân mà mọi nút trừ lá chỉ có một nút con. Có hai loại: xiên trái (left skewed) và xiên phải (right skewed).

Cây xiên trái (Left skewed binary tree)

Chỉ có nút con trái. Chỉ chứa cây con trái.

Cây xiên phải (Right skewed binary tree)

Chỉ có nút con phải. Chỉ chứa cây con phải.

Cây nhị phân đầy (Full binary tree / Proper binary tree)

Tất cả lá ở cùng một cấp, mọi nút không phải lá đều có đúng 2 con, và có số nút tối đa ở mọi cấp. Cây đầy chiều cao h có tối đa 2^h+1 - 1 nút.

Cây nhị phân hoàn chỉnh (Complete binary tree)

Mọi nút không phải lá có đúng 2 con, nhưng lá không nhất thiết ở cùng cấp. Cây hoàn chỉnh là cây mà mọi cấp đều đầy tối đa trừ cấp cuối; cấp cuối được lấp từ trái sang phải.

Cây nhị phân gần hoàn chỉnh (Almost complete binary tree)

Là cây mà mỗi nút có nút con phải thì cũng có nút con trái. Có nút con trái không bắt buộc phải có nút con phải.

Sự khác biệt giữa Cây tổng quát (General Tree) và Cây nhị phân

Cây tổng quát

• Không giới hạn số nút con.
• Đánh giá biểu thức khó khăn.

Cây nhị phân

• Tối đa 2 nút con.
• Đánh giá biểu thức đơn giản.

Ứng dụng của cây

• Thao tác biểu thức số học.
• Xây dựng bảng ký hiệu (symbol table).
• Phân tích cú pháp (Syntax Analysis).
• Viết ngữ pháp (Grammar).
• Tạo cây biểu thức (Expression Tree).