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

Trong đi thường cây rt hay được sdng đdin tlch thi đu ca các gii ththao theo ththc đu loi trc tiếp, chng hn vòng 2 ca World Cub

Thông tin:
83 trang 4 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

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

Trong đi thường cây rt hay được sdng đdin tlch thi đu ca các gii ththao theo ththc đu loi trc tiếp, chng hn vòng 2 ca World Cub

37 19 lượt tải Tải xuống
lOMoARcPSD| 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
lOMoARcPSD| 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ử T
1
,T
2
,...,T
k
các cây với gốc r
1
,r
2
,...,r
k
. Ta
thể xây dựng cây mới bằng cách ặt r m cha (parent) của các
nút r
1
,r
2
,..., r
k
. Trong cây này r gốc T
1
, T
2
, . . . , T
k
các cây
con của gốc r. Các nút r
1
, r
2
, . . . , r
k
ược gọi con (children) của
nút r.
lOMoARcPSD| 27879799
Chú ý: Nhiều khi ể phù hợp ta cần ịnh nghĩa cây rỗng (null tree)
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
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
...
r
r
1
r
k
r
2
T
1
T
2
T
lOMoARcPSD| 27879799
1/28/2013 6
Cây lịch thi ấu
Trong đi thường cây rt hay được sdng đdin t
lch thi đu ca các gii ththao theo ththc đu loi
trc tiếp, chng hn vòng 2 ca World Cub
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 phca các nhà toán dòng hBernoulli
Pháp
Tây ban nha
Brazin
Anh
Đ
c
Ucrain
Italia
Ahentina
Pháp
Brazin
Đ
c
Italia
Pháp
Italia
Italia
Nikolaus
1623-1708
Johan I
1667-1748
Nikolaus
1662-1716
Jacob I
1654-1705
Nikolaus II
1695-1726
Daniel
1700-1782
Johan II
1710-1790
Nikolaus I
1687-1759
Jacob II
1759-1789
Johan III
1746-1807
lOMoARcPSD| 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 qun lý hành chính
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/20
1
3
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
9
1
/28/2013 10
Ban Giám ốc
Phòng
Tài vụ
Phòng
Tổ chức
Phòng
Hành chính
Phòng
Kinh doanh
Phòng
Kế hoch
Văn thư
TP
lOMoARcPSD| 27879799
Cây thư mục
lOMoARcPSD| 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 phhngược: mi người đu có bm. Cây
này là cây nhphân (binary tree).
Thùy H
ươ
ng
Thúy C
i
Quang Dũng
Bích Liên
Trung Kiên
Hoàng Cúc
Quang Thái
lOMoARcPSD| 27879799
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
12
Cây biểu thức (Expression Tree)
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
/
+
/
1
*
3
7
6
4
lOMoARcPSD| 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
- leaf
Con - child
Cha - parent
Tổ tiên - ancestors
Hậu duệ - descendants
Anh em - sibling
Nút trong - internal node
lOMoARcPSD| 27879799
Chiều cao - hight
Chiều sâu - depth
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
16
lOMoARcPSD| 27879799
1/28/2013
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Các thuật ngữ chính
Nếu n
1
, n
2
, . . . , n
k
dãy nút trên cây sao cho n
i
cha của n
i+1
với 1 i < k, thì dãy
này ược gọi là ường i (path) từ nút n
1
tới nút n
k
. Độ 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 ường i từ nút a tới nút b, thì a ược gọi 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 ược gọi 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(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 bằng dài của ường i dài nhất từ nút ó ến cộng 1.
Chiều cao của cây (height of a tree) 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ó.
g
n
t
u
h
T
nút
nodes
CẤU TRÚC DỮ LIỆU VÀ THU
ẬT TOÁ
NGUYỄN ĐƯC NGHĨA
-
Bộ môn
KHM
T
18
lOMoARcPSD| 27879799
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
17
lOMoARcPSD| 27879799
1/28/2013
CuuDuongThanCong.com https://fb.com/tailieudientucntt
n
t
u
h
T
g
con
child
cha
parent
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
20
h
n
t
u
T
g
Nút cha
parent node
1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
19
lOMoARcPSD| 27879799
h
T
u
g
n
t
gốc
root
-
lá - leaf
CẤU TRÚC DỮ LIỆU VÀ THU
ẬT TOÁ
NGUYỄN ĐƯC NGHĨA
-
Bộ môn
KHM
T
22
T
n
h
g
t
u
con
cha
1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
21
lOMoARcPSD| 27879799
1/28/2013
CuuDuongThanCong.com https://fb.com/tailieudientucntt
g
n
T
h
u
t
cây con
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
24
h
g
n
t
u
T
cây con -subtree
1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
23
lOMoARcPSD| 27879799
T
h
g
n
t
u
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
25
lOMoARcPSD| 27879799
Các thuật ngữ với cây có gốc
Đường i trên cây
a
c
b
e
f
d
g
j
i
h
Path 1
Path 2
Path 1: {
a, b, f, j
}
Path 2: {
d, i
}
Từ cha ến con và ến
các nút hậu duệ.
Có duy nhất 1 ường i từ
một nút ến một nút là
hậu duệ của nó.
1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
27
a
b
d
e
f
i
j
g
h
c
k
root, ancestor
parent
nút
child
child
descendent
leaf (không có con)
e, i, k, g, h
là lá (leaves)
internal node
không là lá
(
)
sibling
CU TRÚC D LIU THUT T
NGUYN ĐƯC NGHĨA
-
B môn KHM
T
26
7
3
10
8
4
12
1
6
5
2
11
9
ộ cao
h
=
5
ộ sâu 1
ộ sâu 2
ộ sâu 3
ộ sâu
4
ộ sâu 5
ộ cao = 4
ộ cao = 3
ộ cao h=1
h = 2
Độ cao của cây là 5
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
28
lOMoARcPSD| 27879799
Độ cao (height) và ộ sâu/mức (depth/level)
H
o
w
W
e
V
i
e
w
a
T
r
e
e
Nature Lovers View
Computer Scientists View
1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHMT
29
lOMoARcPSD| 27879799
Bậc (Degree)
9
Số ợng con của nút
x ược gọi là
bậc (degree)
của
x
.
degree = 3
7
3
10
8
4
12
1
6
5
2
11
degree = 1
degree = 0
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁ
NGUYỄN ĐƯC NGHĨA
-
Bộ môn KHM
T
30
lOMoARcPSD| 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:
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
a
b
c
a
c
b
| 1/83

Preview text:

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 r
1,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 r
1, 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)
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á (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