Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây nhị phân tìm kiếm" cung cấp cho người đọ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, nội dung chi tiết. | NỘI DUNG CÂY NHỊ PHÂN TÌM KIẾM ưu điểm của cây nhị phân tìm kiếm 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 Ịj -Trường hợp xấu nhất h LnN -Tình huống xảy ra trường hợp xấu nhất Õ 5 p LLJ- ạ Q y Ọ Q Định nghĩa cây nhị phân tìm kiếm 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ấu trúc dữ liệu của cây nhị phân 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 I struct tagTNode pRight TNode Ị Cấu trúc dữ liệu của cây typedef TNode TREE pí H ọ U 1 r Các thao tác trên cây nhị phân tìm 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 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 Tạo 1 nút có Key bằng X TNode CreateTNode int x TNode p p new TNode cấp phát vùng nhớ động if p NULL exit 1 thoát else p- key x gán trường dữ liệu của nút X p- pLeft NULL p- pRight NULL return p Thêm một nút X Răng buôc Sau khi thêm cây đảm bảo là cây nhị phân tìm kiếm. int insertNode TREE T Data X íf T if T- Key X return 0 if T- Key X return insertNode T- pLeft X else return insertNode T- pRight X T newTNode if T NULL return-1 T- Key X T- pLeft T- pRight NULL 2 Tìm nút có khoá bằng X không dùng đệ quy 0 TNode searchNode TREE Root Data x Node p Root while p NULL if x p- Key return p else if x p- Key p p- pLeft else p p- pRight return NULL 10 Minh hoạ tìm một nút 12