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 - Bài 4: Cây nhị phân tìm kiếm

CÂY NH PHÂN TÌM KI M<br /> M C TIÊU<br /> Hoàn t t bài th c hành này, sinh viên có th :<br /> -<br /> <br /> Hi u ư c các thành ph n c a cây nh phân tìm ki m.<br /> <br /> -<br /> <br /> 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 ,<br /> duy t cây nh phân tìm ki m.<br /> <br /> -<br /> <br /> Á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<br /> gi n.<br /> <br /> Th i gian th c hành: t 120 phút<br /> <br /> n 400 phút<br /> <br /> TÓM T T<br /> 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<br /> tìm ki m có các tính ch t sau:<br /> -<br /> <br /> Khóa c a t t c các nút thu c cây con trái nh hơn khóa nút g c.<br /> <br /> -<br /> <br /> 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.<br /> <br /> -<br /> <br /> Cây con trái và cây con ph i c a nút g c cũng là cây nh phân tìm ki m<br /> <br /> M t s khái ni m:<br /> <br /> Nút lá có<br /> <br /> cao b ng 1<br /> <br /> Trang<br /> <br /> 1<br /> <br /> -<br /> <br /> Tài li u hư ng d n th c hành môn C u trúc d<br /> HCMUS 2010<br /> <br /> li u và gi i thu t<br /> <br /> Ví d cây nh phân tìm ki m:<br /> <br /> 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<br /> 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<br /> 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).<br /> Các thao tác cơ b n trên cây nh phân tìm ki m:<br /> -<br /> <br /> Thêm 1 nút: d a vào tính ch t c a cây nh phân tìm ki m<br /> <br /> tìm v trí thêm nút m i.<br /> <br /> o T o 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<br /> cây nh phân tìm ki m<br /> 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.<br /> <br /> -<br /> <br /> 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:<br /> duy t trư c (NLR), duy t gi a (LNR), duy t sau (LRN). Do tính ch t c a cây nh phân tìm<br /> 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<br /> <br /> Trang<br /> <br /> 2<br /> <br /> -<br /> <br /> Tài li u hư ng d n th c hành môn C u trúc d<br /> HCMUS 2010<br /> <br /> li u và gi i thu t<br /> <br /> N I DUNG TH C HÀNH<br /> Cơ b n<br /> Sinh viên<br /> <br /> c k phát bi u bài t p và th c hi n theo hư ng d n:<br /> <br /> T ch c m t 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.<br /> 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<br /> ó ư 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<br /> 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<br /> r ng (chưa có nút nào)<br /> Sau ó, in ra các ph n t<br /> <br /> ang có trên cây b ng phương pháp duy t trư c.<br /> <br /> 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.<br /> N u có, cho bi t nút ó có<br /> cao bao nhiêu. Sau ó, xóa nút kh i cây, xu t cây sau khi xóa b ng<br /> phương pháp duy t trư c<br /> Phân tích<br /> -<br /> <br /> 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<br /> báo theo ngôn ng C/C++ như sau:<br /> <br /> struct NODE{<br /> int Key;<br /> NODE *pLeft;<br /> NODE *pRight;<br /> };<br /> <br /> -<br /> <br /> Thao tác c n th c hi n:<br /> o Khai báo, kh i t o cây<br /> o (l p) thêm nút có khóa nguyên vào cây nh phân tìm ki m (Insert),<br /> o in các nút c a cây nh phân tìm ki m (NLR),<br /> o tìm 1 giá tr , n u có:<br /> tính<br /> <br /> cao c a nút ó (Height)<br /> <br /> xóa nút kh i cây (RemoveNode)<br /> in các nút c a cây sau khi xóa (NLR)<br /> Chương trình m u<br /> #include "stdio.h"<br /> struct NODE{<br /> int Key;<br /> NODE *pLeft;<br /> NODE *pRight;<br /> };<br /> <br /> Insert (NODE *&pRoot, int x)<br /> <br /> if (pRoot == NULL)<br /> Tài li u hư ng d n th c hành môn C u trúc d<br /> HCMUS 2010<br /> <br /> Trang<br /> <br /> void<br /> {<br /> <br /> 3<br /> <br /> void Init(NODE *&TREE)<br /> {<br /> TREE = NULL;<br /> }<br /> <br /> li u và gi i thu t<br /> <br /> {<br /> NODE *q;<br /> q = new NODE;<br /> q->Key = x;<br /> q->pLeft = q->pRight = NULL;<br /> pRoot = q;<br /> }<br /> else<br /> {<br /> if (x < pRoot->Key)<br /> Insert (pRoot->pLeft, x);<br /> else if (x > pRoot->Key)<br /> Insert (pRoot->pRight, x);<br /> }<br /> }<br /> void CreateTree(NODE *&pRoot)<br /> {<br /> int Data;<br /> do{<br /> printf("Nhap vao du lieu, -1 de ket thuc: ");<br /> scanf("%d", &Data);<br /> if (Data == -1)<br /> break;<br /> Insert(pRoot, Data);<br /> } while(1);<br /> }<br /> void NLR(NODE* pTree)<br /> {<br /> if(pTree != NULL)<br /> {<br /> printf("%4d", pTree->Key);<br /> NLR(pTree->pLeft);<br /> NLR(pTree->pRight);<br /> }<br /> }<br /> NODE* Search(NODE* pRoot, int x)<br /> {<br /> if(pRoot == NULL)<br /> return NULL;<br /> if(x < pRoot->Key)<br /> Search(pRoot->pLeft, x);<br /> else<br /> if(x > pRoot->Key)<br /> Search(pRoot->pRight, x);<br /> else<br /> {<br /> //Ghi chú: Trong trư ng h p nào dòng bên dư i<br /> return pRoot;<br /> }<br /> }<br /> <br /> Tài li u hư ng d n th c hành môn C u trúc d<br /> HCMUS 2010<br /> <br /> Trang<br /> <br /> 4<br /> <br /> int Height(NODE* pNode)<br /> {<br /> if(pNode == NULL)<br /> return 0;<br /> int HL, HR;<br /> HL = Height(pNode->pLeft);<br /> HR = Height(pNode->pRight);<br /> if(HL > HR)<br /> return (1 + HL);<br /> return (1 + HR);<br /> <br /> ư c th c hi n?<br /> <br /> li u và gi i thu t<br /> <br /> }<br /> void SearchStandFor(NODE* &Tree, NODE* &q)<br /> {<br /> if (Tree->pRight)<br /> SearchStandFor(Tree->pRight,q);<br /> else<br /> {<br /> q->Key = Tree->Key;<br /> q = Tree;<br /> Tree = Tree->pLeft;<br /> }<br /> }<br /> void RemoveNode(NODE* &Tree, int x)<br /> {<br /> NODE* p;<br /> if(Tree == NULL)<br /> printf("%d khong co trong cay", x);<br /> else<br /> {<br /> if (x < Tree->Key)<br /> RemoveNode(Tree->pLeft,x);<br /> else<br /> if (x > Tree->Key)<br /> RemoveNode(Tree->pRight,x);<br /> else<br /> {<br /> //Ghi chú: M c ích phép gán này là gì?<br /> p = Tree;<br /> if(p->pRight == NULL)<br /> Tree = p->pLeft;<br /> else<br /> if (p->pLeft == NULL)<br /> Tree = p->pRight;<br /> else {<br /> //Ghi chú: Hàm bên dư i dùng<br /> SearchStandFor(Tree->pLeft,p);<br /> }<br /> delete p;<br /> }<br /> }<br /> }<br /> <br /> làm gì?<br /> <br /> void main()<br /> {<br /> NODE* pTree, *p;<br /> int x;<br /> <br /> Tài li u hư ng d n th c hành môn C u trúc d<br /> HCMUS 2010<br /> <br /> li u và gi i thu t<br /> <br /> Trang<br /> <br /> printf("Nhap vao 1 gia tri de tim: ");<br /> scanf("%d", &x);<br /> p = Search(pTree, x);<br /> if(p != NULL)<br /> {<br /> printf ("%d co xuat hien trong cay.\n", x);<br /> printf("Chieu cao cua nut %d la %d\n", x, Height(p));<br /> RemoveNode(pTree, x);<br /> NLR(pTree);<br /> }<br /> else<br /> <br /> 5<br /> <br /> Init(pTree);<br /> CreateTree(pTree);<br /> NLR(pTree);<br /> <br />