Cây nhị phân là cấu trúc dữ liệu phân cấp trong đó mỗi nút có nhiều nhất hai nút con. Hướng dẫn này sẽ chỉ ra cách tính toán cấp độ cây nhị phân và số lượng nút. Chúng tôi cũng sẽ kiểm tra mối quan hệ giữa cấp độ cây và số lượng nút
2. Cấp độ cây nhị phân
Trong cây nhị phân, mỗi nút có 3 phần tử. một phần tử dữ liệu để giữ một giá trị dữ liệu và hai con trỏ con để chỉ các phần tử con bên trái và bên phải của nó
Nút trên cùng của cây nhị phân là nút gốc. Mức của một nút là số cạnh dọc theo đường dẫn duy nhất giữa nó và nút gốc. Do đó, nút gốc có mức 0. Nếu nó có con, cả hai đều có cấp độ 1
Cấp của cây nhị phân là số cấp cao nhất trong số tất cả các nút. Ví dụ: chúng ta có thể sử dụng 5 nút để xây dựng cây nhị phân có số cấp là 2
3. Tính toán cấp độ cây và số lượng nút
Để tính cấp của cây nhị phân, chúng ta có thể duyệt cây theo cấp. Chúng tôi bắt đầu với nút gốc là cấp 0. Sau đó, chúng tôi truy cập mọi nút trên một cấp độ trước khi chuyển sang cấp độ khác. Ví dụ: trình tự duyệt từng cấp của cây ví dụ trên là 1, 2, 3, 4, 5
Duyệt cây nhị phân theo cấp độ cũng là cách tiếp cận tìm kiếm theo chiều rộng [BFS]. Để thực hiện được quá trình truyền tải này, chúng ta có thể sử dụng một cấu trúc dữ liệu để đảm bảo thứ tự của quá trình truyền tải
Mỗi phần tử của hàng đợi chứa hai giá trị, nút cây hiện tại và số cấp của nút cây hiện tại
Sau khi duyệt, số cấp tối đa sẽ là số cấp của cây. Chúng ta cũng có thể sử dụng bộ đếm để đếm số nút trong quá trình truyền tải
Trong thuật toán này, chúng tôi bắt đầu với nút . Đầu tiên, chúng ta đặt nút và số cấp của nó vào hàng đợi . Sau đó, chúng tôi sử dụng một vòng lặp để duyệt qua tất cả các nút của cây theo cấp độ của chúng.
Trong mỗi lần lặp, chúng tôi tăng cấp của nút cây hiện tại lên 1 và liên kết nó với nút con trái và phải của nút. Trong quá trình truyền tải, chúng tôi ghi lại số cấp tối đa. Sau khi chúng tôi truy cập tất cả các nút của cây, giá trị lớn nhất là cấp độ của cây nhị phân
Nếu cây nhị phân chứa các nút, thời gian chạy tổng thể của thuật toán này là vì chúng ta chỉ truy cập mỗi nút một lần.
4. Số lượng nút tối thiểu và tối đa
Chúng ta có thể sử dụng thuật toán trên để tính chính xác số nút của cây nhị phân và số cấp của nó. Hơn nữa, chúng ta có thể xác định số nút tối thiểu và tối đa cho cây nhị phân có cấp bằng phân tích lý thuyết.
4. 1. Số lượng nút tối thiểu
Dễ dàng thấy rằng chúng ta cần ít nhất một nút cho mỗi cấp để xây dựng cây nhị phân có cấp . Do đó, số nút tối thiểu của cây nhị phân có cấp là . Cây nhị phân này hoạt động giống như cấu trúc dữ liệu danh sách được liên kết.
Chúng ta có thể kết luận số lượng nút tối thiểu với định lý sau
4. 2. Số nút tối đa
Để xây dựng cây nhị phân cấp với số nút tối đa, chúng ta cần đảm bảo tất cả các nút bên trong đều có hai nút con. Ngoài ra, tất cả các nút lá phải ở mức .
Ví dụ, ở mức 0, chúng ta chỉ có nút gốc. Ở mức 1, chúng ta có 2 nút là con của gốc. Tương tự ta có 4 nút cấp 2 là con của các nút cấp 1
Dựa trên quan sát này, chúng ta có thể thấy rằng mỗi cấp độ tăng gấp đôi số nút so với cấp độ trước đó. Điều này là do mỗi nút bên trong có hai nút con. Do đó, số nút tối đa của cây nhị phân cấp là . Chúng tôi cũng gọi loại cây nhị phân này là.
Chúng ta có thể kết luận số lượng nút tối đa với định lý sau
5. Chứng minh bằng quy nạp
Ta cũng có thể dùng quy nạp để chứng minh Định lý 2. Đối với trường hợp cơ sở, trong đó , cây nhị phân cấp 0 chỉ là một nút gốc duy nhất không có nút con nào. Ngoài ra, khi , chúng ta có . Do đó, trường hợp cơ sở thỏa mãn giả thuyết quy nạp.
Trong bước quy nạp, đặt là cây nhị phân cấp . Đối với nút gốc của , cả cây con bên phải và cây con bên trái của nó đều có cấp độ .
Tổng số nút của là tổng của hai cây con và nút gốc của nó. Do đó, chứa tối đa nút. Giả thuyết đúng với , và do đó định lý được chứng minh.
6. Phần kết luận
Bài viết này hướng dẫn cách tính cấp và số nút cho cây nhị phân. Chúng tôi cũng cung cấp kết quả lý thuyết về số nút tối thiểu và tối đa cho cây nhị phân cấp . Cuối cùng, chúng tôi đã sử dụng phương pháp quy nạp để chứng minh rằng số nút tối đa cho một cây nhị phân cấp là .
tác giả dưới cùng
Nếu bạn có một vài năm kinh nghiệm trong Khoa học máy tính hoặc nghiên cứu và bạn muốn chia sẻ kinh nghiệm đó với cộng đồng, hãy xem Nguyên tắc đóng góp của chúng tôi