›
›

Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 9: Cây nhị phân (Binary Trees)

pdf 14 trang phuongnguyen 3170
Download
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 9: Cây nhị phân (Binary Trees)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_giai_thuat_data_structures_algori.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 9: Cây nhị phân (Binary Trees)

  1. Cây nhị phân (Binary Trees) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
  2. Định nghĩa • Cây nhị phân là cây, trong đó mỗi nút có không quá 2 con
  3. Cài đặt
  4. Cây biểu thức • Cây biểu thức là một cây nhị phân, trong đó: − Nút trong lưu trữ toán tử − Nút lá lưu trữ toán hạng
  5. Duyệt cây biểu thức theo thứ tự giữa (inorder traversal) • Trình tự: con trái, nút đang xét, con phải • Đầu ra: biểu thức trung tố
  6. Duyệt cây biểu thức theo thứ tự sau (postorder traversal) • Trình tự: con trái, con phải, nút đang xét • Đầu ra: biểu thức hậu tố
  7. Duyệt cây biểu thức theo thứ tự trước (preorder traversal) • Trình tự: nút đang xét, con trái, con phải • Đầu ra: biểu thức tiền tố
  8. Xây dựng cây biểu thức • Xét trường hợp biểu thức hậu tố (ví dụ: a b + c d e + * *) • Cách làm: − Đọc từng ký tự từ trái sang phải − Toán hạng tạo nút đặt con trỏ tới nút vào ngăn xếp − Toán tử lấy hai con trỏ từ ngăn xếp (trỏ tới hai cây T1 và T2) tạo nút toán tử trỏ tới T1 và T2 đặt con trỏ tới nút toán tử vào ngăn xếp
  9. Xây dựng cây: a b + c d e + * * • Đọc a, b
  10. Xây dựng cây: a b + c d e + * * • Đọc +
  11. Xây dựng cây: a b + c d e + * * • Đọc c, d, e
  12. Xây dựng cây: a b + c d e + * * • Đọc +
  13. Xây dựng cây: a b + c d e + * * • Đọc *
  14. Xây dựng cây: a b + c d e + * * • Đọc *