VIỆN ĐẠI HỌC MỞ HÀ NỘI
KHOA CÔNG NGHỆ TIN HỌC
----    ----
BÁO CÁO ĐỀ TÀI
BÀI TẬP LỚN C++
Lớp 0209A1
Tên bài : Xây dựng cây nhị phân tìm kiếm
Nhóm làm gồm: Nguyễn Hữu Đức
Dương Thúy Lan
Giáo viên hướng dẫn: TS.Trương Tiến Tùng
ThS.Trương Công Đoàn

HÀ NỘI 2009
1

Mục lục
Phần 1: Giới thiệu đề tài.
Phần 2: Phân tích, thiết kế chương trình
Phần 3: Giới thiệu các phương thức quan trọng trong
chương trình

Phần 4: Kết luận
Phần 1: Giới thiệu đề tài
2

Ngày nay, khi ngành công nghệ thông tin ngày càng phát triển, khoa
học máy tính không ngừng vươn tới những tìm tòi mới mẻ hơn, mọi người
chủ yếu làm việc dựa trên máy móc và thiết bị điện tử thì các phần mềm ứng
dụng lại càng trở nên quan trọng và hữu ích hơn bao giờ hết. Tất cả các
thông tin muốn biết, muốn tìm hiểu bạn đều có thể tìm được trên mạng

Các nút lá
Các nút không có nút con được gọi là nút lá hay gọi đơn giản là lá.
Các nút trong
Nút trong của một cây là nút trên cây có ít nhất một con, nghĩa là các nút không
phải là lá. Các khái niệm về mức của mỗi nút, chiều cao của cây được định nghĩa giống
như cây trong lý thuyết đồ thị.
Cây con
Một cây con là một bộ phận của cấu trúc dữ liệu cây mà tự nó cũng là một cây. Một
nút bất kỳ trong cây T, cùng với các nút dưới nó tạo thành một cây con của T.
Cây trong lý thuyết đồ thị
Trong lý thuyết đồ thị, một cây là một đồ thị liên thông và không có chu trình. Cây
như vậy còn được gọi là cây tự do. Một cây có gốc là một cây tư do, trong đó có một đỉnh
được chọn làm gốc và các cạnh được định hướng là hướng của các đường đi đơn ra khỏi
gốc tới các đỉnh khác. Trong trường hợp này, hai đỉnh bất kỳ dược nối với nhau bao hàm
chúng có qua hệ cha-con. Một đồ thị không chu trình với nhiều thành phần liên thông được
gọi là một rừng.
4

Cây sắp thứ tự
Có hai dạng cấu trúc cơ sở của cây là không không thứ tự và cây có thứ tự. Một cây
không thứ tự là cây có cấu trúc cây, trong đó giữa các con của một nút, không có thứ tự
nào. Một cây, trong đó các con của một nút tuân theo một thứ tự xác định được gọi là cây
có thứ tự. Các cây có thứ tự có nhiều ứng dụng sâu sắc trong cấu trúc của cây. Cây tìm
kiếm nhị phân là một cây sắp thứ tự điển hình.
Cây tổng quát và cây nhị phân
Các cây trong đó mỗi nút có thể có nhiều hơn hai con được gọi là cây tổng quát,
các cây trong đó mỗi nút có không quá hai con được gọi là cây nhị phân.
Biểu diễn cây
Có nhiều phương pháp biểu diễn cây. Cách thường dùng nhất là biểu diễn mỗi nút
như một dữ liệu kiểu bản ghi, mỗi nút chứa các con trỏ tới các con hoặc cha của nó, hoặc

Các phương pháp duyệt cây
Duyệt một cây là một trình tự làm việc với các nút trong cây, trình tự này giống
như một chuyến đi qua các nút trên cây theo các liên kết cha-con. Các giải thuật duyệt khác
nhau về thứ tự “viếng thăm” giữa một nút cha và các nút con. Chúng được gọi là duỵệt tiền
thứ tự, nếu viếng thăm đỉnh cha trước rồi mới đến các con, là duyệt hậu thứ tự nếu viếng
thăm hết các con rồi mới đến cha.
6

B. Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân (viết tắt tiếng Anh: BST - Binary Search Tree) là một cấu
trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm.
Định nghĩa
Cây tìm kiếm nhị phân
Cây tìm kiếm ứng với n khóa k
1
,k
2
,...k
n
là cây nhị phân mà mỗi nút đều được gán một
khóa sao cho với mỗi mỗi nút k:
• Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
• Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k
Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các
cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp.
Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại
này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ
hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn hoặc bằng khóa của nút
cha.
Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một tập hợp đơn trị