Bỏ qua đến nội dung chính
Mục lục

Cây nhị phân (binary tree) trong Python: ba cách duyệt

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 7/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 7 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Cây nhị phân (binary tree) là cấu trúc mà mỗi nút có tối đa hai nút con, một bên trái và một bên phải. Bạn gặp nó ở thực đơn tổng đài "bấm 1, bấm 2", ở biểu thức tính tiền, và ở nhiều cấu trúc tìm kiếm dựng trên cây.

Cần biết trước: danh sách liên kết, đệ quy và None.

Cây và cây nhị phân

Nút của danh sách liên kết trỏ tới một nút sau. Nút của cây có thể trỏ tới nhiều nút con, và nút của cây nhị phân có đúng hai chỗ: trai và phai, chỗ nào trống thì là None. Nút trên cùng là gốc, nút không có con nào là lá. Thực đơn tổng đài dưới đây có gốc "Tổng đài", bấm 1 sang trái, bấm 2 sang phải:

python
class Node:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri = gia_tri
        self.trai = trai
        self.phai = phai

ban_hang = Node("Bán hàng", Node("Khóa học"), Node("Sách"))
ho_tro = Node("Hỗ trợ", Node("Cloud"), Node("Tài khoản"))
goc = Node("Tổng đài", ban_hang, ho_tro)
print(goc.trai.gia_tri, "|", goc.phai.gia_tri)
print(goc.phai.trai.gia_tri, goc.phai.trai.trai)

KẾT QUẢ

Bán hàng | Hỗ trợ
Cloud None

goc.phai.trai là bấm 2 rồi bấm 1, tới lá "Cloud", và lá không có con nên .trai là None. Mỗi nút cùng các nút bên dưới nó lại là một cây nhỏ hơn, gọi là cây con. Đổi goc.phai.trai.gia_tri thành goc.trai.phai.gia_tri rồi chạy lại: dòng hai in Sách None.

Duyệt trước bằng đệ quy

Duyệt cây là đi qua mọi nút, mỗi nút một lần. Vì cây con cũng là cây, hàm duyệt gọi lại chính nó cho hai cây con, và dừng khi gặp None. Duyệt trước (preorder) lấy gốc trước, rồi cả cây con trái, rồi cả cây con phải:

python
class Node:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def truoc(nut):
    if nut is None:
        return []
    return [nut.gia_tri] + truoc(nut.trai) + truoc(nut.phai)

goc = Node("Tổng đài",
           Node("Bán hàng", Node("Khóa học"), Node("Sách")),
           Node("Hỗ trợ", Node("Cloud"), Node("Tài khoản")))
print(truoc(goc))

KẾT QUẢ

['Tổng đài', 'Bán hàng', 'Khóa học', 'Sách', 'Hỗ trợ', 'Cloud', 'Tài khoản']

Đó là thứ tự bạn đọc thực đơn từ trên xuống: một mục, rồi hết các mục con của nó, rồi mới sang mục kế bên. Điều kiện dừng if nut is None: return [] lo cả lá lẫn chỗ trống, nên hàm không cần hỏi nút có con hay không.

Duyệt giữa và duyệt sau

Ba cách duyệt chỉ khác ở chỗ đặt gốc: duyệt trước đặt gốc đầu tiên, duyệt giữa (inorder) đặt gốc giữa hai cây con, duyệt sau (postorder) đặt gốc cuối cùng. Cây dưới đây là phép tính tiền hai phần đồ uống, mỗi phần một ly 29000 đồng và một ly 32000 đồng:

python
class Node:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def giua(nut):
    if nut is None:
        return []
    return giua(nut.trai) + [nut.gia_tri] + giua(nut.phai)
def sau(nut):
    if nut is None:
        return []
    return sau(nut.trai) + sau(nut.phai) + [nut.gia_tri]
phep_tinh = Node("*", Node("+", Node(29000), Node(32000)), Node(2))
print(giua(phep_tinh))
print(sau(phep_tinh))

KẾT QUẢ

[29000, '+', 32000, '*', 2]
[29000, 32000, '+', 2, '*']

Duyệt giữa ra đúng cách viết phép tính nhưng mất dấu ngoặc, nên đọc thành 29000 + 32000 * 2 là sai nghĩa. Duyệt sau ra đúng thứ tự tính: gặp số thì giữ lại, gặp phép thì tính trên hai số vừa giữ, cộng trước rồi mới nhân. Phép tính chỉ đúng khi một phép được làm sau khi cả hai vế của nó đã có kết quả, và đó chính là thứ tự gốc cuối cùng.

Chiều cao và số nút

Chiều cao của cây là số nút trên đường dài nhất từ gốc xuống một lá, cây rỗng cao 0 và một lá cao 1. Cả chiều cao lẫn số nút đều tính từ hai cây con theo cùng khuôn đệ quy:

python
class Node:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def so_nut(nut):
    if nut is None:
        return 0
    return 1 + so_nut(nut.trai) + so_nut(nut.phai)
def chieu_cao(nut):
    if nut is None:
        return 0
    return 1 + max(chieu_cao(nut.trai), chieu_cao(nut.phai))
ban_hang = Node("Bán hàng", Node("Khóa học"))
goc = Node("Tổng đài", ban_hang, Node("Hỗ trợ"))
print(so_nut(goc), chieu_cao(goc))

KẾT QUẢ

4 3

Đổi Node("Khóa học") thành Node("Khóa học", Node("Python")) rồi chạy lại: in 5 4. Các hàm của bài đều ghé mỗi nút một lần. so_nut() và chieu_cao() là O(n) với n nút, còn ba hàm duyệt ghép list ở mỗi nút nên tốn thêm phép sao chép, tới O(n²) trên cây lệch hẳn. Một cây lệch hẳn về một phía thì giống danh sách liên kết, chiều cao bằng số nút, và cây sâu vài nghìn tầng có thể chạm giới hạn đệ quy rồi báo RecursionError như bài đệ quy đã nói.

Kiểm tra nhanh

  1. Với hàm truoc của bài, truoc(Node(1, Node(2), Node(3))) trả về gì?

    • [2, 1, 3]
    • [2, 3, 1]
    • [1, 2, 3]
  2. Những câu nào đúng về cây nhị phân?

    • Mỗi nút có tối đa hai nút con
    • Lá là nút không có nút con nào
    • Mỗi nút phải có đủ hai nút con
    • Hàm duyệt đệ quy không cần điều kiện dừng vì lá không có con
  3. Với hàm chieu_cao của bài, chieu_cao(Node("A", None, Node("B", Node("C")))) trả về số nào?

    • 2
    • 3
    • 1
  4. Với hàm giua của bài, giua(Node(1, Node(2), Node(3))) trả về gì?

    • [2, 1, 3]
    • [1, 2, 3]
    • [2, 3, 1]
Đúng hết lần đầu +15 XP

Bài tập

Viết ba cách duyệt và chiều cao cho cây tổng đài

Mỗi Node của thực đơn tổng đài có gia_tri, trai và phai, chỗ con trống là None. Viết thân bốn phương thức của Node, tính cho cây có gốc là chính nút đó:

  • truoc(): các giá trị theo duyệt trước, gốc đứng đầu.

  • giua(): các giá trị theo duyệt giữa, gốc đứng giữa cây con trái và cây con phải.

  • sau(): các giá trị theo duyệt sau, gốc đứng cuối.

  • chieu_cao(): số nút trên đường dài nhất từ nút này xuống một lá, một lá cao 1.

Trả về: ba phương thức duyệt trả về một list, chieu_cao() trả về một int.

python
class Node:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri = gia_tri
        self.trai = trai
        self.phai = phai

    def truoc(self):
        pass  # Viết thân các phương thức thay cho các dòng pass

    def giua(self):
        pass

    def sau(self):
        pass

    def chieu_cao(self):
        pass

Tóm tắt

  • Cây nhị phân gồm các nút có tối đa hai con trai và phai, chỗ trống là None, nút trên cùng là gốc, nút không có con là lá.

  • Hàm duyệt đệ quy gọi lại chính nó cho hai cây con và dừng khi gặp None.

  • Duyệt trước đặt gốc đầu, duyệt giữa đặt gốc giữa, duyệt sau đặt gốc cuối.

  • Duyệt sau cho đúng thứ tự tính một biểu thức, vì hai vế có kết quả trước phép tính.

  • Chiều cao là một cộng chiều cao lớn hơn của hai cây con, đếm nút và chiều cao là O(n), còn ba phép duyệt ghép list có thể chậm tới O(n²) trên cây lệch.

Câu hỏi thường gặp

Làm sao tìm một giá trị trong cây nhị phân cho nhanh?

Cây nhị phân chỉ quy định mỗi nút có tối đa hai con. Muốn tìm nhanh, bạn cần cây nhị phân tìm kiếm, một loại cây có thêm luật xếp giá trị. Bài cây nhị phân tìm kiếm dạy luật đó và cách tìm.

Có cách duyệt cây theo từng tầng không?

Có, đó là duyệt theo chiều rộng: thăm gốc, rồi mọi nút ở tầng hai, rồi tầng ba. Cách này dùng hàng đợi thay cho đệ quy, bài BFS và DFS dạy nó.

Python có sẵn kiểu cây nhị phân không?

Không có kiểu tên cây nhị phân, nên bạn tự viết class Node như bài này. Module heapq dùng một list để giữ một dạng cây nhị phân gọi là heap cho hàng đợi ưu tiên, bài heapq dùng nó.

Chủ đề

binary tree

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập