Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 7: Cây nhị phân tìm kiếm" cung cấp cho người học các kiến thức: Ðịnh nghĩa cây nhị phân tìm kiếm, ưu điểm của cây nhị phân tìm kiếm, cấu trúc dữ liệu của cây nhị phân tìm kiếm, tạo cây rỗng,... 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: Chương 7 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin)CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1Cấu trúc dữ liệu và thuật giải Click To Edit1 NỘIMaster CÂY NHỊ PHÂN TÌM KIẾM DUNGTitle Style Click Ðịnh nghĩaTo Edit cây Master nhị phân tìm Title kiếm Style • Cây nhị phân • Bảo đảm nguyên tắc bố trí khoá tại mỗi nút: – Các nút trong cây trái nhỏ hơn nút hiện hành – Các nút trong cây phải lớn hơn nút hiện hành Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Ví dụ: 18 13 37 15 23 40 2 Ưu Click To cây điểm của Editnhị Master Title phân tìm kiếmStyle • Nhờ trật tự bố trí khóa trên cây : – Định hướng được khi tìm kiếm • Cây gồm N phần tử : – Trường hợp tốt nhất h = log2N Cấu trúc dữ liệu và thuật giải – Trường hợp xấu nhất h = LnCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 – Tình huống xảy ra trường hợp xấu nhất ? 3 CấuClick Toliệu trúc dữ Edit củaMaster cây nhị Title phân Style tìm kiếm • Cấu trúc dữ liệu của 1 nút typedef struct tagTNode { int Key; //trường dữ liệu là 1 số nguyên struct tagTNode *pLeft; Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 struct tagTNode *pRight; }TNode; • Cấu trúc dữ liệu của cây typedef TNode *TREE; 4 CácClick To trên thao tác Editcây Master Title nhị phân tìmStyle kiếm Tạo 1 cây rỗng Tạo 1 nút có trường Key bằng x Thêm 1 nút vào cây nhị phân tìm kiếm Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Xoá 1 nút có Key bằng x trên cây Tìm 1 nút có khoá bằng x trên cây 5 TạoClick To Edit cây rỗng Master Title Style • Cây rỗng -> địa chỉ nút gốc bằng NULL void CreateTree(TREE &T) { T ...