1
Chương 4
CÂY NHỊ PHÂN
4.1. Cấu trúc cây
4.1.1. ðịnh nghĩa
4.1.2. Một số khái niệm cơ bản
4.2. Cây nhị phân
4.2.1. ðịnh nghĩa
4.2.2. Một số tính chất của cây nhị phân
4.2.3. Biểu diễn cây nhị phân
4.2.3. Duyệt cây nhị phân
4.3. Cây nhị phân tìm kiếm
4.3.1. Cây nhị phân tìm kiếm
4.3.2. Các thao tác trên cây nhị phân tìm kiếm
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
2
4.1 Cấu Trúc Cây
4.1.1. ðịnh nghĩa cây
4.1.2. Một số khái niệm cơ bản
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
3
4.1.1. ðịnh nghĩa cây
ðịnh nghĩa 1: Một cây là tập hợp hữu hạn các nút trong
ñó có một nút ñặc biệt gọi là gốc (root). Giữa các nút có
một quan hệ phân cấp gọi là "quan hệ cha con".
Nút gốc
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
Nút gốc

r1 r2
r
T1
T2
ðịnh nghĩa 2: Cây ñược ñịnh nghĩa ñệ qui như sau
1. Một nút là một cây và nút này cũng là gốc của cây.
2. Giả sử T1, T2, …,Tn (n
≥
1) là các cây có gốc tương
ứng r1, r2,…, rn. Khi ñó cây T với gốc r ñược hình thành
bằng cách cho r trở thành nút cha của các nút r1, r2,…, rn
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
4
4.1.2. Một số khái niệm cơ bản
Bậc của một nút: Là số con của nút ñó
Bậc của một cây: Là bậc lớn nhất của các nút có trên
cây ñó (số cây con tối ña của một nút thuộc cây). Cây có
bậc n thì gọi là cây n - phân
Cây bậc 2 hay còn gọi là cây nhị phân
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
5
 Nút gốc: Là nút có không có nút cha
 Nút lá: Là nút có bậc bằng 0
 Nút nhánh: Là nút có bậc khác 0 và không phải là nút gốc
Nút gốc
Nút lá
Nút nhánh
Khoa CNTT Trường TC TÂY NAM Á

© Dương Thành Phết-www.thayphet.net
6
 Mức của một nút
Mức (gốc (T
0
)) =0
Gọi T
1
, T
2
, , T
n
là các cây con của T
0
.
Khi ñó Mức (T
1
) = Mức (T
2
) = = Mức (T
n
) = Mức (T
0
) +1
 Chiều cao của cây: Là số mức lớn nhất có trên cây ñó
Cây có chiều cao là 3
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
7
 ðường ñi: Dãy các ñỉnh n

1
,n
2
, ,n
k
gọi là ñường ñi
nếu n
i
là cha của n
i+1
(1 ≤ i ≤ k-1
 ðộ dài của ñường ñi: Là số nút trên ñường ñi -1
ðộ dài ñường ñi là 3
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
8
 Cây ñược sắp – Cây có thứ tự: Trong một cây, nếu
các cây con của mỗi ñỉnh ñược sắp theo một thứ nhất
ñịnh, thì cây ñược gọi là cây ñược sắp (cây có thứ tự).
A
B
C
5
3
8
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
9
4.2. Cây Nhị Phân
4.2.1. ðịnh nghĩa

4.2.2. Một số tính chất của cây nhị phân
4.2.3. Biểu diễn cây nhị phân
4.2.4. Duyệt cây nhị phân
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
10
Cây nhị phân là cây mà mỗi nút có tối ña hai cây con. ðối
với cây con của một nút có phân biệt cây con trái và cây
con phải.
4.2.1. ðịnh Nghĩa
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
11
4.2.1. Một Số Tính Chất Của Cây Nhị Phân
 Số lượng tối ña các nút có ở mức i: 2
i
(i
≥
0)
 Số nút lá tối ña trên cây có chiều cao h la: 2
h
 Số lượng nút tối ña của cây có chiều cao h: 2
h+1
-1(h
≥
1 )
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
12
13

4.2.3 Biễu Diễn Cây Nhị Phân
 Lưu trữ kế tiếp
Phương pháp tự nhiên nhất ñể biểu diễn cây nhị phân
là
chỉ ra ñỉnh con trái và ñỉnh con phải của mỗi ñỉnh.
Ta có thể sử dụng một
mảng ñể lưu trữ các ñỉnh của
cây nhị phân.
Mỗi ñỉnh của cây ñược biểu gồm ba giá trị
 Infor: Mô tả thông tin gắn với mỗi ñỉnh
 Letf : Chỉ ñỉnh con trái
 Right: Chỉ ñỉnh con phải.
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
14
Nếu cây nhị phân ñầy ñủ. Có thể lưu trữ cây này
bằng mãng 1 chiều
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
15
Nếu cây nhị phân không ñầy ñủ thì cách lưu trữ này
không thích hợp vì phí nhiều bộ nhớ.
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
16
 Lưu trữ móc nối
Cách lưu trữ này khắc phục nhược ñiểm của cách lưu
trữ kế tiếp ñồng thời phản ánh ñược dạng tự nhiên của

cây. Cách lưu trữ này một phần tử có qui tắc sau:
 Infor: Mô tả thông tin gắn với mỗi ñỉnh
 Letf : Con trỏ trỏ tới cây con trái
 Right: Con trỏ trỏ tới cây con phải
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
17
Khai báo cấu cây
typedef struct TNODE
{
<Data> Key;//<Data> là kiêu dư liêu cho key
struct NODE *pLeft, *pRight;
} *TREE;
typedef struct TNODE
{
int Key;
struct NODE *pLeft, *pRight;
} *TREE;
Ví vụ khai báo cây NP biểu diễn các nút là số nguyên
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
18
 Duyệt cây nhị phân
Duyệt theo thứ tự trước (NLR)
Tại nút t ñang xét nếu khác rỗng
- Thăm gốc
- Duyệt câycon trái theo thứ trước
- Duyệt cây con phải theo thư tự trước
void NLR(TREE t)
{

if (t != NULL)
{
<xử lý nút gốc>;
NLR(t->pleft);
NLR(t->pright);
}
}
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
19
Duyệt theo thứ tự giữa (LNR)
Tại nút t ñang xét nếu khác rỗng
- Duyệt cây con trái theo thứ giữa
- Thăm gốc
- Duyệt cây con phải theo thư tự giữa
void LNR(TREE t)
{
if (t != NULL)
{
NLR(t->pleft);
<xử lý nút gốc>;
NLR(t->pright);
}
}
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
20
Duyệt theo thứ tự sau (LRN)
Tại nút t ñang xét nếu khác rỗng
- Duyệt cây con trái theo thứ sau

- Duyệt cây con phải theo thư tự sau
- Thăm gốc
void LRN(TREE t)
{
if (t != NULL)
{
NLR(t->pleft);
NLR(t->pright);
<xử lý nút gốc>;
}
}
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
21
4.3. Cây Nhị Phân Tìm Kiếm
4.3.1. Cây nhị phân tìm kiếm
4.3.2. Các thao tác trên cây nhị phân tìm kiếm
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
22
4.3.1 Cây Nhị Phân Tìm Kiếm
Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân thoả mãn
ñồng thời các ñiều kiện:
 Khoá các ñỉnh thuộc cây con trái nhỏ hơn khoá nút gốc
 Khoá nút gốc nhỏ hơn (hoặc bằng) khoá các ñỉnh thuộc
cây con phải
 Cây con trái và cây con phải của gốc cũng là CNPTK
Cây NPTK ñược sử dụng vào nhiều
mục ñích khác nhau. Tuy nhiên việc
sử dụng cây NPTK ñể lưu giữ và

tìm kiếm thông tin vẫn là một trong
những ứng dụng quan trọng nhất
ðịnh Nghĩa
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
23
 Nút có giá trị nhỏ nhất nằm ở trái nhất của cây
 Nút có giá trị lớn nhất nẳm ở phải nấht của cây
Min
Max
Các Tính Chất
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net
24
25
4.3.2 Các Thao Tác Trên Cây NPTK
 Khai báo cấu trúc cây
 Dựng cây – Thêm nút vào cây
 Duyệt cây
 Dựng cây từ kết quả duyệt cây
 Tìm kiếm nút có giá trị x
 Xóa nút có giá trị x trên cây
 Hủy cây
Khoa CNTT Trường TC TÂY NAM Á
© Dương Thành Phết-www.thayphet.net