Khái niệm cơ bản
Cây nhị phân được định nghĩa là cây trong đó không nút nào có thể có nhiều hơn hai nút con. Mức độ cao nhất của bất kỳ nút nào là hai. Điều này cho thấy mức độ của cây nhị phân là 0 hoặc một hoặc hai.
Trong hình trên, cây nhị phân bao gồm một gốc và hai cây con TreeLeft &TreeRight. Tất cả các nút bên trái cây nhị phân được biểu thị là cây con bên trái và tất cả các nút bên phải cây nhị phân được gọi là cây con bên phải.
Thực hiện
Một cây nhị phân có tối đa hai con; chúng ta có thể gán các con trỏ trực tiếp cho chúng. Việc khai báo các nút cây cũng giống như cấu trúc đối với danh sách được liên kết kép, trong đó một nút là một cấu trúc bao gồm thông tin khóa cộng với hai con trỏ (trái và phải) tới các 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 nghiêm ngặt
Cây nhị phân chính xác được định nghĩa là một cây nhị phân trong đó tất cả các nút sẽ có hoặc không hoặc hai nút con. Nó không bao gồm một nút con trong bất kỳ nút nào.
Cây xiên
Cây xiên được định nghĩa là cây nhị phân trong đó mọi nút ngoại trừ lá chỉ có một nút con. Có hai loại cây lệch, tức là cây nhị phân lệch trái và cây nhị phân lệch phải.
Cây nhị phân lệch trái
Một cây xiên trái có nút chỉ liên kết với nút con bên trái. Nó là một cây nhị phân chỉ chứa các cây con bên trái.
Cây nhị phân lệch phải
Một cây xiên bên phải có nút chỉ được liên kết với con bên phải. Nó là một cây nhị phân chỉ chứa các cây con bên phải.
Cây nhị phân đầy đủ hoặc cây nhị phân thích hợp
Cây nhị phân được định nghĩa là cây nhị phân đầy đủ nếu tất cả các lá ở cùng cấp và mọi nút không phải lá đều có đúng hai nút con và nó phải chứa số nút cao nhất có thể trong tất cả các cấp. Cây nhị phân đầy đủ có chiều cao h có tối đa 2h + 1 - 1 nút.
Cây nhị phân hoàn chỉnh
Mỗi nút không phải lá có đúng hai nút con nhưng tất cả các lá không nhất thiết phải thuộc cùng một cấp. Một cây nhị phân hoàn chỉnh được định nghĩa là một trong đó tất cả các cấp có số lượng nút cao nhất ngoại trừ cấp cuối cùng. Các phần tử cấp cuối cùng phải được điền theo hướng từ trái sang phải.
Cây nhị phân gần như hoàn chỉnh
Một cây nhị phân gần như hoàn chỉnh được định nghĩa là một cây trong đó mỗi nút có con bên phải cũng có con bên trái. Có con bên trái không cần nút để có con bên phải
Sự khác biệt giữa Cây chung và Cây nhị phân
Cây chung
- Cây chung không có giới hạn về số lượng cây con.
- Đánh giá bất kỳ biểu hiện nào trong các cây nói chung là một việc khó.
Cây nhị phân
- Một cây nhị phân có tối đa hai con
- Đánh giá biểu thức rất đơn giản trong cây nhị phân.
Ứng dụng của cây xanh
- Thao tác với biểu thức số học
- Xây dựng bảng ký hiệu
- Phân tích cú pháp
- Viết Ngữ pháp
- Tạo Cây Biểu thức