Báo cáo bài tập lớn cấu trúc dữ liệu và giải thuật đề tài cài đặt cây nhị phân tìm kiếm

Trên tập hợp các nút này có một quan hệ phân cấp gọi là quan hệ "cha - con".Cây nhị phân tìm kiếm binary search tree – BST là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn

TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI

KHOA CÔNG NGHỆ THÔNG TIN

-BÁO CÁO BÀI TẬP LỚN MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

ĐỀ TÀI: CÀI ĐẶT CÂY NHỊ PHÂN TÌM KIẾM

Giảng viên hướng dẫn: ThS Nguyễn Thị Tâm Sinh viên thực hiện: Nguyễn Long Thành – 18A4

Đỗ Mạnh Thắng – 18A2

Đỗ Minh Quân – 19A3

Hà Nội – Năm 2020

MỤC LỤC

Lời mở đầu 3

Phân công công việc 4

I CƠ SỞ LÝ THUYẾT 5

1.1 Cây nhị phân tìm kiếm 5

1.2 Một số khái niệm 5

II MÔ TẢ CÁC THAO TÁC TRÊN CÂY NHỊ PHÂN TÌM KIẾM 6

2.1 Khai báo cài đặt cây nhị phân 6

2.2 Hàm khởi tạo rỗng 6

2.3 Hàm kiểm tra rỗng 6

2.4 Hàm thêm một nút 7

2.5 Hàm xóa một nút 7

2.6 Hàm nhập một cây tìm kiếm nhị phân 7

2.7 Hàm duyệt cây 7

2.7.1 Duyệt theo thứ tự trước 7

2.7.2 Duyệt theo thứ tự giữa 7

2.7.3 Duyệt theo thứ tự sau 8

2.8 Hàm xác định số nút của cây 8

2.9 Hàm xác định chiều cao của cây 8

2.10 Hàm xác định mức của cây 8

III CHƯƠNG TRÌNH MINH HỌA 9

3.1 Xây dựng chương trình 9

3.2 Kết quả 16

TÀI LIỆU THAM KHẢO 17

Lời mở đầu

Cùng với sự phát triển của khoa học kĩ thuật , công nghệ thông tin nói chung và bộ môn cấu trúc dữ liệu và giải thuật nói riêng ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực Với một cơ sở dữ liệu khổng lồ, việc đưa ra một phương pháp nhằm giải quyết vấn đề tìm kiếm dữ liệu có hiệu quả và nhanh chóng nhất luôn được sự quan tâm của các nhà phát triển phần mềm Thông thường dữ liệu được biểu diễn dưới dạng danh sách liên kết Việc truy suất dữ liệu chưa đạt hiệu quả cao Sử dụng cấu trúc dữ liệu cây là một giải pháp làm tăng hiệu suất trong các thao tác xử lý Vấn đề đặt ra : với việc sử dụng cấu trúc dạng cây, chúng ta cần dùng giải thuật nào với từng dạng dữ liệu để đạt hiệu quả cao nhất Để giải quyết vấn đề trên ta cùng tìm hiểu một số phương pháp duyệt cây

Phân công công việc

Họ tên Phân công công việc Đánh giá kết

Nguyễn Long

Thành

Làm phần I và phần II Sửa lại chương trình và Kiểm thử

Đỗ Mạnh Thắng Xây dựng chương trình

và Kiểm thử

Đỗ Minh Quân Sửa lại chương trình và

Kiểm thử Sửa những lỗi nhỏ trong bài tập lớn

I CƠ SỞ LÝ THUYẾT

I.1 Cây nhị phân tìm kiếm

Cây (Trees) là một tập hợp hữu hạn các phần tử gọi là nút cây (Node), trong

đó có một nút đặc biệt gọi là nút gốc (Root) Trên tập hợp các nút này có một quan hệ phân cấp gọi là quan hệ "cha - con"

Cây nhị phân tìm kiếm (binary search tree – BST) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn nút khóa của tất cả các nút thuộc cây con trái và nhỏ hơn tất cả nút khóa thuộc cây con phải

Ví dụ

I.2 Một số khái niệm

Một nút đơn độc cũng là một cây

Tập hợp rỗng cũng là một cây mà ta gọi là cây rỗng

Mức của một nút :

+ Nút gốc : Mức 0

+ Các nút cách nút gốc i cạnh được gọi là nút ở mức i Nút gốc (Root): Là nút không có nút cha

Nút lá (leaf): Là nút không có nút con

Chiều cao của một nút: Là độ dài đường đi từ nút đó đến nút lá xa nhất Chiều cao của một cây: Là chiều cao của nút gốc

Bậc của một nút: Là số nút con của nút đó

Bậc của một cây: Là bậc cao nhất của các nút trong cây

II MÔ TẢ CÁC THAO TÁC TRÊN CÂY NHỊ PHÂN TÌM KIẾM

II.1 Khai báo cài đặt cây nhị phân

Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết ứng với một nút của, ta dùng một biến động lưu trữ các thông tin

Thông tin lưu trữ tại nút

Địa chỉ nút gốc của cây con trái trong bộ nhớ

Địa chỉ của nút gốc của cây con phải trong bộ nhớ

Khai báo tương ứng như sau:

#include<stdlib.h>

#include<stdio.h>

typedef int item ;

struct NODE

{

int key;

NODE *Left, *Right;

typedef NODE *TREE;

II.2 Hàm khởi tạo rỗng

void khoitaorong(TREE &T){

T=NULL;

}

II.3 Hàm kiểm tra rỗng

int ktrarong(TREE T){

if(T==NULL)

return 1;

else

return 0;

}

II.4 Hàm thêm một nút

Hàm này cho phép chúng ta nhập thêm một số vào dãy số mà ta đã nhập và xét số đó để sắp xếp vào vị trí của một nút trong cây

Xảy ra hai trường hợp:

Cây rỗng

Cây không rỗng

- Nếu X trùng với gốc thì ta không thể thêm node

- Nếu X< gốc và chưa có lá con bên trái thì thực hiện thêm vào bên trái

- Tương tự X> gốc thì ta thêm vào bên phải

II.5 Hàm xóa một nút.

Hàm cho phép ta xóa một nút trong cây tìm kiếm nhị phân

Xảy ra hai trường hợp

Cây rỗng

Cây khác rỗng

- X là nút lá

- X chỉ có một con trái (phải)

- X có đủ cả hai con

Xây dựng thêm hàm tìm kiếm

- Hàm tìm kiếm có nhiệm vụ xác định vị trí của nút cần xóa

II.6 Hàm nhập một cây tìm kiếm nhị phân

- Cho phép ta nhập n số ta muốn, n số đó sẽ tạo thành n nút trong cây nhị phân

- Hàm còn làm thêm nhiệm vụ sắp xếp vị trí đứng của các nút vừa nhập

II.7 Hàm duyệt cây

II.7.1 Duyệt theo thứ tự trước

Hàm có nhiệm vụ:

- Thăm nút gốc

- Thăm các nút gốc của cây con trái theo thứ tự trước

- Thăm các nút gốc của cây con phải theo thứ tự trước

II.7.2 Duyệt theo thứ tự giữa

Hàm có nhiệm vụ:

- Thăm các nút gốc của cây con trái theo thứ tự giữa

- Thăm nút gốc

- Thăm các nút gốc của cây con phải theo thứ tự giữa

II.7.3 Duyệt theo thứ tự sau

Hàm có nhiệm vụ sau:

- Thăm các nút gốc của cây con trái theo thứ tự sau

- Thăm các nút gốc của cây con phải theo thứ tự sau

- Thăm nút gốc

II.8 Hàm xác định số nút của cây

Sử dụng hàm để đếm xem trên cây có tất cả bao nhiêu nút

Xảy ra 2 trường hơp:

Cây rỗng số nút trên cây là 0

Cây không rỗng: thì chiều cao cây sẽ tổng các nút bên trái và nút bên phải của cây cộng với 1 ( 1 là nút gốc)

II.9 Hàm xác định chiều cao của cây

Hàm này sử dụng để tính chiều cao của cây nhị phân tức là đếm số tầng của cây tìm kiếm nhị phân

Ta có các trường hợp sau:

Trường hợp cây rỗng thì xuất ra chiều cao của cây là -1

Cây khác rỗng:

- Không có cây con bên trái và bên phải thì chiều cao của cây là 0

- Có cả cây con bên trái và bên phải thì chiều cao là 1+ cây bên trái + cây bên phải

- Cây cực trái hoặc cây cực phải thì chiều cao của cây là 1+ cây bên trái hoặc 1 + cây bên phải

II.10 Hàm xác định mức của cây

Hàm này sử dụng để xác định mức của một nút bất kỳ mà nười sử dụng cần xác định, nút được nhập từ bàn phím.có sử dụng biếm đếm, mỗi lần như thế lại cộng thêm một giá trị

III CHƯƠNG TRÌNH MINH HỌA

III.1 Xây dựng chương trình

Đề bài: Cây nhị phân tìm kiếm.

Viết chương trình cài đặt một cây tìm kiếm nhị phân (nhãn của mỗi nút được nhập từ bàn phím)

Yêu cầu chi tiết:

1 Viết phần khai báo để cài đặt một cây tìm kiếm nhị phân

2 Viết thủ tục khởi tạo cây rỗng

3 Viết hàm kiểm tra cây rỗng

4 Viết thủ tục xen một nút vào cây tìm kiếm nhị phân

5 Viết thủ tục xóa một nút trong cây tìm kiếm nhị phân

6 Viết thủ tục nhập một cây tìm kiếm nhị phân với nhãn của các nút của cây được nhập vào từ bàn phím

7 Viết các thủ tục duyệt cây: Duyệt tiền tố, trung tố, hậu tố

8 Viết hàm xác định số nút trong cây

9 Thiết kế hàm xác định chiều cao của cây

10 Viết hàm xác định mức của một nút trong cây

BÀI LÀM

// phan khai bao

#include<stdlib.h>

#include<stdio.h>

typedef int item ; //kieu item la kieu nguyen

struct NODE

{

int key; //truong key cua du lieu

NODE *Left, *Right; //con trai va con phai

};

int nmax(int a,int b){

return a>=b?a:b;

}

int d=0;

typedef NODE *TREE; //cay

// khoi tao rong

void khoitaorong(TREE &T){

T=NULL;

}

// ktra rong

int ktrarong(TREE T){

if(T==NULL)

return 1;

else

return 0;

}

// ham them nut

int themnut(TREE &T, int x) // chen 1 Node vao cay {

if (T != NULL)

{

if (T->key == x) return -1;

if (T->key > x) return themnut(T->Left, x); else if (T->key < x) return themnut(T->Right, x); }

T = (NODE *) malloc(sizeof(NODE));

if (T == NULL) return 0;

T->key = x;

T->Left = T->Right = NULL;

return 1;

}

// ham nhap

void nhap(TREE &T) // nhap cay

{

int x, tl=1;

while (tl)

{

printf("\n Nhap vao Node: ");

scanf("%d", &x);

int check = themnut(T, x);

if (check == -1) printf("\n\n Node da ton tai!"); else if (check == 0) printf("\n Khong du bo nho"); printf("\n Ban co muon tiep tuc khong <0/1>");

scanf("%d",&tl);

}

}

// Duyet theo thu tu truoc

void NLR(TREE T)

{

if(T!= NULL)

{

printf("%d ",T->key);

NLR(T->Left);

NLR(T->Right);

}

}

// duyet theo thu tu giua

void LNR(TREE T)

{

if(T!=NULL)

{

LNR(T->Left);

printf("%d ", T->key);

LNR(T->Right);

}

// duyet theo thu tu sau

void LRN(TREE T)

{

if(T!=NULL)

{

LRN(T->Left);

LRN(T->Right);

printf("%d ", T->key);

}

}

// ham tim nut

NODE* timnut(TREE T, int x)

{

if (T!=NULL)

{

if (T->key == x) { NODE *P = T; return P;}

if (T->key > x) return timnut(T->Left, x);

if (T->key < x) return timnut(T->Right, x);

}

return NULL;

}

// dem nut

int demnut(TREE T){

if(T==NULL)

return 0;

else

return (demnut(T->Right) + demnut(T->Left) + 1); }

// ham xoa nut

int xoanut(TREE &T, int x) // xoa nut co key x

{

if (T==NULL) return 0;

if (T->key > x) return xoanut(T->Left, x);

if (T->key < x) return xoanut(T->Right, x);

else // T->key == x

{

TREE p = T;

if (T->Left == NULL) T = T->Right; // Node chi co cay con phai else if (T->Right == NULL) T = T->Left; // Node chi co cay con trai else // Node co ca 2 con

{

NODE* q = T->Right;

timnut(T, x);

}

delete p;

}

}

//xac dinh chieu cao cua cay

int ccaocay(TREE T){

if(T==NULL)return -1;

if((T->Right==NULL) && (T->Left==NULL))

return 0;

if((T->Right!=NULL) && (T->Left!=NULL))

return nmax((1 + ccaocay(T->Right)),(1 + ccaocay(T->Left)));

if(T->Left==NULL&&T->Right!=NULL)

return (1 + ccaocay(T->Right)); else

if(T->Left!=NULL&&T->Right==NULL) return (1 + ccaocay(T->Left)); }

// ham xac dinh muc cua 1 nut

void muc(TREE T, int x)

{

if (T!=NULL)

{

d++;

if (T->key > x) muc(T->Left, x);

if (T->key < x) muc(T->Right, x);

}

}

// ham main

int main()

{

TREE T;

T=NULL; //Tao cay rong

nhap(T); //Nhap cay

//duyet cay

printf("\n Duyet cay theo ttt: ");

NLR(T);

printf("\n Duyet cay theo ttg: ");

LNR(T);

printf("\n Duyet cay theo tts: ");

LRN(T);

printf("\n so nut cua cay la:%d", demnut(T)); printf("\n Chieu cao cay la: %d",ccaocay(T)); int a;

printf("\n Nhap nut: "); scanf("%d",&a);

d=0; muc(T,a); printf(" Muc cua nut la: %d",d); NODE *P;

int x;

printf("\n Nhap vao nut can tim: ");

scanf("%d", &x);

P = timnut(T, x);

if (P != NULL) printf("\n Tim thay nut %d: ", P->key); else printf("\n nut %d khong co trong cay: ", x);

if (xoanut(T, x)) printf("\n Xoa thanh cong "); else printf("\n Khong tim thay nut %d can xoa: ", x); printf("\n Duyet cay theo ttt: ");

NLR(T);

printf("\n Duyet cay theo ttg: ");

LNR(T);

printf("\n Duyet cay theo tts: ");

LRN(T);

printf("\n Chieu cao cay la: %d",ccaocay(T)); printf("\n so nut cua cay la:%d", demnut(T)); return 0;

}

III.2 Kết quả

Chương trình cho ta được kết quả sau:

- Xuất ra được các thứ tự duyệt : NLR, LNR, LRN.

- Đếm được số nút của cây.

- Xác định được chiều cao của cây.

- Xác định được mức của nút.

- Tìm nút của cây.

- Xóa thành công nút cần xóa trên cây.

- Thêm được các nút chưa có trên cây.

Ví dụ:

Nhập một dãy số sau: 12 22 43 55

Chương trình xuất ra:

Duyệt theo NLR: 12 22 43 55

Duyệt theo LNR: 12 22 43 55

Duyệt theo LRN: 55 43 22 12

Số nút của cây là : 4

Chiều cao của cây là: 3

Nhập nút: 12

Mức của nút là : 1

Nhập nút : 12

Tìm thấy nút 12

Xóa thành công

Duyệt theo NLR : 22 43 55

Duyệt theo LNR: 22 43 55

Duyệt theo LRN: 55 43 22

Chiều cao của cây : 2

Số nút của cây : 3

TÀI LIỆU THAM KHẢO

Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, nhà xuất bản Đại học Quốc gia Hà Nội, 2006

Lê Minh Trung, Bài tập cấu trúc dữ liệu và giải thuật, Nhà xuất bản thống kê, 2005

Donald Knuth The Art of Compter Programming, Volume 3: Sorting and Searching, Third Edition Addison-Wesley, 1997 ISBN 0-201-89685-0 Section 6.2.2: Binary Tree Searching, pp 426–458

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein Introduction to Algorithms, Second Edition MIT Press and McGraw-Hill,

2001 ISBN 0-262-03293-7 Chapter 12: Binary search trees, pp 253–272 Section 15.5: Optimal binary search trees, pp 356–363