Bài 2.3:Cây nhị phân tìm kiếm

Chia sẻ: Nguyen Ha | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

99
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cấu trúc dữ liệu Cây nhị phân tìm kiếm là cây nhị phân trong đó tại mỗi nút, khoá của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khoá của tất các nút thuộc cây con phải. Cấu trúc dữ liệu của cây nhị phân tìm kiếm là cấu trúc dữ liệu biểu diễn cây nhị phân nói chung. struct TNode { int Info; struct TNode *pL,*pR; };

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài 2.3:Cây nhị phân tìm kiếm

2.3. Cây nhị phân tìm kiếm (Binary Searching Tree) 2.3.1. Khái niệm – Cấu trúc dữ liệu  Cây nhị phân tìm kiếm là cây nhị phân trong đó tại mỗi nút, khoá của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khoá của tất các nút thuộc cây con phải.  Cấu trúc dữ liệu của cây nhị phân tìm kiếm là cấu trúc dữ liệu biểu diễn cây nhị phân nói chung. struct TNode { int Info; struct TNode *pL,*pR; }; 1
2.3. Cây nhị phân tìm kiếm (Binary Searching Tree) 2.3.2. Các thao tác trên cây nhị phân tìm kiếm 2.3.2.a. Thêm vào một phần tử X vào cây 2.3.2.b. Tạo một cây NPTK 2.3.2.c. Duyệt cây 2.3.2.d. Tìm một phần tử X trong cây 2.3.2.e. Huỷ một phần tử có khoá X 2
2.3.2.a. Thêm vào một phần tử X vào cây Việc thêm một phần tử x vào cây phải đảm bảo điều kiện ràng buộc của CNPTK: - * Mọi số thuộc cây con trái của nút đó đều nhỏ hơn số ứng với nút đó - * Mọi số thuộc cây con phải của nút đó đều lớn hơn số ứng với nút đó Hàm insert trả về giá trị -1: khi không đủ bộ nhớ. 0: khi gặp nút trùng. 1: khi thực hiện thành công. 3
int InsertTree(TREE &T,int k) { if (T!=NULL) { //neu can ca so trung nhau thi bo dong ngay duoi if (T->Info==k) return 0; if (T->Info>k) return InsertTree(T->pL,k); else return InsertTree(T->pR,k); } else { T=(TREE)malloc(sizeof(TNode)); if (T==NULL) return -1; T->Info=k; T->pL=T->pR=NULL; return 1; } } 4
2.3.2.b. Tạo một cây NPTK: Ta có thể tạo CNPTK bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng void CreateTree(TREE &T) { T=NULL; int k; coutn; for (int i=1;i>k; InsertTree(T,k); } } 5
Ví dụ tạo cây nhị phân tìm kiếm:  Cho mảng: 60 25 65 19 40 10 15 30 44 50 X=60 ->Root 25L 65>60->R 19L 40>25>19->R 101015>…>25->RL 44>30->R 50>44->R 6
Ví dụ chèn nút:  Chèn nút 34 62 34L 34>21->R 66 21 34L->NULL-> chèn 17 50 75  Chèn nút 68 68>62->R 34 58 68>66->R 70 68L 68L->NULL->chèn 68 7
2.3.2.c. Duyệt cây 2.3.2.d. Tìm một phần tử X trong cây int SearchTree(TREE T,int k) { if (T==NULL) return 0; else if (T->Info==k) return 1; if (k>T->Info) return SearchTree(T->pR,k); else return SearchTree(T->pL,k); } 8
2.3.2.c. Duyệt cây 2.3.2.d. Tìm một phần tử X trong cây TNode* SearchTree1(TREE T,int k) { if (T==NULL) return NULL; else if (T->Info==k) return T; if (k>T->Info) return SearchTree1(T->pR,k); else return SearchTree1(T->pL,k); } 9
2.3.2.e. Huỷ một phần tử có khoá X int DelTree(TREE &T,int k) { if (T==NULL) return 0; if (T->Info>k) return DelTree(T->pL,k); if (T->InfopR,k); else { TNode *p=T; if (T->pR==NULL) T=T->pL; else if (T->pL==NULL) T=T->pR; else { TNode *q=T->pR; SearchStandfor(p,q); } delete(p); } } 10
2.3.2.e. Huỷ một phần tử có khoá X void SearchStandfor(TREE &p,TREE &q) { if (q->pL) SearchStandfor(p,q->pL); else { p->Info=q->Info; p=q; q=q->pR; } } 11
2.3.2.f. Huỷ toàn bộ CNPTK Void removeTree( TREE &T) { if(T) { removeTree(T->pL); removeTree(T->pR); delete(T); } } 12
2.3.2.a. Tìm kiếm trên cây nhị phân tìm kiếm BST  Tìm kiếm trong cây có tồn tại nút có khóa (Key) là SearchData hay không.  Dùng thuật toán tìm kiếm nhị phân vì do đặc điểm của cây nhị phân tìm kiếm thì tại 1 nút nểu Key của nút này khác với SearchData:  Nếu SearchData > Key của nút tìm ở cây con bên phải  Nếu SearchData < Key của nút tìm ở cây con bên trái B1: CurrNode = BSTree B2: IF (CurrNode == NULL or CurrNode->Key == SearchData) Thực hiện BKT B3: IF (CurrNode ->Key > SearchData) // tìm ở cây con bên trái CurrNode = CurrNode->BSTree->BSTLeft B4: ELSE // tìm ở cây con bên phải CurrNode = CurrNode->BSTree->BSTRight B5: Lặp lại B2 BKT: Kết thúc 13
- Minh họa thuật toán:  Giả sử chúng ta cần tìm kiếm nút có thành phần dữ liệu là 30 trên cây nhị phân tìm kiếm sau: SearchData = 30 14
CurNode->Key > SearchData // Tìm kiếm trên cây con trái => CurNode = CurNode->BST_Left 15
CurNode->Key > SearchData // Tìm kiếm trên cây con trái => CurNode = CurNode->BST_Left CurNode->Key = SearchData Thuật toán kết thúc (Tìm thấy) 16
2.3.2.a. Tìm kiếm trên cây nhị phân tìm kiếm BST (tt) Cài đặt thuật toán BSTType BSTSearching (BSTType BSTree, T SearchData) { BSTType CurrNode = BSTree; while (CurrNode !=NULL & CurrNode->Key != SeachData) { if (CurrNode ->Key > SearchData) CurrNode = CurrNode ->BSTLeft; else CurrNode = CurrNode ->BSTRight; } return (CurrNode); } 17
2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm  Giả sử thêm vào 1 nút có thành phần dữ liệu là NewData vào cây nhị phân tìm kiếm sao cho sau khi thêm, cây vẫn là cây nhị phân tìm kiếm.  Bao gồm các thao tác tìm kiếm vị trí thêm và thêm nút vào cây.  Thao tác chỉ thêm được nếu không có hiện tượng trùng khóa, do đó nếu NewData trùng với Key của 1 trong các nút trong cây thì không thực hiện thêm. 18
2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm (tt) B1: NewNode = BinTreeCreateNode(NewData) B2: IF(NewNode == NULL) Thực hiện BKT B3: IF (BSTree == NULL) B3.1: BSTree = NewNode B3.2: Thực hiện BKT B4: CurrNode = BSTree B5: IF (CurrNode == NULL) Thực hiện BKT B6: IF (CurrNode->Key > NewData) B6.1: AddLeft = True B6.2: If (CurrNode->BSTLeft != NULL) CurrNode = CurrNode->BSTLeft B7: IF (CurrNode->Key < NewData) B6.1: AddLeft = False B6.2: If (CurrNode->BSTRight != NULL) CurrNode = CurrNode->BSTRight B8: Lặp lại B5 B9: IF (AddLeft == True) CurrNode = CurrNode->BSTLeft B10: ELSE CurrNode = CurrNode->BSTRight BKT: Kết thúc 19
- Minh họa thuật toán:  Giả sử chúng ta cần thêm vào trong cây nhị phân tìm kiếm 1 nút có thành phần dữ liệu là 55: NewData = 55 20