Chương 4: Cây - Cấu trúc dữ liệu và giải thuật (ET2100) | Trường Đại học Bách khoa Hà Nội

lOMoAR cPSD| 27879799 Nội dung
4.1. Định nghĩa và các khái niệm 4.2. Cây nhị phân 4.3. Các ứng dụng 1/28/2013 2 lOMoAR cPSD| 27879799
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 3
4.1.1. Định nghĩa cây
Cây bao gồm các nút, có một nút ặc biệt ược gọi là gốc
(root) và các cạnh nối các nút. Cây ược ịnh nghĩa ệ qui như
sau: Định nghĩa cây:
Basic Step: Một nút r là cây và r ược gọi là gốc của cây này.
Recursive Step: Giả sử T1,T2,...,Tk là các cây với gốc là r1,r2,...,rk. Ta
có thể xây dựng cây mới bằng cách ặt r làm cha (parent) của các
nút r1,r2,..., rk . Trong cây này r là gốc và T1, T2, . . . , Tk là các cây
con của gốc r. Các nút r1, r2, . . . , rk ược gọi là con (children) của nút r. lOMoAR cPSD| 27879799
Chú ý: Nhiều khi ể phù hợp ta cần ịnh nghĩa cây rỗng (null tree) là
cây không có nút nào cả. 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 4
Cấu trúc ệ qui của cây r r r 1 2
r k T T 1 T 2 k 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 5
Cây trong thực tế ứng dụng
• Biểu ồ lịch thi ấu • Cây gia phả
• Biểu ồ phân cấp quản lý hành chính. • Cây thư mục
• Cấu trúc của một quyển sách • Cây biểu thức
• Cây phân hoạch tập hợp • ... lOMoAR cPSD| 27879799 1/28/2013 6 Cây lịch thi ấu
Trong đời thường cây rất hay được sử dụng để diễn tả
lịch thi đấu của các giải thể thao theo thể thức đấu loại
trực tiếp, chẳng hạn vòng 2 của World Cub Pháp Pháp Tây ban nha Pháp Brazin Brazin Anh Italia Đ Đ ứ c ứ c Ucrain Italia Italia Italia Ahentina 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 7 Cây gia phả
Cây gia phả của các nhà toán dòng họ Bernoulli Nikolaus 1623-1708 Johan I Nikolaus Jacob I 1667-1748 1662-1716 1654-1705 Nikolaus II Daniel Johan II Nikolaus I 1695-1726 1700-1782 1710-1790 1687-1759 Johan III Jacob II 1746-1807 1759-1789 lOMoAR cPSD| 27879799 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 8
Cây phân cấp quản lý hành chính Ban Giám ốc Phòng Phòng Phòng Phòng Phòng Tổ chức Tài vụ Hành chính Kinh doanh Kế hoạch TP Văn thư
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 9
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 1 /28/2013 10 lOMoAR cPSD| 27879799 Cây thư mục lOMoAR cPSD| 27879799 Cây mục lục sách 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 11
Cây gia phả ngược (Ancestor Tree)
Cây phả hệ ngược: mỗi người đều có bố mẹ. Cây
này là cây nhị phân (binary tree). Thùy Hươ ng Thúy Cả Quang Dũng i Bích Liên Trung Kiên Hoàng Cúc Quang Thái lOMoAR cPSD| 27879799
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 12
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây biểu thức (Expression Tree) + / / 1 3 * 4 6 7 1/3 + 6*7 / 4 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 13
Cây phân hoạch tập hợp lOMoAR cPSD| 27879799 14
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa
4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 15
4.1.2. Các thuật ngữ chính • Nút - node • Gốc - root • Lá - leaf • Con - child • Cha - parent • Tổ tiên - ancestors • Hậu duệ - descendants • Anh em - sibling
• Nút trong - internal node lOMoAR cPSD| 27879799 • Chiều cao - hight • Chiều sâu - depth
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 16
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT lOMoAR cPSD| 27879799
Các thuật ngữ chính
• Nếu n1, n2, . . . , nk là dãy nút trên cây sao cho ni là cha của ni+1 với 1 i < k, thì dãy
này ược gọi là ường i (path) từ nút n1 tới nút nk. Độ dài (length) của ường i là bằng số
lượng nút trên ường i trừ bớt 1. Như vậy ường i ộ dài 0 là ường i từ một nút ến chính nó.
• Nếu có ường i từ nút a tới nút b, thì a ược gọi là tổ tiên (ancestor) của b, còn b ược
gọi là hậu duệ (descendant) của a.
• Tổ tiên (hậu duệ) của một nút khác với chính nó ược gọi là tổ tiên (hậu duệ) chính
thường (proper). Trong cây, gốc là nút không có tổ tiên chính thường và mọi nút khác
trên cây ều là hậu duệ chính thường của nó.
• Một nút không có hậu duệ chính thường ược gọi lá lá (leaf).
• Các nút có cùng cha ược gọi là anh em (sibling).
• Cây con (subtree) của một cây là một nút cùng với tất cả các hậu duệ của nó. • Chiều
cao (height) của nút trên cây là bằng ộ dài của ường i dài nhất từ nút ó ến lá cộng 1.
Chiều cao của cây (height of a tree) là chiều cao của gốc. Độ sâu/mức (depth/level)
của nút là bằng 1 cộng với ộ dài của ường i duy nhất từ gốc ến nó. Th u
ậ n
t g ữ nút nodes 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THU ẬT TOÁ N
NGUYỄN ĐƯC NGHĨA - Bộ môn KHM T 18 CuuDuongThanCong.com
https://fb.com/tailieudientucntt lOMoAR cPSD| 27879799
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 17
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT lOMoAR cPSD| 27879799 Th g
uậ n t ữ Nút cha parent node
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 1/28/2013 19 Th ậ g u n
t ữ cha con parent child 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 20 CuuDuongThanCong.com
https://fb.com/tailieudientucntt lOMoAR cPSD| 27879799 Th
uậ t g n ữ con cha
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 1/28/2013 21
Thuậ n
t g ữ gốc lá - leaf
- root
CẤU TRÚC DỮ LIỆU VÀ THU ẬT TOÁ N
NGUYỄN ĐƯC NGHĨA - Bộ môn KHM T 22 lOMoAR cPSD| 27879799 Th
uậ t ng ữ
cây con -subtree
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 1/28/2013 23 Thuật ng ữ cây con 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 24 CuuDuongThanCong.com
https://fb.com/tailieudientucntt lOMoAR cPSD| 27879799 T
huậ t ng ữ cây con
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 1/28/2013 25 lOMoAR cPSD| 27879799
Các thuật ngữ với cây có gốc Đường i trên cây
Có duy nhất 1 ường i từ một nút ến một nút là
Từ cha ến con và ến hậu duệ của nó. các nút hậu duệ. a b d c Path 1 Path 2 e f g h i j Path 1: { a, b, f, j } Path 2: { d, i }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 27
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT ộ cao h ộ sâu 1 = 5 root, ance 7 stor a internal node parent ộ cao = 4 3 10 (k hông ộ l s à â lá ) u 2 4 b d nút c sibling ộ cao = 3 8 ộ sâu 3 12 11 2 e f leaf (không có con) g h h = 2 child chil 1 ộ sâu d 6 4 5 i j descendent e, i, k, g, h Độ cao của cây là 5 ộ cao h=1 9 ộ sâu 5 CẤ C U Ấ U TR T Ú R C Ú C DỮ D Ữ LIỆU Ệ U VÀ VÀ TH T U H Ậ U k là lá (leaves) T T TOÁ T N 26 28 NGUYỄ NGUY N ĐƯ Ễ C NGHĨA A -Bộ môn KHMT
- Bộ môn KHM T lOMoAR cPSD| 27879799
Độ cao (height) và ộ sâu/mức (depth/level)
How We View a Tree Nature Lovers View
Computer Scientists View
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 1/28/2013
- Bộ môn KHMT 29 lOMoAR cPSD| 27879799 Bậc (Degree) Số lượng con của nút degree = 3 x ược gọi là 7
bậc (degree) của x . 3 10 4 8 degree = 1 12 11 2 degree = 0 1 6 5 9
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁ N 30 NGUYỄN ĐƯC NGHĨA
- Bộ môn KHM T lOMoAR cPSD| 27879799
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ
4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây 1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 31
4.1.3. Cây có thứ tự - Ordered Tree
• Thứ tự của các nút
• Các con của một nút thường ược xếp thứ tự từ trái sang phải. Như
vậy hai cây trong hình sau ây là khác nhau, bởi vì hai con của nút a
xuất hiện trong hai cây theo thứ tự khác nhau: a a b c c b
• Cây với các nút ược xếp thứ tự ược gọi là cây có thứ tự. Ta sẽ xét
chủ yếu là cây có thứ tự. Vì vậy, tiếp theo thuật ngữ cây là ể chỉ cây