zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ 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ển

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

Báo xấu

68
lượt xem 3
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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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

Cây nhị phân (Binary Trees) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
Định nghĩa • Cây nhị phân là cây, trong đó mỗi nút có không quá 2 con
Cài đặt
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
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ố
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ếp
Xây dựng cây: a b + c d e + * * • Đọc a, b
Xâ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, e
Xâ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 *

CÓ THỂ BẠN MUỐN DOWNLOAD

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 © 2022-2032 TaiLieu.VN. All rights reserved.