Luận văn Thuật toán và chương trình thiết kế hệ công cụ trong toán học

Biểu diễn thường dùng nhất cho các cây nhị phân là sử dụng các mẩu tin với 2 liên kết cho mỗi nút . Thông thường chúng ta dùng liên kết được đặt tên là L(Left) và R(Right) để chỉ rằng thứ tự được chọn . Một số dạng đặc biệt của cây nhị phân: Cây lệch trái Cây lệch phải Cây zic-zắc Cây nhị phân hoàn chỉnh(Complete Binary Tree) Cây nhị phân đầy đủ là một trường hợp đặc biệt của cây nhị phân hoàn chỉnh . Như vậy trong các cây nhị phân cùng có số lượng nút như nhau thì cây nhị phân suy biến cho ta chiêù cao lớn nhất , còn cây nhị phân hoàn chỉnh thì có chiều cao nhỏ nhất và loại cây này là cây có dạng cân đối nhất . Đối với cây nhị phân ta có một số tính chất sau : Bổ đề: 1. Số lượng tối đa các nút ở mức i trên một cây nhị phân là 2i-1 ( i >=1) 2. Số lượng tối đa các nút ở trên một cây nhị phân có chiều cao h = 2h -1