Tài liệu C4_Cau truc cay (Tree) pptx

Cấu trúc cây (Tree)

2/4/14 Nhập môn CTDL và thuật toán 2

Nội dung

• Giới thiệu khái niệm cấu trúc cây.

• Cấu trúc dữ liệu cây nhị phân, cây nhị

phân tìm kiếm

• Giới thiệu cấu trúc dữ liệu cây nhị phân

tìm kiếm cân bằng.

2/4/14 Nhập môn CTDL và thuật toán 3

Cây?

• Định nghĩa 1: Cây là một tập hợp T các

phần tử (gọi là nút của cây) trong đó có 1

nút đặc biệt được gọi là gốc, các nút còn

lại được chia thành những tập rời nhau

T1, T2 , ... , Tn theo quan hệ phân cấp

trong đó Ti cũng là một cây.

Mỗi nút ở cấp i sẽ quản lý một số nút ở

cấp i+1. Quan hệ này người ta còn gọi là

quan hệ cha-con

2/4/14 Nhập môn CTDL và thuật toán 4

Cây?

• Định nghĩa 2: Cây là tập hợp các phần tử

được tổ chức :

• Hoặc là tập rỗng(cây rỗng)

• Hoặc tập khác rỗng trong đó có một nút

gốc, các nút còn lại được phân thành

nhóm, trong đó mỗi nhóm là một cây (cây

con)

2/4/14 Nhập môn CTDL và thuật toán 5

Ví dụ

• Sơ đồ tổ chức của một công ty

Công ty A

R&D Kinh doanh Taøi vuï Saûn xuaát

Noäi ñòa Quoác teá TV CD Amplier

Chaâu aâu Myõ Caùc nöôùc

2/4/14 Nhập môn CTDL và thuật toán 6

Cây thư mục

C:\

Documents and Settings Program Files My Music

Desktop Favorites Start Menu Adobe Microsoft Office

2/4/14 Nhập môn CTDL và thuật toán 7

2/4/14 Nhập môn CTDL và thuật toán 8

2/4/14 Nhập môn CTDL và thuật toán 9

Một số khái niệm cơ bản

• Bậc của một nút : là số cây 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 trong cây. Cây có bậc n thì gọi là cây n￾phân.

• Nút gốc : là nút không có nút cha.

• Nút lá : là nút có bậc bằng 0 .

• Nút trong : là nút có bậc khác 0 và không

phải là gốc .

2/4/14 Nhập môn CTDL và thuật toán 10

Owner

Jake

Manager Chef Brad

Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

Ví dụ

ROOT NODE

2/4/14 Nhập môn CTDL và thuật toán 11

Owner

Jake

Manager Chef Brad

Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

Ví dụ : Nút Lá

NODE lá

2/4/14 Nhập môn CTDL và thuật toán 12

Ví dụ

Tree nodes

Tree edges

2/4/14 Nhập môn CTDL và thuật toán 13

Ví dụ

Gốc(root)

Nút trong

lá

cha

và

con