Xem mẫu
- Bài 10. Cây Tree
1
- Cây – Cấu trúc dữ liệu phi
tuyến (TreesNonlinear data
structures)
ĐHGTVT
CT
CNTT KTVT
2
- Một số ví dụ sử dụng cấu
trúc dữ liệu cây
3
Data structures trees
- Cây gia phả
4
Data structures trees
- Cây biểu diễn các tổ chức
ĐHGTVT
KT
ĐĐT
CNTT CK
…
KTVT
ĐKH TTBĐ
CNPM KHMT VT
Mạng
5
Data structures trees
- Cây biểu diễn hệ thống files
Cây mô tả sự phân chia hệ thống files
6
Data structures trees
- Cấu trúc của cuốn Cây thể hiện
cấu trúc
sách
thông tin
Cây thể hiện cấu trúc của một cuốn sách
7
Data structures trees
- Cây thể
hiện lựa
Cây quyết định chọn quyết
định
Bạn đã có gia đình riêng chưa?
rồi chưa
Bạn có bằng đại học không?
Không chấp nhận
có Không
Bạn có tốt nghiệp loại giỏi không? Không chấp nhận
có không
Chấp nhận Không chấp nhận
Cây quyết định tuyển nhân viên
8
Data structures trees
- Cây nhị phân biểu diễn các biểu thức
toán học
Một cây nhị phân biểu diễn một biểu thức. Cây này biểu diễn
biểu thức ((((3+1)*3/((95)+2))((3*(74))+6)). Gi á trị được kết
hợp lại tại nút trong có nhãn “/” là 2.
9
Data structures trees
- Cây cú pháp
S XY
X XA | a | b
Y AY | a
A a
10
Data structures trees
- Tổng kết: Cây là cách tổ chức dữ liệu
rất hữu dụng trong rất nhiều ứng dụng
khác nhau
ĐHGTVT
CT
CNTT KTVT
11
Data structures trees
- Cây tổng quát
Cây là gì?
Cây là một tập các nút với quan hệ chacon
(parentchild) giữa các nút. Trong đó có một
nút được gọi là gốc và nó không có cha.
Trong khoa học máy tính, một cây là một mô
hình trừu tượng của cấu trúc phân cấp.
Các ứng dụng:
Tổ chức biểu đồ
Hệ thống file
Các môi trường lập trình …
12
Data structures trees
- Một số khái niệm
Gốc (root): gốc là nút không Cây con: Cây bao gồm
có nút cha ( vd: A) một số nút của một cây
ban đầu
Nút trong: Nút có ít nhất một
nút con (Vd: A, B, C, F) A
Nút ngoài (lá): nút không có
nút con (Vd: E, I, J, K, G, H,
D) B C D
Đô sâu của một nút:
Nút gốc có độ sâu là 0, nếu E F G H
nút cha có độ sâu là h thì nút
con có độ sâu là h+1
Chiều cao của cây: là giá trị I J K
lớn nhất của độ sâu của tất
cả các nút (3)
Cây con
13
Data structures trees
- Cấu trúc dữ liệu trừu tượng cây
Chúng ta quản lý các nút Các phương thức truy vấn:
thông qua địa chỉ của
int isInternal(Node*)
chúng.
int isExternal(Node*)
Các phương thức chung:
int isRoot(Node*)
int size()
int isEmpty() Thêm vào đó là những phương
Các phương duyệt cây: thức cập nhật được định nghĩa
void preorder(Node*) trong các cấu trúc dữ liệu tạo
void inorder(Node*)
Tree ADT (Node tạo cây)
void postorder(Node*)
Phương thức thêm phần tử vào
Các phương thức truy cập:
cây.
Địa chỉ root()
void insert(Node* parent,
Element e)
◊ Phương thức xóa phần tử
void remove(Node*);
14
Data structures trees
- Duyêt theo thứ tự trước –preorder
traversal
Duyệt cây là cách đi thăm
các nút của cây theo một Algorithm preOrder(v)
hệ thống If(v!=null)
Duyệt theo thứ tự trước, tức visit(v)
là: nút cha được thăm trước
for mỗi nút con w của v
sau đó thăm các nút con,
cháu, … preorder (w)
1
ĐHGTVT
10
2
6
CNTT CK QLGĐ
9
5 7 8
3 4
KHMT NHIET
KHMT CNPM ĐMTX CKOT
15
Data structures trees
- Ví dụ: Duyêt theo thứ tự trước
Thăm cây theo thứ tự trước (preorder). Trong đó cây con
được thăm theo thứ tự từ trái qua phải
16
Data structures trees
- Bài tập: Hãy chỉ ra thứ tự thăm các nút của cây dưới
đây bằng cách sử dụng phương pháp duyệt theo thứ
tự trước?
17
Data structures trees
- Thư tự thăm các nút bằng phương pháp duyệt theo
thứ tự trước
18
Data structures trees
- Duyệt theo thứ tự giữa
inorder Traversal
Algorithm inOrder(v)
Duyệt theo thứ tự sau, tức là:
If(v!=null)
nút con được thăm trước sau
đó thăm nút cha w = con cả của v
inOrder(w)
Ứng dụng: Tính toán không
gian sử dụng bởi các files và
visit(v)
các thư mục con
for mỗi nút con w1#w của v
4
cs16/ inOrder (w1)
9
2 6
todo.txt
homeworks/ programs/
1K
5 7 8
1 3
Robot.java
h1c.doc h1nc.doc DDR.java Stocks.java
20K
3K 2K 10K 25K
19
Data structures trees
- Duyệt theo thứ tự sau
PostOrder Traversal
Duyệt theo thứ tự sau, tức là:
Algorithm postOrder(v)
nút con được thăm trước sau
đó thăm nút cha If(v!=null)
Ứng dụng: Tính toán không
for mỗi nút con w của v
gian sử dụng bởi các files và
các thư mục con postOrder (w)
visit(v)
9
cs16/
8
3 7
todo.txt
homeworks/ programs/
1K
4 5 6
1 2
Robot.java
h1c.doc h1nc.doc DDR.java Stocks.java
20K
3K 2K 10K 25K
20
Data structures trees
nguon tai.lieu . vn
