Bài 6. Cây nhị phân

BÀI 6 CÂY NHỊ PHÂN

Sau bài học này em sẽ:

1. Cấu trúc cây và cây nhị phân

Hoạt động 1. Tìm hiểu cấu trúc cây và cây nhị phân

Đọc, quan sát, thảo luận về khái niệm và cấu trúc cây. Với mỗi sơ đồ cây đã được mô tả trong hoạt động khởi động, hãy chỉ ra nút gốc, nút nhánh, nút lá và tính chiều cao của cây.

Các sơ đồ trong hoạt động khởi động đều có cấu trúc cây.

Cây (tree) bao gồm một tập hợp các nút (node) chứa thông tin, có kết nối với nhau, thường được gọi là quan hệ cha con. Mỗi nút cha có thể kết nối với nhiều nút con. Mỗi nút chỉ có thể kết nối với một nút cha. Mỗi cây có một nút đóng vai trò gốc (root). Nút gốc không có nút cha (Hình 6.2).

Một số định nghĩa và khái niệm liên quan đến cấu trúc cây:

Các định nghĩa trên được thể hiện trong Hình 6.2.

Cây nhị phân (binary tree) là cây mà mọi nút có tối đa hai nút con là nút con trái và nút con phải.

2. Biểu diễn cây nhị phân bằng mảng một chiều

Hoạt động 2. Tìm hiểu cây nhị phân và cách biểu diễn cây nhị phân bằng mảng một chiều

Cây nhị phân có thể được biểu diễn bằng mảng một chiều hoặc bằng nút liên kết.

Chúng ta xét một số trường hợp đặc biệt của cây nhị phân.

Dễ thấy với cây nhị phân hoàn hảo, mỗi mức k sẽ có đủ 2^k nút. Do vậy nếu cây hoàn hảo có chiều cao h thì tổng số nút sẽ là 1 + 2 + 2^2 + ... + 2^h = 2^(h+1) - 1.

Cây nhị phân hoàn hảo là trường hợp riêng của cây hoàn chỉnh, trong đó mức cao nhất của cây có đủ 2^h nút. Với cây hoàn chỉnh, số lượng nút tại mức h sẽ có từ 1 đến 2^h nút.

Riêng đối với cây nhị phân hoàn chỉnh, có thể biểu diễn thông tin của cây một cách đơn giản qua mảng một chiều. Có thể biểu diễn thông tin của cây nhị phân hoàn chỉnh bằng mảng một chiều như sau:

Cây nhị phân hoàn chỉnh được đánh chỉ số như sau: bắt đầu từ 0 (nút gốc), sau đó đánh chỉ số lần lượt theo các nút ở từng mức, từ trái sang phải, cho đến nút cuối cùng của cây (Hình 6.6). Cụ thể như sau:

Ngược lại, nếu cho trước mảng một chiều bất kì, khi đó có thể dễ dàng thiết lập cây nhị phân hoàn chỉnh tương ứng với mảng này. Nút gốc của cây sẽ tương ứng với phần tử đầu tiên của mảng, với chỉ số 0. Các phần tử tiếp theo tương ứng với các nút của cây theo thứ tự từng mức từ trái sang phải. Hình 6.7 mô tả quan hệ cha con giữa các phần tử của mảng nếu biểu diễn cây nhị phân.

Cây nhị phân hoàn chỉnh có thể được biểu diễn bằng mảng một chiều có số phần tử bằng số nút của cây.

Lưu ý: Cây nhị phân tổng quát có thể được biểu diễn bằng mảng một chiều bằng cách bổ sung các nút có giá trị None để tạo thành cây hoàn chỉnh, sau đó biểu diễn bằng mảng như đã nêu trên. Ví dụ sau minh hoạ cho ý tưởng này: Cây rỗng cũng có thể được biến đổi thành cây nhị phân hoàn chỉnh bằng cách bổ sung các nút giả (nút None). Cây nhị phân tổng quát đều có thể được biến đổi thành cây nhị phân hoàn chỉnh bằng cách bổ sung các nút giả (nút None). Những cây nhị phân như vậy được gọi là cây nhị phân hoàn chỉnh đã biến đổi (có thể có các nút giả None) để phân biệt với cây nhị phân hoàn chỉnh (không có các nút None). Như vậy, cây nhị phân hoàn chỉnh có thể được biểu diễn bằng mảng một chiều, còn cây nhị phân tổng quát cũng có thể được biểu diễn bằng mảng một chiều sau khi bổ sung các nút None. Trong bài học này chỉ làm việc với cây nhị phân hoàn chỉnh, còn cây nhị phân hoàn chỉnh đã được biến đổi sẽ được đề cập trong các bài học sau.

3. Các thuật toán duyệt cây nhị phân

Hoạt động 3. Tìm hiểu một số thuật toán duyệt cây nhị phân

Trao đổi, thảo luận và thực hiện các thuật toán duyệt cây nhị phân. Bài toán đặt ra là cần duyệt tất cả các nút của cây nhị phân, mỗi nút duyệt một lần.

Trong phần này tất cả các cây nhị phân đều được hiểu là cây nhị phân hoàn chỉnh và được biểu diễn bằng mảng một chiều A cho trước.

a) Duyệt trước (preorder traversal)

Cây con có nút gốc v được gọi là "cây v" (Hình 6.9). Ý tưởng của phương pháp duyệt trước là bắt đầu từ nút gốc, sau đó duyệt cây con trái. Duyệt xong cây con trái thì chuyển sang duyệt cây con phải. Đoạn mã giả sau là thuật toán duyệt trước cây v. Lời gọi duyệt chính là preorder(root).

1 preorder(cây v) # Duyệt trước (gốc-trái-phải) cây v
2 Nếu cây khác rỗng:
3     Duyệt nút v # gốc
4     preorder(cây con trái của nút v) # trái
5     preorder(cây con phải của nút v) # phải

Hàm cài đặt thuật toán duyệt trước trên Python có dạng preorder(A, k), trong đó k là chỉ số nút bắt đầu duyệt, A là mảng biểu diễn cây nhị phân tương ứng.

1 def preorder(A, k):
2     if k < len(A) and A[k] != None:
3         print(A[k], end=" ")
4         preorder(A, left(k))
5         preorder(A, right(k))

Chú ý các hàm left(), right() đã được xác định từ trước; ví dụ như sau:

1 def left(i):
2     return 2*i + 1
3 def right(i):
4     return 2*i + 2

Xét ví dụ cây nhị phân hoàn chỉnh. Với ví dụ này thì lệnh duyệt trước bắt đầu từ gốc sẽ duyệt các nút của cây lần lượt theo mũi tên trên Hình 6.10.

b) Duyệt sau (postorder traversal)

Ý tưởng của phương pháp duyệt sau là duyệt toàn bộ cây con trái, sau đó duyệt cây con phải, cuối cùng duyệt nút gốc. Đoạn mã giả của thuật toán duyệt sau bắt đầu từ nút v như sau:

1 postorder(cây v) # Duyệt sau (trái-phải-gốc) cây v
2 Nếu cây khác rỗng:
3     postorder(cây con trái của nút v) # trái
4     postorder(cây con phải của nút v) # phải
5     Duyệt nút v # gốc

Lời gọi duyệt chính là postorder(root).

Hàm cài đặt trên Python như sau:

1 def postorder(A, k):
2     if k < len(A) and A[k] != None:
3         postorder(A, left(k))
4         postorder(A, right(k))
5         print(A[k], end=" ")

Với ví dụ trên thì thuật toán duyệt sau sẽ duyệt các nút của cây bắt đầu từ gốc lần lượt theo mũi tên trên Hình 6.11.

c) Duyệt giữa (inorder traversal)

Ý tưởng của phương pháp duyệt giữa là duyệt cây con trái trước, sau đó duyệt nút gốc, cuối cùng duyệt cây con phải. Đoạn mã giả của thuật toán duyệt giữa bắt đầu từ nút v như sau:

1 inorder(cây v) # Duyệt giữa (trái-gốc-phải) cây v
2 Nếu cây khác rỗng:
3     inorder(cây con trái của nút v) # trái
4     Duyệt nút v # gốc
5     inorder(cây con phải của nút v) # phải

Lời gọi duyệt chính là inorder(root).

Hàm cài đặt trên Python như sau:

1 def inorder(A, k):
2     if k < len(A) and A[k] != None:
3         inorder(A, left(k))
4         print(A[k], end=" ")
5         inorder(A, right(k))

Với ví dụ trên thì thuật toán duyệt giữa sẽ duyệt các nút của cây lần lượt theo mũi tên trên Hình 6.12.

Các thuật toán duyệt cây nhị phân bao gồm duyệt trước, duyệt sau và duyệt giữa.

LUYỆN TẬP

VẬN DỤNG