Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc cây

Chia sẻ: _ _ | Ngày: | Loại File: PPTX | Số trang:140

Thêm vào BST

Báo xấu

11
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cấu trúc cây" được biên soạn với các nội dung chính sau đây: Khái niệm cấu trúc cây; Phép duyệt cây và Biểu diễn cây; Cây nhị phân và Cây nhị phân tìm kiếm; Cây AVL; Cây AA. Mời các bạn cùng tham khảo bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc cây

Cấu trúc dữ liệu và giải thuật Cấu trúc cây Giảng viên: Văn Chí Nam
Nội dung trình bày 2 Cấu trúc dữ liệu và giải thuật HCMUS 2011
3 Khái niệm Cấu trúc dữ liệu và giải thuật HCMUS 2011
Một số thuật ngữ 4  Tree  Search tree  Binary search tree  Balanced tree  AVL tree  AA tree  Red-Black tree  … Cấu trúc dữ liệu và giải thuật HCMUS 2011
Cây tổng quát 5 Cấu trúc dữ liệu và giải thuật HCMUS 2011
Cây tổng quát 6 Sơ đồ tổ chức Cây thư mục Cấu trúc dữ liệu và giải thuật HCMUS 2011
Định nghĩa 7 Cây (cây có gốc) được xác định đệ quy như sau: 1. Tập hợp gồm 1 đỉnh là một cây. Cây này có gốc là đỉnh duy nhất của nó. 2. Gọi T1, T2, … Tk (k ≥ 1) là các cây không cắt nhau có gốc tương ứng r1, r2, … rk. Giả sử r là một đỉnh mới không thuộc các cây Ti. Khi đó, tập hợp T gồm đỉnh r và các cây Ti tạo thành một cây mới với gốc r. Các cây T1, T2, … Tk được gọi là cây con của gốc r. Cấu trúc dữ liệu và giải thuật HCMUS 2011
Định nghĩa 8 r Nút gốc r r r 1 2 k T1 T2 Tk Cây con Cấu trúc dữ liệu và giải thuật HCMUS 2011
Các khái niệm 9  node: đỉnh  root: gốc cây  leaf: lá  inner node/internal node: đỉnh trong  parent: đỉnh cha  child: đỉnh con  path: đường đi Cấu trúc dữ liệu và giải thuật HCMUS 2011
Các khái niệm 10 r Nút gốc rk r r r 1 2 k k k 1 2 T1 T2 Tk k k k 3 4 5 Cây con Nút lá Đường đi k Cấu trúc dữ liệu và giải thuật HCMUS 2011 6
Các khái niệm 11  degree/order: bậc  Bậc của node: Số con của node  Bậc của cây: bậc lớn nhất trong số các con  depth/level: độ sâu/mức  Mức (độ sâu)của node: Chiều dài của đường đi từ node gốc đến node đó cộng thêm 1.  height: chiều cao  Chiều cao cây: Cấu trúc dCây rỗng:ải thu 0 ật HCMUS 2011  ữ liệu và gi
Các khái niệm 12 Bậc = k r Nút gốc Bậc = 2 Độ cao = 4 rk r r r 1 2 k k k 1 2 T1 T2 Tk k k k 3 4 5 Cây con Nút lá Đường đi k Cấu trúc dữ liệu và giải thuật HCMUS 2011 6
13 Phép duyệt cây Cấu trúc dữ liệu và giải thuật HCMUS 2011
Phép duyệt cây 14  Đảm bảo đến mỗi node trên cây chính xác một lần một cách có hệ thống.  Nhiều thao tác xử lý trên cây cần phải sử dụng đến phép duyệt cây.  Các phép cơ bản:  Duyệt trước (Preorder) Cấu trúc dữ liệu và giải thuật HCMUS 2011
Phép duyệt cây 15 Parent(a)? Parent(b) = a Eldest- a Child(c) = g b c d e f g h NextSibling(g) = h i NextSibling(h)? Cấu trúc dữ liệu và giải thuật HCMUS 2011
Phép duyệt cây 16 Duyệt theo chiều sâu a b c d e f g h i j k Cấu trúc dữ liệu và giải thuật HCMUS 2011
Phép duyệt cây 17  Pre-order  Post-order void Preorder(NODE A) void Postorder(NODE A) { { NODE B; NODE B; Visit(A); B = EldestChild(A); B = EldestChild(A); while (B != ) { while (B != ) { Preorder(B); Postorder(B); B = NextSibling(B); B = Cấu trúc d ữ li ệu và giả i thu ật HCMUS 2011 NextSibling(B); }
Phép duyệt cây 18 In-Order void Inorder(NODE A) { NODE B; B = EldestChild(A); if (B != ) { Inorder(B); B = NextSibling(B); } Visit(A); while (B != ) { Inorder(B); B = NextSibling(B); } } Cấu trúc dữ liệu và giải thuật HCMUS 2011
19 Biểu diễn cây Cấu trúc dữ liệu và giải thuật HCMUS 2011
Bằng danh sách cây con 20 info child id next 1 a 2 3 2 b 4 5 a 6 7 8 3 c 4 d 9 10 5 e b c 6 f 11 7 g d e f g h 8 h 9 i i j k 10Cấu trúc d j ữ liệu và giải thuật HCMUS 2011