Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 04: Cây nhị phân tìm kiếm

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 04: Cây nhị phân tìm kiếm

1. I MỤC TIÊU Hoàn t t bài th c hành này, sinh viên có th : - Hi u ưc các thành ph n c a cây nh phân tìm ki m. - Thành th o các thao tác trên cây nh phân tìm ki m: t o cây, thêm ph n t , xóa ph n t , duy t cây nh phân tìm ki m. - Áp d ng c u trúc d li u cây nh phân tìm ki m vào vi c gi i quy t m t s bài toán ơ n gi n. Th i gian th c hành: t 120 phút n 400 phút TÓM T ẮT Cây nh phân tìm ki m là cây có t i a 2 nhánh (cây con), nhánh trái và nhánh ph i. Cây nh phân tìm ki m có các tính cht sau: - Khóa c a tt c các nút thu c cây con trái nh h ơn khóa nút gc. - Khóa c a nút g c nh h ơn khóa c a t t c các nút thu c cây con ph i. - Cây con trái và cây con ph i c a nút gc c ng là cây nh phân tìm ki m Mt s khái ni m: - Nút lá có cao b ng 1 1 1 Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
2. Ví d cây nh phân tìm ki m: Trong m i nút c a cây nh phân tìm ki m, thông tin liên k t là vô cùng quan tr ng. Ch c n m t x lý không c n th n có th làm m t ph n liên k t này thì cây s b ‘ gãy ’ cây con liên quan ng v i liên k t ó (không th truy xu t ti p t t c các nút c a nhánh con b m t). Các thao tác c ơ b n trên cây nh phân tìm ki m: - Thêm 1 nút: d a vào tính ch t c a cây nh phân tìm ki m tìm v trí thêm nút m i. o To cây: t cây r ng, l n l ưt thêm các nút vào cây b ng ph ươ ng th c thêm nút vào cây nh phân tìm ki m - Xóa 1 nút: là nút lá, là nút có 1 nhánh con, là nút có 2 nhánh con. - Duy t cây nh phân tìm ki m: có th i ưc h t các ph n t trên cây nh phân tìm ki m: duy t tr ưc (NLR), duy t gi a (LNR), duy t sau (LRN). Do tính ch t ca cây nh phân tìm ki m, phép duy t gi a cho phép duy t các khóa c a cây theo th t t ng d n 2 2 Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
3. NỘI DUNG TH ỰC HÀNH C b n Sinh viên c k phát bi u bài t p và th c hi n theo h ưng d n: T ch c mt cây nh phân tìm ki m trong ó m i ph n t ch a thông tin d li u là s nguyên. Ng ưi dùng s nh p các giá tr nguyên t bàn phím. V i m i giá tr nguyên ưc nh p vào, giá tr ó ưc thêm vào cây nh phân tìm ki m mà v n m b o cây sau khi thêm v n là cây nh phân tìm ki m. N u ng ưi dùng nh p vào giá tr -1, quá trình nh p d li u s k t thúc. Cây ban u là cây rng (ch ưa có nút nào) Sau ó, in ra các ph n t ang có trên cây b ng ph ươ ng pháp duy t tr ưc. Cho ng ưi dùng nh p vào 1 giá tr nguyên t bàn phím, cho bi t giá tr này có trong cây hay không. Nu có, cho bi t nút ó có cao bao nhiêu. Sau ó, xóa nút kh i cây, xu t cây sau khi xóa b ng ph ươ ng pháp duy t tr ưc Phân tích - Cây nh phân tìm ki m có m i nút ch a d li u nguyên. Thông tin c a m i nút ưc khai báo theo ngôn ng C/C++ nh ư sau: struct NODE{ int Key; NODE *pLeft; NODE *pRight; }; - Thao tác c n th c hi n: o Khai báo, kh i t o cây o (l p) thêm nút có khóa nguyên vào cây nh phân tìm ki m (Insert ), o in các nút c a cây nh phân tìm ki m ( NLR ), o tìm 1 giá tr , n u có:
   tính cao c a nút ó ( Height )
   xóa nút kh i cây ( RemoveNode )
   in các nút c a cây sau khi xóa ( NLR ) Ch ươ ng trình m ẫu #include "stdio.h" struct NODE{ int Key; NODE *pLeft; NODE *pRight; }; void Init(NODE *&TREE) { TREE = NULL; } 3 3 void Insert (NODE *&pRoot, int x) { if (pRoot == NULL) Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
4. { NODE *q; q = new NODE; q->Key = x; q->pLeft = q->pRight = NULL; pRoot = q; } else { if (x Key) Insert (pRoot->pLeft, x); else if (x > pRoot->Key) Insert (pRoot->pRight, x); } } void CreateTree(NODE *&pRoot) { int Data; do { printf( "Nhap vao du lieu, -1 de ket thuc: " ); scanf( "%d" , &Data); if (Data == -1) break ; Insert(pRoot, Data); } while (1); } void NLR(NODE* pTree) { if (pTree != NULL) { printf( "%4d" , pTree->Key); NLR(pTree->pLeft); NLR(pTree->pRight); } } NODE* Search(NODE* pRoot, int x) { if (pRoot == NULL) return NULL; if (x Key) Search(pRoot->pLeft, x); else if (x > pRoot->Key) Search(pRoot->pRight, x); else { //Ghi chú: Trong tr ường h ợp nào dòng bên d ưới được th ực hi ện? return pRoot; } } int Height(NODE* pNode) { if (pNode == NULL) return 0; int HL, HR; HL = Height(pNode->pLeft); HR = Height(pNode->pRight); if (HL > HR) 4 return (1 + HL); return (1 + HR); Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
5. } void SearchStandFor(NODE* &Tree, NODE* &q) { if (Tree->pRight) SearchStandFor(Tree->pRight,q); else { q->Key = Tree->Key; q = Tree; Tree = Tree->pLeft; } } void RemoveNode(NODE* &Tree, int x) { NODE* p; if (Tree == NULL) printf( "%d khong co trong cay" , x); else { if (x Key) RemoveNode(Tree->pLeft,x); else if (x > Tree->Key) RemoveNode(Tree->pRight,x); else { //Ghi chú: M ục đích phép gán này là gì? p = Tree; if (p->pRight == NULL) Tree = p->pLeft; else if (p->pLeft == NULL) Tree = p->pRight; else { //Ghi chú: Hàm bên d ưới dùng để làm gì? SearchStandFor(Tree->pLeft,p); } delete p; } } } void main() { NODE* pTree, *p; int x; Init(pTree); CreateTree(pTree); NLR(pTree); printf( "Nhap vao 1 gia tri de tim: " ); scanf( "%d" , &x); p = Search(pTree, x); if (p != NULL) { printf ( "%d co xuat hien trong cay.\n" , x); printf( "Chieu cao cua nut %d la %d\n" , x, Height(p)); RemoveNode(pTree, x); NLR(pTree); 5 } else Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
6. printf( "%d khong co trong cay.\n" , x); } Yêu c ầu 1. Biên d ch on ch ươ ng trình nêu trên. 2. Cho bi t k t qu in ra màn hình khi ng ưi dùng nh p vào các d li u sau: -1 -1 5 -1 -1 7 10 -23 -25 -4 1 -1 -23 -23 7 10 -25 -4 1 -1 -23 7 10 -23 -4 1 -25 -1 -23 1 2 3 4 -1 5 3 3. Nêu nh n xét ng n g n m i liên h gi a th t nh p d li u vào (v i cùng t p d li u – d li u th 3, 4, và 5) v i th t in d li u ra màn hình. 4. V hình cây nh phân tìm ki m theo d li u ưc nh p câu 2. 5. N u b Init(pTree) trong hàm main k t qu có thay i hay không? Gi i thích lý do? 6. N u trong hàm CreateTree vòng l p do while ưc thay i nh ư d ưi ây thì k t qu k t xu t ra màn hình s nh ư th nào i v i d li u câu 2? Gi i thích lý do? do { printf( "Nhap vao du lieu, -1 de ket thuc: " ); scanf( "%d" , &Data); Insert(pRoot, Data); if (Data == -1) break ; }while (1); 7. Trong hàm NLR n u ta i tr t t nh ư bên d ưi thì k t qu th nào? void NLR(NODE* pTree) { if (pTree != NULL) { NLR(pTree->pLeft); 6 printf( "%4d" , pTree->Key); NLR(pTree->pRight); Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
7. } } 8. Hãy ghi chú các thông tin b ng cách tr l i các câu h i ng v i các dòng l nh có yêu c u ghi chú (//Ghi chú ) trong các hàm Search , RemoveNode . 9. N u trong hàm RemoveNode thay i nh ư sau, k t qu có thay i không? N u có, ch ra cách k t qu không thay i. N u không, gi i thích lý do else { //Ghi chú: Hàm bên d ưới dùng để làm gì? SearchStandFor(Tree->pRight ,p); } 10. Trong hàm RemoveNode nu không có dòng delete p; thì k t qu có gì khác? Dòng ó dùng làm gì. Áp d ng – Nâng cao 1. B sung ch ươ ng trình m u cho phép tính tng giá tr các nút trên cây nh phân g m các giá tr nguyên. Gi ý: tham kh o hàm NLR vi t hàm SumTree . 2. B sung ch ươ ng trình m u cho phép tìm giá tr nguyên l n nh t và nh nh t trong s các ph n t nguyên trên cây nh phân tìm ki m g m các giá tr nguyên. Gi ý: d a vào tính ch t 1, 2 c a cây nh phân tìm ki m. 3. B sung ch ươ ng trình m u cho phép tính s l ưng các nút c a cây nh phân g m các giá tr nguyên. Gi ý: tham kh o hàm NLR vi t hàm CountNode . 4. B sung ch ươ ng trình m u cho bi t s l ưng các nút lá trên cây nh phân. Gi ý: tham kh o thao tác duy t cây nh phân NLR . 5. S d ng cây nh phân tìm ki m gi i bài toán: a. m có bao nhiêu giá tr phân bi t trong dãy s cho tr ưc b. V i m i giá tr phân bi t, cho bi t s l ưng ph n t BÀI T ẬP THÊM 1. S d ng cây nh phân tìm ki m đ gi i bài toán đm (th ng kê) s l ưng ký t có trong văn bn (Không d u). a. Xây d ng cây cho bi t m i ký t có trong v n b n xu t hi n m y l n b. Nh p vào 1 ký t . Ki m tra ký t ó xu t hi n bao nhiêu l n trong v n b n 2. Bài toán t ươ ng t nh ư trên nh ưng th ng kê s l ưng ti ng có trong văn b n (không d u) Ví d : Vn b n có n i dung nh ư sau: “hoc sinh di hoc mon sinh hoc” Kt qu cho th y nh ư sau: di: 1 hoc: 3 7 mon: 1 Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010
8. sinh: 2 8 8 Trang Trang Tài li ệu h ướng d ẫn th ực hành môn Cấu trúc d ữ li ệu và gi ải thu ật HCMUS 2010