Sự khác biệt giữa cây nhị phân hoàn chỉnh và cây nhị phân đầy đủ

Cây nhị phân hoàn chỉnh vs Cây nhị phân đầy đủ

Cây nhị phân là một cây trong đó mỗi nút có một hoặc hai con. Trong cây nhị phân, một nút không thể có nhiều hơn hai con. Trong một cây nhị phân, trẻ em được đặt tên là trẻ em bên trái và trẻ em bên phải. Các nút con chứa tham chiếu đến cha mẹ của chúng. Cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp độ của cây nhị phân được lấp đầy hoàn toàn trừ cấp độ cuối cùng. Ở cấp độ chưa được lấp đầy, các nút được gắn bắt đầu từ vị trí ngoài cùng bên trái. Cây nhị phân đầy đủ là một cây trong đó mỗi nút trong cây có hai con ngoại trừ lá của cây.

Cây nhị phân đầy đủ là gì?

Cây nhị phân đầy đủ là một cây nhị phân trong đó mỗi nút trong cây có chính xác bằng 0 hoặc hai con. Nói cách khác, mỗi nút trong cây ngoại trừ lá có chính xác hai con. Hình 1 bên dưới mô tả một cây nhị phân đầy đủ. Trong cây nhị phân đầy đủ, số nút (n), số laves (l) và số nút nội bộ (i) có liên quan theo một cách đặc biệt để nếu bạn biết bất kỳ một trong số chúng, bạn có thể xác định hai nút còn lại các giá trị như sau:

1. Nếu một cây nhị phân đầy đủ có i nút nội bộ:

- Số lá l = i + 1

- Tổng số nút n = 2 * i + 1

2. Nếu một cây nhị phân đầy đủ có n nút:

- Số nút nội bộ i = (n-1) / 2

- Số lá l = (n + 1) / 2

3. Nếu một cây nhị phân đầy đủ có l lá:

- Tổng số nút n = 2 * l-1

- Số nút nội bộ i = l-1

Cây nhị phân hoàn chỉnh là gì?

Như trong hình 2, một cây nhị phân hoàn chỉnh là một cây nhị phân trong đó mọi cấp độ của cây được lấp đầy hoàn toàn trừ cấp độ cuối cùng. Ngoài ra, ở cấp độ cuối cùng, các nút phải được đính kèm bắt đầu từ vị trí ngoài cùng bên trái. Một cây nhị phân hoàn chỉnh có chiều cao h thỏa mãn các điều kiện sau:

- Từ nút gốc, mức trên mức cuối cùng biểu thị một cây nhị phân đầy đủ có chiều cao h-1

- Một hoặc nhiều nút ở cấp độ cuối có thể có 0 hoặc 1 con

- Nếu a, b là hai nút ở cấp trên mức cuối cùng, thì a có nhiều con hơn b khi và chỉ khi a nằm bên trái của b

Sự khác biệt giữa Cây nhị phân hoàn chỉnh và Cây nhị phân đầy đủ là gì?

Cây nhị phân hoàn chỉnh và cây nhị phân đầy đủ có một sự khác biệt rõ ràng. Trong khi cây nhị phân đầy đủ là cây nhị phân trong đó mọi nút có 0 hoặc 2 con, cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp của cây nhị phân được điền hoàn toàn trừ cấp cuối cùng. Một số cấu trúc dữ liệu đặc biệt như đống cần phải là cây nhị phân hoàn chỉnh trong khi chúng không cần phải là cây nhị phân đầy đủ. Trong cây nhị phân đầy đủ, nếu bạn biết số lượng nút tổng hoặc số lượng laves hoặc số nút nội bộ, bạn có thể tìm thấy hai nút kia rất dễ dàng. Nhưng một cây nhị phân hoàn chỉnh không có thuộc tính đặc biệt liên quan đến ba thuộc tính.