cấu trúc dữ liệu giải thuật3 (1).pptxadasd

data struction

1. 01 02 CÂY NHỊ PHÂN 03 CÀI ĐẶT CÂY 04 THUẬT TOÁN DUYỆT CÂY NHÓM 3 TỔNG QUÁT VỀ CÂY Ch8.Trees

2. THÀNH VIÊN NHÓM 3 Họ và Tên MSSV Nguyễn Quốc Bảo 23166012 Phan Minh Phú 23166081 Nguyễn Thị Kim Hân 23166022 Lữ Thị Kim Hạnh 23166023 Nguyễn Quốc Hoan 23166030 Lê Tài Đức 23166017 Lê Thị Thu Hiền 23166028

3. 01 TỔNG QUÁT VỀ CÂY

4. 1.1 Đ ịnh nghĩa về cây Cây là một tập nút: - Nếu tập nút rỗng, đó là cây rỗng. - Nếu tập nút không rỗng: Có một nút root được gọi là nút gốc. Có k cây con T₁, T₂, ..., Tₖ (k ≥ 0) sao cho nút gốc của mỗi cây con đó được nối với nút root bằng một cạnh. Nút root được gọi là nút cha, còn gốc của các cây con T₁, T₂, ..., Tₖ được gọi là các nút con của root.

5. VÍ DỤ :

6. 1.2 Định nghĩa đệ quy về cây Một nút tạo thành một cây. Nếu có n cây T₁, T₂, ..., Tn tách biệt có các nút gốc lần lượt là r₁, r₂, ..., rn; r là một nút có quan hệ cha-con với r₁, r₂, ..., rn thì tồn tại một cây mới T nhận r làm gốc.

7. 1.3 M ột số khái niệm cơ bản

8. 1.3 M ột số khái niệm cơ bản 1.Nút lá : Nút không có con (B, C, H...). 2. Nút anh em : Các nút cùng cha (K, L, M cùng cha là F). 3. Nút ông (E) và nút cháu (P, Q) 4. Đường đi từ nút n₁ đến nút nₖ : L à dãy nút n₁, n₂, ..., nₖ trong đó nᵢ là cha của nᵢ₊₁ (1 ≤ i < k).

9. 5. Chiều dài đường đi là số cạnh trên đường đi đó. Đường đi từ một nút tới chính nó có chiều dài bằng 0. 6. Chiều sâu của nút nᵢ : L à chiều dài đường đi từ nút gốc đến nút nᵢ. Nút gốc có chiều sâu 0. Chiều sâu của cây bằng chiều sâu của nút lá sâu nhất. 7. Chiều cao của nút nᵢ : L à chiều dài của đường đi dài nhất từ nút nᵢ đến một nút lá Nút lá có chiều cao 0. Chiều cao của cây bằng chiều cao của nút gốc. Chiều cao của cây = chiều sâu của cây 8. Nếu có đường đi từ nút n₁ đến nút n₂: Nút n₁ được gọi là tổ tiên của nút n₂, và nút n₂ được gọi là hậu duệ của nút n₁. Nếu n₁ ≠ n₂ thì ta có các khái niệm tổ tiên thực sự và hậu duệ thực sự.

10. 1.4 V í dụ về cây

11. 02 YOUR LOGO CÂY NHỊ PHÂN

12. Cây nhị phân là cây mà mỗi nút có tối đa hai cây con. Đối với cây con của một nút có phân biệt cây con trái và cây con phải . 2.1. Định nghĩa

13. 2.2 Một Số Tính Chất Của Cây Nhị Phân Số lượng tối đa các nút có ở mức i trên cây nhị phân là 2^(i-1) (i ≥ 1) Số lượng nút tối đa trên 1 cây nhị phân có chiều cao h là 2^h - 1 (h ≥ 1)

14. 2.3 Biểu Diễn Cây Nhị Phân - Lưu trữ kế tiếp: Phương pháp tự nhiên nhất để biểu diễn cây nhị phân là chỉ ra định con trái và định con phải của mỗi đỉnh. - Ta có thể sử dụng một mảng để lưu trữ các đỉnh của cây nhị phân. Mỗi đỉnh của cây được biểu gồm ba giá trị: Infor: Mô tả thông tin gắn với mỗi đỉnh Left: Chỉ định con trái Right: Chỉ định con phải

15. - Nếu cây nhị phân đầy đủ có thể lưu trữ cây này bằng mảng một chiều

16. - Nếu cây nhị phân không đầy đủ thì cách lưu trữ này không thích hợp vì phí nhiều bộ nhớ

17. Lưu trữ móc nối Cách lưu trữ này khắc phục nhược điểm của cách lưu trữ kế tiếp đồng thời phản ánh được dạng tự nhiên của cây. Cách lưu trữ này một phần tử có qui tắc sau: left info right Info : Mô tả thông tin gắn với mỗi đỉnh Left: Con trỏ tới cây con trái Right: Con trỏ tới cây con phải

18. 03 YOUR LOGO C ÀI ĐẶT CÂY

19. 3.1. Cài đặt cây Cài đặt cây thường được thực hiện bằng cách sử dụng lớp (class) để mô tả mỗi nút (node) trong cây. Sau đó, bạn liên kết các nút với nhau để tạo nên cấu trúc cây. 2 cách cài đặt cây phổ biến: Cây nhị phân (Binary Tree) Cây tổng quát (General Tree)

20. 3.2. Cấu trúc liên kết cho cây nhị phân Cây nhị phân (binary tree) có tối đa 2 phần tử con, cấu tạo chủ yếu gồm: Phần tử cha. Phần tử con trái và con phải.

21. Ưu điểm : Linh hoạt, dễ chèn/xoá nút. Nhược điểm : Tốn bộ nhớ do dùng nhiều con trỏ. 3.2. Cấu trúc liên kết cho cây nhị phân

22. 3.3. Cấu trúc liên kết cho cây tổng quát Cây tổng quát (general tree) không bị giới hạn phần tử con cho mỗi phần tử cha, có cấu tạo chủ yếu gồm: Phần tử cha. Nhiều phần tử con và phần tử con của con

23. Ưu điểm : Linh hoạt không giới hạn 2 như cây nhị phân , dễ chèn/xoá nút. Nhược điểm : Tốn bộ nhớ do dùng nhiều con trỏ, chậm hơn cây nhị phân , khó cân bằng: 3.3. Cấu trúc liên kết cho cây tổng quát

24. 04 YOUR LOGO THUẬT TOÁN DUYỆT CÂY

25. Thuật toán duyệt cây là phương pháp có hệ thống để truy cập tất cả các vị trí (nút) trong một cây. Mỗi lần "thăm" một nút có thể thực hiện các thao tác khác nhau tùy vào mục đích sử dụng, từ đơn giản như tăng bộ đếm đến các phép tính phức tạp. 4.1 Thuật Toán Duyệt Cây Tiền tự (pre-order) : Xử lý cha trước, rồi đến các con. Hậu tự (post-order) : Duyệt hết con rồi mới xử lý nút cha Trung tự (in-order): Duyệt con trái trước, xử lý gốc rồi mới duyệt con phải

26. Duyệt tiền thứ tự, hậu thứ tự và trung tự của cây tổng quát Pre-order: F, B, A, D, C,E, G, I, H Post-order: A, C, E, D, B, H, I, G, F In-order: A, B, C, D, E, F, G, I, H Tiền tự (pre-order) : Xử lý cha trước, rồi đến các con. Hậu tự (post-order) : Duyệt hết con rồi mới xử lý nút cha Trung tự (in-order): Duyệt con trái trước, xử lý cha rồi mới duyệt con phải

27. 4.2 Duyệt theo chiều rộng BFS (Breadth – First – Search ) Bạn có thể hình dung như đi từng tầng của cây , giống như quét các tầng trong một tòa nhà từ tầng 1 đến tầng 3. Duyệt theo chiều rộng sẽ đi theo thứ tự : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 - Là cách đi qua cây theo từng tầng, từ trên xuống dưới, từ trái qua phải.

28. - Vì sao dùng BFS (chiều rộng) trong trò chơi? - Trò chơi (X-O), chương trình cần: Xem tất cả các nước đi có thể xảy ra tại một lượt (ví dụ: lượt X đi trước). Sau đó mới xem tiếp các nước đi ở lượt kế tiếp (O đi sau). Mỗi tầng của cây là một lượt chơi. BFS sẽ duyệt tất cả các nước đi trong cùng một lượt, trước khi chuyển sang lượt kế tiếp.

29. 4.3 Duyệt theo chiều sâu DFS (Depth – First – Search ) DFS  (Duyệt theo chiều sâu) có  3 cách tiếp cận  khác nhau: Các loại DFS: Pre-order In-order Post-order DFS khi cài đặt sẽ mặc định chạy Pre-order Duyệt theo chiều sâu sẽ đi theo thứ tự : 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 -> 7 -> 8 DFS là một thuật toán duyệt hoặc tìm kiếm trên đồ thị hoặc cây , theo nguyên tắc: Đi càng sâu càng tốt trước , sau đó mới quay lại để đi các nhánh khác.

30. 4.4 Ứng dụng của duyệt cây trong thuật toán DFS hoạt động bằng cách: Đi càng sâu càng tốt theo một hướng. Nếu gặp ngõ cụt , quay lui (backtrack) để thử hướng khác. Lặp lại cho đến khi: Tìm thấy đường ra đầu tiên Đã duyệt hết mọi đường có thể. Rat In Maze

31. Cảm ơn thầy và các bạn đã lắng nghe! YOUR LOGO