intTypePromotion=1
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 4: Khái niệm cơ bản về cây

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:38

Thêm vào BST
Báo xấu
180
lượt xem 22
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 4: Khái niệm cơ bản về cây trình bày một số khái niệm cơ bản của cây, một số tính chất của cây, phép duyệt cây nhị phân, cây khung,... Mời các bạn cùng tham khảo.

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 Toán rời rạc ứng dụng trong tin học - Chương 4: Khái niệm cơ bản về cây

  1. TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC KHÁI NIỆM CƠ BẢN VỀ CÂY 1
  2. Một số khái niệm cơ bản  Cây  Định nghĩa:  Cây là một đồ thị vô hướng, liên thông và không có chu trình sơ cấp  Cây không có cạnh bội và khuyên  Cây là một đơn đồ thị  Ví dụ G1 G2 G G3 G4 Chương 2. Cây 2
  3. Một số khái niệm cơ bản  Rừng  Định nghĩa:  Rừng là một đồ thị vô hướng và không có chu trình  Rừng có thể có nhiều thành phần liên thông  Mỗi thành phần liên thông là một cây  Ví dụ G Chương 2. Cây 3
  4. Một số khái niệm cơ bản  Định lý (Điều kiện đủ của cây)  Nếu mọi cặp đỉnh của một đồ thị vô hướng G luôn tồn tại một đường đi sơ cấp thì G là một cây  Chứng minh  SV tham khảo tài liệu Chương 2. Cây 4
  5. Một số khái niệm cơ bản  Cây có gốc  Định nghĩa  Một cây với một đỉnh được chọn làm gốc  Định hướng các cạnh trên cây từ gốc đi ra  Ví dụ a e d a f b b e g d f b e c c a c h d f g h g h  Cùng một cây, nếu chọn gốc khác nhau thì cây có gốc thu được sẽ khác nhau Chương 2. Cây 5
  6. Một số khái niệm cơ bản  Cây có gốc  Một số khái niệm  Cha  Lá  Anh em  Đỉnh trong  Tổ tiên  Cây con  Con cháu  Mức  Chiều cao Chương 2. Cây 6
  7. Một số khái niệm cơ bản  Định lý Daisy Chain T là đồ thị có n đỉnh. Các mệnh đề tương đương: 1. T là một cây 2. T không có chu trình và có n-1 cạnh 3. T liên thông, mọi cạnh đều là cầu 4. Giữa hai đỉnh bất kỳ của T luôn tồn tại một đường đi sơ cấp duy nhất 5. T không có chu trình và T U {e} có chu trình 6. T liên thông và có n-1 cạnh Chương 2. Cây 7
  8. Một số khái niệm cơ bản  Cây m-phân  Định nghĩa  Cây m-phân  Cây có gốc  Tất cả các đỉnh trong có không quá m con  Cây m-phân đầy đủ  Tất cả các đỉnh trong có không quá m con  m=2: Cây nhị phân Chương 2. Cây 8
  9. Một số khái niệm cơ bản  Cây m-phân  Ví dụ T1 T2 T3  T1: Cây nhị phân đầy đủ  T2: Cây tam phân đầy đủ  T3: Cây tứ phân (không đầy đủ) Chương 2. Cây 9
  10. Một số tính chất của cây  Tính chất 1  Cây n đỉnh (n ≥ 2) có ít nhất 2 đỉnh treo  Tính chất 2  Cây m-phân đầy đủ với i đỉnh trong có n = m.i + 1  Tính chất 3  i = (n -1)/m  l = [(m - 1)n + 1] / m  l = (m - 1)i + 1  n=l+i Chương 2. Cây 10
  11. Phép duyệt Cây nhị phân  Định nghĩa  Duyệt cây  Liệt kê các đỉnh theo một thứ tự xác định, mỗi đỉnh một lần  Thường được đỉnh nghĩa đệ quy cho các cây con  3 phương pháp duyệt cây  Duyệt tiền tự (Pre-Oder)  Duyệt trung tự (In-Oder)  Duyệt hậu tự (Post-Oder) Chương 2. Cây 11
  12. Phép duyệt Cây nhị phân  Định nghĩa  Duyệt tiền tự 1. Duyệt nút gốc 2. Duyệt tiền tự con trái 3. Duyệt tiền tự con phải 1 2 3 Chương 2. Cây 12
  13. Phép duyệt Cây nhị phân  Định nghĩa  Duyệt trung tự 1. Duyệt trung tự con trái 2. Duyệt nút gốc 3. Duyệt trung tự con phải 2 1 3 Chương 2. Cây 13
  14. Phép duyệt Cây nhị phân  Định nghĩa  Duyệt hậu tự 1. Duyệt hậu tự con trái 2. Duyệt hậu tự con phải 3. Duyệt nút gốc 3 1 2 Chương 2. Cây 14
  15. Phép duyệt Cây nhị phân  Định nghĩa  Ví dụ A  Duyệt tiền tự  ABDECF B C  Duyệt trung tự E  DBEACF D F  Duyệt hậu tự  DEBFCA Chương 2. Cây 15
  16. Ký pháp nghịch đảo Ba Lan  Cây biểu thức số học  Là cây nhị phân  Mỗi nút trong biểu diễn cho toán tử 2 ngôi θ  Biểu diễn cho biểu thức E1 θ E2  Con trái biểu diễn cho biểu thức E1  Con phải biểu diễn cho biểu thức E2  Mỗi nút lá biểu diễn cho một toán hạng Chương 2. Cây 16
  17. Ký pháp nghịch đảo Ba Lan  Cây biểu thức số học  Ví dụ E = (2 + 3)*2 – (4 – 1)*(15/5) Chương 2. Cây 17
  18. Ký pháp nghịch đảo Ba Lan  Cây biểu thức số học  Duyệt cây biểu thức  Biểu thức tiền tố  Biểu thức trung tố  Biểu thức hậu tô Chương 2. Cây 18
  19. Ký pháp nghịch đảo Ba Lan  Cây biểu thức số học  Ký pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN)  Biểu thức ở dạng hậu tố  Ví dụ: 5 1 2 + 4 * + 3 –  Sử dụng để tính giá trị biểu thức trên máy tính  Tính từ trái qua phải  Không sử dụng dấu ngoặc  Sử dụng Stack (ngăn xếp) Chương 2. Cây 19
  20. Ký pháp nghịch đảo Ba Lan  Cây biểu thức số học  Ký pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN)  Thuật toán tính giá trị biểu thức RPN  Đọc một ký hiệu (token)  Nếu ký hiệu là một số  Đẩy vào Stack  Ngược lại, ký hiệu là một toán tử  Lấy ra 2 toán hạng từ Stack  Tính giá trị theo toán tử đối với 2 toán h ạng  Đẩy kết quả vào Stack Chương 2. Cây 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD


intNumView=180
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2