Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương V: Cấu trúc Cây

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

Chương IV: Cấu trúc Cây

Cấu trúc Cây

z

Nội dung

1. Các khái niệm

2. Cây tổng quát

1. ADT Cây

2. Biểu diễn cây tổng quát

3. Duyệt cây tổng quát

3. Cây nhị phân

1. Định nghĩa và tính chất

2. Duyệt cây nhị phân

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

4. Ứng dụng của cấu trúc cây cho cây biểu thức

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

1

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

Định nghĩa Cây

− Cây là một cấu trúc phi tuyến, thiết lập trên một

tập hữu hạn các “nút”

– Tồn tại một nút đặc biệt gọi là “gốc” (root)

– Giữa các nút tồn tại một quan hệ phân cấp hay gọi

là quan hệ cha con

– Một nút trừ nút gốc chỉ có một cha

– Một nút có thể có từ 0 đến n con

Đỗ Bích Diệp - Khoa CNTT

Định nghĩa Cây

z Định nghĩa đệ quy về

Cây

r

– Một nút tạo thành một

cây.

– Nếu có n cây T₁, T₂, …,

T_ntách biệt có các nút

gốc lần lượt là r₁, r₂, … ,

r_n; r là một nút có quan

hệ cha-con với r₁, r₂, … ,

r_nthì tồn tại một cây mới

T nhận r làm gốc.

r1

r2

rn

T2

T1

Tn

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

2

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

Ví dụ Cây

Cây thư mục trong máy tính

Desktop

My Network

Places

My

Documents

My Computer

My Received

Files

WindowsXP

(C:)

CD Driver

(D:)

My Pictures

Floppy(A:)

My Music

Đỗ Bích Diệp - Khoa CNTT

Ví dụ Cây

Cây phân cấp chức năng hệ thống thông tin

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

3

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

Ví dụ Cây

Cây mục lục Sách

Đỗ Bích Diệp - Khoa CNTT

Các thuật ngữ liên quan đến cây

– Cấp (Degree) của một nút và của cây

z Cấp của một nút là số các con của nút đó

z Cấp của một cây là cấp cao nhất của một nút trên cây

Degree 3

Degree 2

A

Degree 4

B

C

D

I

Degree 1

E

F

G

H

J

K

Degree 3

L

M

N

P

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

4

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

Các thuật ngữ liên quan đến cây

– Đường đi trên cây:

z Dãy các nút n₁, n₂, .., n_ktrong đó n_ilà nút cha của n_i+1( i =

1..k-1) là đường đi từ n₁đến n_k

Path from A to M

Length = 3

A

B

C

D

E

F

G

H

I

J

K

P

L

M

N

Đỗ Bích Diệp - Khoa CNTT

Các thuật ngữ liên quan đến cây

z Độ sâu hay mức (Depth – Level ) của nút

– Độ dài đường đi từ gốc đến nút đó + 1

Depth 1

A

Depth 2

B

C

G

D

I

Depth 3

Depth 4

E

F

H

J

K

P

L

M

N

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

5

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

Các thuật ngữ liên quan đến cây

z Độ cao (Height) của nút

– Độ dài đường đi dài nhất từ nút đó đến 1 nút lá trong cây +

1

– Chiều cao của cây là chiều cao của nút gốc của cây đó

Height =4

Height =3

A

B

C

D

I

Height = 2

E

F

G

H

J

K

P

L

M

N

Height = 1

Đỗ Bích Diệp - Khoa CNTT

Các thuật ngữ liên quan đến cây

z Tổ tiên (Ancestor): A,C, G là tổ tiên của M

z Hậu duệ (descendants): E, F, G, H, L,M …đều là hậu duệ của A

z Anh em (siblings): E, F là một cặp anh em ; L, N là một cặp anh

em

A

B

C

G

D

I

E

F

H

J

K

P

L

M

N

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

6

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

Các thuật ngữ liên quan đến cây

z Rừng là một tập hợp hữu hạn các cây phân biệt , không

giao nhau

B

C

G

D

I

E

F

H

J

K

L

M

N

Đỗ Bích Diệp - Khoa CNTT

Các thao tác cơ bản trên Cây

–

Các thao tác truy nhập cây

z root() : trả ra nút gốc của cây

z parent( Tree T, Node p): trả ra nút cha của nút p trong cây T

z children(Tree T, Node p): trả ra danh sách các nút con của nút p trong

cây T

z left_most_child(Tree T, Node p) : trả ra nút con cực trái của nút p

z right_most_child(Tree T, Node p) : trả ra nút con cực phải của nút p

z left_sibling (Tree T, Node p) : trả ra nút anh em kề cận bên trái của nút

p

z right_sibling(Tree T, Node p) : trả ra nút anh em kề cận bên phải của

nút p

–

Các thao tác khác

z height (Tree T)

z size(Tree T)

z isRoot (Tree T, Node p); isLeaf (Tree T, Node p);

isInternal (Tree T, Node p);

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

7

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

Biểu diễn cây tổng quát

– Dựa trên tham chiếu đến nút cha

z Cây T có các nút được đánh số từ 1 đến n

z Cây T được biểu diễn bằng một danh sách tuyến tính

trong đó nút thứ i sẽ chứa một thành phần tham chiếu

đến cha của nó

z Nếu dùng mảng, A[i] = j nếu j là cha của nút i ; nếu i₁là

A

gốc thì A[i] = 0;

2

4

3

B

C

D

0

1

2

3

6

5

6

7

E

G

H

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

8

9

L

N

Đỗ Bích Diệp - Khoa CNTT

Biểu diễn cây tổng quát

– Dựa trên danh sách các nút con

z 1 nút trong cây có một danh sách các nút con

z Danh sách các nút con thường là danh sách móc nối

z Trong trường hợp sử dụng danh sách móc nối, các nút

đầu danh sách được lưu trong một mảng

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

8

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

Biểu diễn cây tổng quát

– Dựa trên danh sách các nút con

A[1]

A[2]

2

5

6

3

7

4

1

A

2

4

3

B

C

D

A[3]

5

6

7

NULL

A[4]

A[5]

A[6]

E

G

H

8

9

8

9

L

N

NULL

A[7]

A[8]

A[9]

Đỗ Bích Diệp - Khoa CNTT

Biểu diễn cây tổng quát

– Thông qua một cây cấp 2

z Với một nút trong cây , chỉ quan tâm tới 2 quan hệ

– Quan hệ 1-1 giữa nút đó và nút con cực trái của nó (con cả)

– Quan hệ 1-1 giữa nút đó và nút em kế cận bên phải của nó

z Dựa vào nhận định này, người ta biểu diễn được một cây

tổng quát dưới dạng một cây nhị phân gọi là cây nhị phân

tương đương (equivalent binary tree)

z Quy cách của 1 nút trên cây nhị phân tương đương sẽ

như sau

LCHILD

INFO

RSIBLING

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

9

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

Biểu diễn cây tổng quát

A

z Ví dụ:

– Cây tổng quát

B

C

D

I

E

F

G

H

K

A

– Cây nhị phân tương đương

B

E

C

F

G

D

H

I

Đỗ Bích Diệp - Khoa CNTT

K

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

9

3.D

5

1. B

2. C

6

7

8

3

4

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

10

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

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

⇒

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

1. B

2. C

3. D

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

⇒

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

1. B

2. C

3. D

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

11

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

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

⇒

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

1. B

2. C

3. D

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

⇒

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

1. B

2. C

3. D

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

12

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

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

⇒

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

1. B

2. C

3. D

3

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

Thăm nút con

tiếp theo

1. B

2. C

3. D

3

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

13

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

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

⇒

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

1. B

2. C

3. D

3

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

⇒

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

1. B

2. C

3. D

3

4

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

14

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

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

1

Không còn con

I. A

Quay lại nút gốc

2

1. B

2. C

3. D

3

4

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

Thăm nút con

tiếp theo của gốc

1

I. A

2

1. B

2. C

3. D

3

4

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

15

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

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

for each child w of v

preOrder(w)

⇒

Ứng dụng: In ra các mục lục của

một tài liệu

1

I. A

2

1. B

2. C

3. D

3

4

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

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

z

Duyệt cây là thăm các nút trên cây

theo một thứ tự nhất định, mỗi nút

thăm 1 lần

Khi duyệt theo thứ tự trước, một nút

sẽ được thăm trước các hậu duệ

của nó

Algorithm preOrder(v)

visit(v)

⇒

for each child w of v

preOrder(w)

Ứng dụng: In ra các mục lục của

một tài liệu

Và tiếp tục như vậy ….

1

I. A

2

1. B

2. C

3. D

5

3

4

1.1 E

1.2 F

2.1 G

2.2 H

2.3 I

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

16

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

Duyệt cây theo thứ tự sau

z

Duyệt theo thứ tự sau thì một nút

sẽ được thăm sau các hậu duệ

của nó

Algorithm postOrder(v)

for each child w of v

postOrder(w)

z

Ứng dụng: Xác định kích thước

của các tệp trong một thư mục và

các thư mục con của

9

visit(v)

cs16/

8

3

7

todo.txt

1K

homeworks/

programs/

4

5

6

1

2

h1c.doc

3K

h1nc.doc

2K

DDR.java

10K

Stocks.java

25K

Robot.java

20K

Đỗ Bích Diệp - Khoa CNTT

Duyệt cây theo thứ tự giữa

z

Duyệt theo thứ tự giữa thì một nút

sẽ được thăm sau các hậu duệ

của nó trong cây con cực trái và

trước các hậu duệ trong các cây

con tiếp theo

Algorithm inOrder(v)

if (isLeaf(v)) then visit(v)

else

inOrder(left_most_child(v))

visit(v)

for each child w of v (w is

not the left most child)

4

cs16/

inOrder(w)

9

2

6

todo.txt

1K

homeworks/

programs/

5

7

8

1

3

h1c.doc

3K

h1nc.doc

2K

DDR.java

10K

Stocks.java

25K

Robot.java

20K

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

17

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

Cây nhị phân ( Binary Tree)

– Là cây mà mọi nút trên cây chỉ có tối đa là 2 con.

z Cây con của một nút cũng cần phải được phân biệt rõ

ràng thành cây con trái (left subtree) và cây con phải

(right subtree)

A

right-subtree

left-subtree

B

C

F

D

E

G

Đỗ Bích Diệp - Khoa CNTT

Ví dụ cây nhị phân

– Cây biểu thức số học với các phép toán 2 ngôi

+

-

/

z

*

x

3

y

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

18

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

Ví dụ cây nhị phân

– Cây quyết định

Want a fast meal?

Yes

No

How about coffee?

On expense account?

Yes

No

Yes

No

Starbucks

Spike’s

Al Forno

Café Paragon

Đỗ Bích Diệp - Khoa CNTT

Ví dụ cây nhị phân

– Kết quả thi đấu một môn thể thao theo cặp tại nhiều

vòng

H

A

H

F

E

A

H

C

A

D

E

B

H

G

F

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

19

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

Các dạng đặc biệt của cây nhị phân

z Cây suy biến (degenerate binary tree)

– Mỗi nút trong của cây có đúng 1 nút con

A

C

F

G

(a)

(b)

(c)

(d)

Đỗ Bích Diệp - Khoa CNTT

Các dạng đặc biệt của cây nhị phân

z Cây nhị phân đầy đủ (full

A

binary tree)

– Mỗi nút trong của cây đều

có đầy đủ 2 con

B

C

F

D

G

E

A

z Cây nhị phân gần đầy

B

C

– Ở mức cuối cùng không

có đầy đủ các nút

G

D

E

F

H

I

J

K

Đỗ Bích Diệp - Khoa CNTT

Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN

20

Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương V: Cấu trúc Cây - Đỗ Bích Diệp