intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài giảng Cấu trúc dữ liệu và giải thuật: Cây nhị phân - Nguyễn Mạnh Hiển

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:14

65
lượt xem
2
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ây nhị phân" trình bày các định nghĩa về cây nhị phân, cây biểu thức, duyệt cây biểu thức theo thứ tự giữa, duyệt cây biểu thức theo thứ tự sau, xây dựng cây biểu thức. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Cây nhị phân - Nguyễn Mạnh Hiển

  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 *
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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