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

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.
Nội dung trích xuất từ tài liệu:
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ểnCây nhị phân(Binary Trees)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnĐịnh nghĩa• Cây nhị phân là cây, trong đó mỗi nút có không quá 2 conCài đặtCâ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ạngDuyệ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ố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ố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ố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ếpXây dựng cây: a b + c d e + * *• Đọc a, bXây dựng cây: a b + c d e + * *• Đọc +Xây dựng cây: a b + c d e + * *• Đọc c, d, eXây dựng cây: a b + c d e + * *• Đọc +Xây dựng cây: a b + c d e + * *• Đọc *Xây dựng cây: a b + c d e + * *• Đọc *