Các khái niệm

Danh sách lien kết
- Khái niệm: Danh sách liên kết là 1 cấu trúc dữ liệu bao gồm 1 tập các phần tử, trong đó mỗi phần tử là 1 phần của 1 nút có chứa một liên kết tới nút kế tiếp
- Mói tiếp nhau thong qua vùng liên kết
- Cách truy cập : Tuần tự
- Thay đổi vị trí cần thay đổi các liên kết của 1 số pt liên quan
- Kích thước: không cần khai báo trước
- Gồm: liên kết vòng và liên kết kép
- Các tác vụ: khởi tạo(init), kiểm tra DSLK rỗng(IsEmpty), Xác định kick thước(Size),Chèn(Insert), Xóa(Remove), Tìm kiếm(Retrieve), Thay thế(Replace),Duyệt(Traverse)
Stack:
- Định nghĩa: Là 1 cấu trúc dữ liệu có 2 thao tác cơ bản: bổ sung (push) và loại bỏ phần tử (pop), trong đó việc loại bỏ sẽ tiến hành loại phần tử mới nhất được đưa vào danh sách
- Thêm Stack: thêm ở đầu
- Nguyên tắc: FILO hay LIFO
- Cài đặt: Mảng hoặc dslk
Queue:
- ĐỊnh nghĩa: Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu, gọi là lối sau (rear) và phép loại bỏ một phần tử được thực hiện ở đầu kia, gọi là lối trước (front).
- Loại bỏ: không thể thực hiện nếu hàng đợi rỗng
- Bổ sung: nếu đầy không thể thực hiện
- Thêm phẩn tử vào lối sau(rear)
- Nguyên tắc:FIFO hay LILO
- CÀi đặt: = mảng hoặc dslk



CÂY
- khái niệm: là một tập hợp các nút (các đỉnh) và các cạnh, thỏa mãn một số yêu cầu nào đó.
- Có 1 nút gốc( nằm ở vị trí cao nhất)
- Mỗi nút có 1 nút cha
- Nút không có cha là nút lá
- Chiều cao nút là đg đi dài nhất từ nút tớ 1 lá
- Chiều cao cây là chiều cao của gốc
- Cài đặt:Bằng mảng các nút cha hoặc thông qua danh sách các nút con
CÂY NHỊ PHÂN:
- định nghĩa: Cây nhị phân là một loại cây đặc biệt mà mỗi nút của nó chỉ có nhiều nhất là 2 nút con. Khi đó, 2 cây con của mỗi nút được gọi là cây con trái và cây con phải.
- Cài đặt: bằng dslk có 3 thành phần là Item, left, right
- Đối với cây nhị phân đầy đủ ta nên cài đặt bằng mản, không đầy đủ cài bằng dslk
-



CÂY NHỊ PHÂN TÌM KIẾM
- Là cây nhị phân có tính chất khóa của nút con bên trái bao giờ cũng nhỏ hơn khóa của nút cha, còn khóa của cây con bên phải bao giờ cũng lớn hơn hoặc bằng khóa của nút cha.


Duyệt cây
Trước: Gốc, Trái , Phải
Giữa: Trái, gốc, phải
Sau:Trái, phải, gốc