Nối tiếp chương 5, Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 giới thiệu nội dung về cây và cây nhị phân: định nghĩa, khái niệm và ví dụ minh họa, một số tính chất của cây nhị phân, cấu trúc dữ liệu và duyêt cây nhị phân. Mời các bạn tham khảo.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Trường ĐH Công nghệ Thông tin
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
Cấu trúc dữ liệu 1 vá thuật giải Click To Edit
1
NỘIMaster
CÂY VÀ CÂY NHỊ PHÂN
DUNGTitle Style
- Định Nghĩa
Click ToCây
Edit Master Title Style
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ó một nút đặc biệt gọi là
nút 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ệ
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
phân cấp, trong đó Ti cũng là 1 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 gọi là quan hệ cha – con.
2
- MộtClick
Số Khái
ToNiệm
Edit Master Title Style
• 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
• 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 .
Cấu trúc dữ liệu 1 vá thuật giải
• Mức của một nút:
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
– Mức (gốc (T) ) = 0.
– Gọi T1, T2, T3, ... , Tn là các cây con của T0 :
Mức (T1) = Mức (T2) = . . . = Mức (Tn) = Mức (T0)
+ 1.
• Độ dài đường đi từ gốc đến nút x: là số nhánh
cần đi qua kể từ gốc đến x.
3
- Ví Dụ 1 TổTo
Click Chức
EditDạng Cây
Master Title Style
BB-Electronic Corp.
R&D Kinh doanh Taøi vuï Saûn xuaát
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
Noäi ñòa Quoác teá TV CD Amplier
Chaâu aâu Myõ Caùc nöôùc
4
- CâyClick
Nhị Phân
To Edit Master Title Style
• Mỗi nút có tối đa 2 cây con
Caây Caây
con con
traùi
Cấu trúc dữ liệu 1 vá thuật giải
phaûi
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
5
- MộtClick
Số Tính
ToChất
EditCủa Cây Nhị
Master Phân
Title Style
• Số nút nằm ở mức i
2i.
• Số nút lá 2h-1, với h là
chiều cao của cây.
• Chiều cao của cây h
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
log2(N)
– N = số nút trong cây
• Số nút trong cây 2h-1.
6
- CấuClick
Trúc Dữ
To Liệu
EditCủa Cây Nhị
Master Phân
Title Style
typedef struct tagTNode
{
Data Key;
struct tagTNode *pLeft; Key
struct tagTNode *pRight;
}TNode;
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
typedef TNode *TREE;
7
- Ví Dụ Cây Được Tổ Chức Trong Bộ Nhớ
Click
Trong
To Edit Master Title Style
1f
2f 6 3f
3f
2f
Cấu trúc dữ liệu 1 vá thuật giải
7f 9 N
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
N 4 5f
5f 7f
N 5 N N 8 N
8
- Duyệt CâyTo
Click NhịEdit
PhânMaster Title Style
Có 3 trình tự thăm gốc :
Duyệt trước
Duyệt giữa
Duyệt sau
Cấu trúc dữ liệu 1 vá thuật giải
Độ phức tạp O (log2(h))
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
Trong đó h là chiều cao cây
9
- Ví Dụ Kết To
Click QuảEdit
CủaMaster
Phép Duyệt
TitleCây
Style
9
2 8
6 1
5 7
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
10
3 12 4
• NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4.
• LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4.
• Kết quả của phép duyệt : LRN, NRL,LRN, LNR?
10
- Duyệt Trước
Click To Edit Master Title Style
void NLR(TREE Root)
{
if (Root != NULL)
{
; //Xử lý tương ứng theo nhu cầu
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
NLR(Root->pLeft);
NLR(Root->pRight);
}
}
11
- Duyệt Giữa
Click To Edit Master Title Style
void LNR(TREE Root)
{
if (Root != NULL)
{
LNR(Root->pLeft);
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
; // Xử lý tương ứng theo nhu
cầu
LNR(Root->pRight);
}
}
12
- Duyệt SauTo
Click Edit Master Title Style
void LRN(TREE Root)
{
if (Root != NULL)
{
LRN(Root->pLeft);
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
LRN(Root->pRight);
; // Xử lý tương ứng theo nhu
cầu
}
}
13
- BiểuClick
Diễn Cây
To Tổng
EditQuát Bằng Title
Master Cây Nhị Phân
Style
A
B
E C
A
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
F H D
B C D
G I
J
E F G H I J
14
- Cách biểu diễn
Click cây nhịMaster
To Edit phân khác
Title Style
Đôi khi còn quan tâm đến cả quan hệ 2 chiều cha
con chứ không chỉ một chiều như định nghĩa. Cấu
trúc cây nhị phân như sau:
typedef struct tagTNode{
DataType Key;
Struct tagTNode* pParent;
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
Struct tagTNode* pLeft;
Struct tagTNode* pRight;
}TNODE;
Typedef TNODE* Tree;
Cây nhị phân tìm kiếm giúp dễ dàng trong tìm kiếm
thông tin.
15
- CâuClick
hỏi và To
Bài tập
Edit Master Title Style
1. Định nghĩa cây và cấu trúc cây.
2. Nêu một số tính chất của cây.
3. Nêu định nghĩa và một số ứng dụng của
cây nhị phân.
Cấu trúc dữ liệu 1 vá thuật giải
4. Nêu một số tính chất của cây nhị phân.
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
Cấu trúc biểu diễn cây nhị phân như thế
nào?
5. Trình bày các kiểu duyệt cây nhị phân.
16
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
