Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 3: Cây

3/2/2011

NỘI DUNG

Khái niệm cơ bản

Cây

CHƯƠNG 3

Cây nhị phân

Duyệt cây

CÂY ‐ TREE

KHÁI NIỆM

Cây ‐ tree

• Biểu diễn mối quan hệ

có thứ bậc giữa các đối

tượng

• Quan hệ giữa các nút là

quan hệ cha‐con hoặc

ngang hàng

Cây phả hệ ‐ family tree

1

3/2/2011

KHÁI NIỆM

Các nút ở mức ngoài cùng được

gọi là nút lá – leaf node

Định nghĩa: Cây là một tập hợp gồm các nút. Tập này có thể rỗng,

nếu không thì nó bao gồm một nút ꢀ được gọi là gốc và một tập

rỗng hoặc khác rỗng các cây con ꢁ_ꢂ, ꢁ_ꢃ, . . , ꢁ_ꢄmà có nút gốc

được nối trực tiếp bằng một cạnh từ nút gốc ꢅ

Các nút không phải nút lá được gọi

là nút trong – internal node

Nút gốc – là nút mà không có nút

ꢀ

nào đứng trên nó

A

Mỗi nhánh có thể được

xem như là một cây con

B

C

ꢁ_ꢂ

ꢁ_ꢃ

ꢁ_ꢄ

. . .

D

E

F

G

H

A

KHÁI NIỆM

C

E

• Các nút cùng cha là anh em (sibling)

• E và C, hoặc F, G và H

• Nút gốc: là nút không có nút nào đứng trên

F

G

H

F

G

H

• Đường đi từ nút ꢆ_ꢇtới nút ꢆ_ꢈtrên cây là một danh sách các

nút ꢆ_ꢇ, ꢆ_ꢇꢉꢊ, . . , ꢆ_ꢈtrong đó nút ꢆ_ꢇlà cha của nút ꢆ_ꢇꢉꢊ

.

• Độ dài đường đi: là số cạnh trên đường đi.

• A là gốc

• Nút lá: nút không có nút con

• Đường đi qua ꢆ đỉnh thì có độ dài ꢆ ꢋ 1

• Đường đi từ nút đến chính nó có độ dài là 0

• E, F, G, H

Đường đi từ A đến H là A, C, H có độ dài 2

Đường đi từ C đến C có độ dài 0

2

3/2/2011

A

KHÁI NIỆM

C

E

Biểu diễn cây: thông qua nút cha của nó (cấu trúc liên tiếp)

F

G

H

A

• Độ sâu/mức (depth/level)của nút: độ dài đường đi từ nút gốc

đến chính nó

C

E

• Độ sâu của nút gốc A là 0, của nút G, H là 2

• Độ cao (height) của nút: là độ dài đường đi lớn nhất từ nó đến

một nút lá

F

G

H

• Độ cao của nút lá E, F, G, H là 0, của nút A là 2

• Độ cao của cây: là độ cao của nút gốc

0

A

C

• Độ sâu của cây: là độ sâu lớn nhất của nút lá trên cây

KHÁI NIỆM

Biểu diễn cây: Con đầu tiên và

Biểu diễn cây: danh sách các nút con (cấu trúc liên kết)

các nút anh em (cấu trúc liên kết)

A

E

C

A

struct TreeNode

{

E

C

F

C

E

G

H

F

DATA_TYPE info;

struct TreeNode *firstChild;

struct TreeNode *nextSibling;

}

G

F

G

H

3

3/2/2011

KHÁI NIỆM

Duyệt cây

KHÁI NIỆM

Duyệt cây

• Duyệt cây theo thứ tự sau (post‐order traversal): xử lý dữ liệu

trên các nút con trước sau đó mới xử lý dữ liệu trên nút hiện tại

• Duyệt cây theo thứ tự trước (pre‐order traversal): xử lý dữ liệu

trên nút hiện tại trước sau đó xử lý tiếp đến các nút con của nó

A

C

E

F

G

H

F

G

H

In ra các đỉnh khi duyệt theo thứ tự trước: A, E, C, F, G, H

In ra các đỉnh khi duyệt theo thứ tự sau: E, F, G, H, C, A

CÂY NHỊ PHÂN

Cây nhị phân – binary tree:

A

• Là một tập rỗng, hoặc

• Có một nút gốc với hai cây nhị

C

B

phân con của gốc gọi là cây con trái

(left subtree) và cây con phải (right

subtree)

CÂY NHỊ PHÂN

D

E

F

H

G

4

3/2/2011

CÂY NHỊ PHÂN

Một số cây nhị phân gồm 3 nút khác nhau

• Cây nhị phân đầy đủ (full binary tree):

• Các nút không phải là lá đều có 2 nút con

• Các nút lá có độ sâu bằng nhau

• Cây nhị phân đầy đủ chiều cao h

có bao nhiêu nút lá?

• Cây nhị phân đầy đủ có bao nhiêu nút?

CÂY NHỊ PHÂN

Cây nhị phân cân bằng (balanced binary tree): là cây nhị phân thỏa

• Cây nhị phân hoàn chỉnh (complete binary tree) chiều cao ꢌ

• Các nút từ mức 0 tới ꢌ ꢋ 1 là cây nhị phân đầy đủ

• Một số nút ở mức ꢌ ꢋ 1 có thể có 0 hoặc 1 con

• Nếu ꢍ, ꢎ là các nút ở mức ꢌ ꢋ 1, thì ꢍ có nhiều con hơn ꢎ nếu ꢍ

nằm ở bên trái ꢎ

mãn

• Với mọi nút thì chênh lệch chiều cao của cây con trái và cây con

phải không quá 1

Mỗi cây nhị phân hoàn chỉnh là cây cân bằng

5

3/2/2011

DUYỆT CÂY – TREE TRAVERSAL

Mỗi nút trên cây nhị phân gồm :

• Giá trị chứa tại nút

• Cây con trái

• Cây con phải

DUYỆT CÂY

Duyệt cây theo thứ tự

TREE TRAVERSAL

• Thứ tự trước – preorder: Giá trị  con trái  con phải

• Thứ tự giữa – inorder : con trái  giá trị  con phải

• Thứ tự sau – postorder : con trái  con phải  giá trị

DUYỆT CÂY – TREE TRAVERSAL

1

Thứ tự trước : 1, 2, 3

A

Thứ tự giữa : 2, 1, 3

Thứ tự sau : 2, 3, 1

3

2

C

B

ỨNG DỤNG CỦA CÂY NHỊ PHÂN

D

E

F

Thứ tự trước : A, B, D, E, G, H, C, D

Thứ tự giữa : D, B, G, E, H, A, F, C

Thứ tự sau : D, G, H, E, B, F, C, A

H

G

6

3/2/2011

CÂY BIỂU THỨC – EXPRESSION TREE

Cây biểu thức – expression tree: xây dựng từ các toán tử và toán

hạng

• Toán tử 1 ngôi: nút gốc biểu diễn toán tử, chỉ có 1 nút

con biểu diễn toán hạng

• Toán tử 2 ngôi: gốc là toán tử, 2 nút con lần lượt là toán hạng

trái và phải

ꢏꢐꢑ

ꢋ

ꢋ3

log ꢒ

a

3

%

+

2+3

a%3

++

!

5!

3++

3

a

2

3

5

ꢘ ꢙ ꢋꢖ ꢗ ꢕ/ꢔ ∗ ꢃ^ꢚ

• Pre‐order traversal ‐> prefix notation

• In‐order traversal ‐> infix notation

• Post‐order traversal ‐> postfix notation

CÂY BIỂU THỨC – EXPRESSION TREE

ꢙ

Thuật toán xây dựng cây biểu thức từ biểu thức dạng hậu tố

Đọc lần lượt các phần tử của biểu thức hậu tố

• Gặp toán hạng: tạo ra cây có 1 nút là toán hạng và đẩy vào stack

• Gặp toán tử:

ꢘ

ꢗ

ꢋ

∗

• Nếu là toán tử 1 ngôi: lấy ra 1 cây ꢛ trong stack, tạo ra 1 cây

trong đó toán tử là nút gốc và cây ꢛ là nút con, sau đó đẩy cây

này vào stack

ꢖ

/

^

• Nếu là toán tử 2 ngôi: lấy ra 2 cây trong stack ꢛ , ꢛ_ꢜ(ꢛ_ꢜđược

ꢊ

lấy ra trước), tạo cây trong đó toán tử này là gốc và ꢛ , ꢛ_ꢜlần

ꢊ

lượt là con trái và con phải của nó, sau đó đẩy cây này vào stack

ꢕ

ꢔ

ꢃ

ꢓ

•

Sau khi duyệt xong biểu thức hậu tố, cây biểu thức là cây có gốc

nằm ở đỉnh của stack

7

3/2/2011

ꢝ ꢞ ꢗ ꢒ ∗ ꢟ ꢋ

Ban đầu stack rỗng

Gặp ꢝ

Gặp ꢗ

Gặp ꢞ

Gặp ꢋ

ꢖ

ꢕ

ꢗ

ꢋ

ꢖ

ꢕ

Gặp ꢒ

Gặp ∗

Gặp ꢟ

∗

ꢡ

ꢗ

ꢠ

ꢕ

∗

ꢡ

ꢠ

ꢗ

ꢖ

ꢠ

ꢗ

ꢖ

ꢕ

ꢖ

ꢕ

ꢖ

ꢕ

CÂY QUYẾT ĐỊNH, CÂY TÌM KIẾM NHỊ PHÂN

BIỂU DIỄN CÂY NHỊ PHÂN

Cây quyết định cho thuật toán tìm kiếm nhị phân trên dãy số

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

8

3/2/2011

BIỂU DIỄN CÂY NHỊ PHÂN

Biểu diễn cây nhị phân

Biểu diễn bằng cấu trúc liên kết

• Dùng cấu trúc liên tiếp (mảng): số lượng nút trên cây chiều cao

ꢇ

∑

ꢌ là giới hạn ( 2 )

struct TreeNode

{

• Truy nhập nhanh ꢢꢣ1ꢤ

• Lãng phí bộ nhớ lớn nếu cây chưa phải là dạng đầy đủ hoặc

hoàn chỉnh

DATA_TYPE info;

struct TreeNode *leftChild;

struct TreeNode *rightChild;

}

• Dùng cấu trúc liên kết: thường dùng hơn

• Truy cập 1 nút chậm hơn

• Tiết kiệm bộ nhớ hơn (trong trường hợp tổng quát)

struct TreeNode

{

BIỂU DIỄN CÂY NHỊ PHÂN

int data;

struct TreeNode *leftChild;

struct TreeNode *rightChild;

}

Duyệt cây theo thứ tự trước

void preorderTraversal(TreeNode* root)

{

if(root==NULL) return;

printf("%d ",root‐>data);

if(root‐>leftChild!=NULL) inorderTraversal(root‐>leftChild);

if(root‐>rightChild!=NULL) inorderTraversal(root‐>rightChild);

}

9

3/2/2011

10

Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 3: Cây - Nguyễn Duy Hiệp