1
CHƯƠNG 3- CÂY

2
Chương 3: Cây
3.1 Các khái niệm cơ bản
3.2 Cây nhị phân
3.2.1 Định nghĩa và tính chất
3.2.2 Biểu diễn cây nhị phân
3.2.3 Duyệt cây nhị phân

3
3.1 CÁC KHÁI NIỆM CƠ BẢN

Khái niệm cây:
–
Cây gồm một tập hợp hữu hạn các nút-node
–
Có một quan hệ thứ tự bộ phận (cha-con)
giữa các nút.
–
Có một nút đặc biệt, không là con của bất
cứ nút nào và là tổ tiên của mọi nút trong
cây, gọi là nút gốc (root).
–
Cây không có nút nào gọi là cây rỗng.

4
3.1 CÁC KHÁI NIỆM CƠ BẢN


,n
2
,…,n
k
= q
sao cho n
i
là cha của n
i+1.

6
3.1 CÁC KHÁI NIỆM CƠ BẢN

Độ dài đường đi – path length – là số cung nối
từng cặp hai nút trên đường đi, nó chính là số
nút trừ 1.

Cây có thứ tự - ordered tree – là cây mà có xét
đến thứ tự giữa các con của một nút. Nói nôm
na là có xét đến quan hệ “anh em”.

Con trưởng hay con cực trái là một nút là con
thứ nhất trong quan hệ thứ tự giữa các nút
cùng cha.

Em liền kề của một nút là nút đứng ngay sau
trong quan hệ thứ tự giữa các nút cùng cha.

Rừng – forest- là danh sách hữu hạn cây.


–
Số lượng tối đa của mỗi nút trên cây nhị
phân có chiều cao h là 2
h
-1

(h ≥ 1).
( Chứng minh)

10
3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN

Biểu diễn cây nhị phân bằng cấu trúc
mảng.

Biểu diễn cây nhị phân bằng danh sách
các nút.

Biểu diễn cây nhị phân bằng móc nối
các nút.

11
3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN
BẰNG CẤU TRÚC MẢNG
Với cây nhị phân hoàn chỉnh hoặc đầy
đủ trái ta có thể dùng cấu trúc mảng để
thể hiện một cây: Xếp liên tiếp các nút
của cây vào mảng theo thứ tự từ trên
xuống dưới, từ trái sang phải. Trường
hợp một nút bị khuyết thì thay bằng giá