Đề tài Xây dựng cây nhị phân tìm kiếm

VIỆN ĐẠI HỌC MỞ HÀ NỘI KHOA CÔNG NGHỆ TIN HỌC ---- c & d ---- 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 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 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 Internet thông qua các công cụ tìm kiếm. Các công cụ tìm kiếm đó được xây dựng từ các phần mềm tìm kiếm khác nhau. Một trong những chương trình tìm kiếm mà chúng tôi đề cập đến ở đây chính là Cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân được xây dựng bằng ngôn ngữ C++. Đây 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. Ngoài ra cấu trúc Cây nhị phân tìm kiếm còn được ứng dụng trong việc tra từ điển. Dưới đây là một vài giới thiệu về Cây và Cây nhị phân tìm kiếm. A. Cây Ví dụ về một cây nhị phân Trong khoa học máy tính, cây là một cấu trúc dữ liệu được sử dụng rộng rãi gồm một tập hợp các nút (tiếng Anh: node) được liên kết với nhau theo quan hệ cha-con. Cây trong cấu trúc dữ liệu đầu tiên là mô phỏng (hay nói cách khác là sự sao chép) của cây (có gốc) trong lý thuyết đồ thị. Hầu như mọi khái niệm trong cây của lý thuyết đồ thị đều được thể hiện trong cấu trúc dữ liệu. Tuy nhiên cây trong cấu trúc dữ liệu đã tìm được ứng dụng phong phú và hiệu quả trong nhiều giải thuật. Khi phân tích các giải thuật trên cấu trúc dữ liệu cây, người ta vẫn thường vẽ ra các cây tương ứng trong lý thuyết đồ thị. Các nút Một nút có thể chứa một giá trị, một điều kiện, một cấu trúc dữ liệu riêng biệt hoặc chính một cây. Mỗi nút trong một cây có thể không có hoặc có một số nút con, các nút con có mức cao hơn nó (theo quy ước khác với cây tự nhiên, cây trong cấu trúc dữ liệu phát triển từ trên xuống). Một nút có con được gọi là nút cha của các nút con. Một nút có nhiều nhất một nút cha. Nút gốc Trong mỗi cây có một nút đặc biệt được gọi là nút gốc (hay nói đơn giản là gốc). Nút gốc là nút duy nhất không có nút cha. Nút gốc là nơi khởi đầu của nhiều giải thuật trên cây. Tất cả các nút khác được nối về nút gốc bằng một đường đi qua các cạnh hay các liên kết. 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. 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ả hai. Cây cũng có thể biểu diễn bằng các mảng cùng với quan hệ giữa các vị trí trong mảng. Biểu diễn bằng các nút với các con trỏ Mỗi nút là một dữ liệu kiểu bản ghi với ba trường: Một trường thường gọi là INFOR, chứa thông tin lưu trữ tại nút đó. Thông tin này có thể chỉ là một số, một ký tự, cũng có thể là một tập hợp dữ liệu rất phức tạp. Hai trường LLINK và RLINK chứa các liên kết trái và phải. Nếu cây là cây nhị phân, LLINK trỏ tới con trái của nút, RLINK trỏ tới con phải của nút. Nếu cây là cây tổng quát, LLINK trỏ tới con cực trái và RLINK trỏ tới em kế cận phải của nút đó. Do đó danh sách các nút biểu diễn một cây tổng quát, khi được xem là biểu diễn của cây nhị phân sẽ cho một cây nhị phân. Cây nhị phân này được gọi là cây nhị phân tương đương với cây tổng quát ban đầu. Biểu diễn cây nhị phân bằng mảng 1- Cây nhị phân đầy đủ là cây nhị phân, trong đó mỗi nút trong chỉ có hai con. Cây nhị phân hoàn chỉnh là cây nhị phân đầy đủ, trong đó tất cả các lá đều ở mức cao nhất. Một cây nhị phân hoàn chỉnh chiều cao h chỉ có 2h + 1 − 1 nút. 2- Do đó người ta có thể dùng một mảng gồm 2h + 1 − 1 phần tử để biểu diễn cây hoàn chỉnh, bằng cách lần lượt lưu trữ thông tin của mỗi nút vào mảng theo thứ tự từ trên xuống dưới, từ trái sang phải. Khi đó con trái của nút thứ i là phần tử thứ 2*i, con phải là phần tử thứ 2*i+1. Cha của phần tử thứ i là phần tử thứ int(i/2). 3- Nếu cây là không hoàn chỉnh, ta gán giá trị Null cho các vị trí còn thiếu so với cây nhị phân hoàn chỉnh. 4- Một cách khác, dùng một mảng hai chiều trong dòng thứ nhất ghi các thông tin của nút, dòng thứ hai ghi chỉ số của nút cha của nút đó với dấu + nếu nút hiện tại là con trái, với dấu - nếu nút hiện tại là con phải của nút cha. 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. 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 k1,k2,...kn 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ị như trong lý thuyết tập hợp. Cây loại này sử dụng các bất đẳng thức 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 khóa của nút cha. Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tiìm kiếm trở nên phức tạp hơn. Trong khoa học máy tính, duyệt cây là việc lần lượt viếng thăm các đỉnh của cây theo một thứ tự nào đó. Các cây nói trong bài này là cây có gốc. Dưới đây trình bày một số thuật toán duyệt cây thông dụng. Duyệt cây nhị phân Khi xét một cây nhị phân, mỗi đỉnh cùng với các đỉnh đứng sau nó là gốc của một cây con. Ta xét một đỉnh A là đỉnh trong của cây nhị phân. Theo thứ tự người ta xem xét thứ tự thăm đỉnh A so với việc thăm hai con của nó là thăm A trước rồi 2 con sau, thăm A xen giữa việc thăm hai con, thăm A sau thi thăm hai con: A, con trái, con phải Con trái, A, con phải Con trái, con phải, A Tất nhiên nếu không có con nào thì việc thăm con ấy không diễn ra. Còn nếu con L hoặc con R của A lại là gốc của một cây con, thì việc thăm thay bằng việc duyệt cây con có gốc tại đó. Từ đó có các phương pháp duyệt tiền thứ tự, trung thứ tự, hậu thứ tự đối với cây nhị phân có gốc tại đỉnh A như sau Duyệt tiền thứ tự cây con gốc A Nếu Cây là rỗng Return Thăm A Duyệt tiền thứ tự cây con gốc L Duyệt tiền thứ tự cây con gốc R Duyệt trung thứ tự cây con gốc A Nếu Cây là rỗng Return Duyệt trung thứ tự cây con gốc L Thăm A Duyệt trung thứ tự cây con gốc R Duyệt hậu thứ tự cây con gốc A Nếu Cây là rỗng Return Duyệt hậu thứ tự cây con gốc L Duyệt hậu thứ tự cây con gốc R Thăm A Ví dụ Giả sử có cây nhị phân sau A / \ B C / \ / \ D E F G Duyệt tiền thứ tự với cây này diễn ra tuần tự như sau Thăm A, Duyệt cây gốc B, Duyệt cây gốc C Thăm A, Thăm B, Thăm D, Thăm E, Thăm C, Thăm F, Thăm G Duyệt trung thứ tự với cây này diễn ra tuần tự như sau Duyệt cây gốc B, Thăm A, Duyệt cây gốc C Thăm D, Thăm B, Thăm E, Thăm A, Thăm F, Thăm C, Thăm G Duyệt hậu thứ tự với cây này diễn ra tuần tự như sau Duyệt cây gốc B, Duyệt cây gốc C, Thăm A Thăm D, Thăm E, Thăm B, Thăm F, Thăm G, Thăm C, Thăm A Duyệt cây tổng quát Nếu tại gốc A của cây có các con từ trái sang phải là A1,A2,...,An thì quá trình duyệt tiền thứ tự, trung và hậu thứ tự như sau Duyệt tiền thứ tự Thăm A Lần lượt duyệt các cây con gốc A1,A2,...,An Duyệt trung thứ tự Duyệt cây con gốc A1 Thăm A Lần lượt duyệt các cây con gốc A2,...,An Duyệt hậu thứ tự Lần lượt duyệt các cây con gốc A1,A2,...,An Thăm A Tuy nhiên người ta ít xem xét việc duyệt trung thứ tự của cây tổng quát Duyệt theo mức Một phương pháp duyệt cây khác là duyệt theo mức. Bắt đầu duyệt từ gốc (đỉnh mức 0), rồi duyệt các con của gốc từ trái sang phải (các đỉnh mức 1), tiếp đến là các đỉnh mức 2,... Phần 2: Phân tích, thiết kế chương trình Chương trình xây dựng lớp Tree với các con trỏ trái, con trỏ phải. Lớp Tree gồm có các hàm sau: -Hàm nhập n số -Hàm xét n số vừa nhập thành cây -Hàm thêm 1 số vào cây -Hàm tính chiều cao của cây -Hàm đếm số lá trong cây -Hàm hiện các số thuộc tầng K của cây -Hàm tìm 1 nút bất kỳ -Hàm tìm tầng có chứa nút x -Hàm xoá -Hàm hiện nút theo các thứ tự ( trái_nút_phải, nút_trái_phải, trái_phải_nút ) -Hàm vẽ đồ hoạ Chức năng của từng hàm cụ thể như sau: _Hàm nhập (void nhap(tree *&T)): Cho phép ta nhập n số mà ta muốn, n số đó sẽ tạo thành n nút trong cây tìm kiếm nhị phân. _Hàm xét n số vừa nhập thành cây (void xet(tree *&T,int x)): Hàm này sẽ xét n số mà ta vừa nhập vào và sắp xếp chúng thành các nút trong cây. _Hàm thêm 1 số vào cây (void add(tree *&T,int x)): Hàm này cho phép ta nhập thêm 1 số vào dãy số mà ta đã nhập và xét số đó để sắp xếp vào vị trí của 1 nút trong cây. _Hàm tính chiều cao của cây (int H(tree *&T)): Hàm này dùng để tính chiều cao của cây tìm kiếm nhị phân tức là đếm số tầng trong cây tìm kiếm nhị phân. _Hàm đếm số lá trong cây (int demla(tree *&T,int &tong)): Sử dụng hàm này để đếm xem trong cây có tất cả bao nhiêu lá (nút). _Hàm hiện các số thuộc tầng K của cây (void hientang(tree *&T,int k)): Khi ta muốn biết tầng K của cây tìm kiếm nhị phân có tất cả bao nhiêu lá, ta sử dụng hàm void hientang(tree *&T,int k) này. _Hàm tìm 1 nút bất kỳ (int search(tree *&T,int x)): Hàm này cho phép người sử dụng tìm 1 nút bất kỳ nào đó mà người sử dụng muốn tìm, xem nút đó có trong cây không và nếu có thì nằm ở vị trí nào. _Hàm tìm tầng của 1 nút (int timtangnutx(tree *&T,int k,int x)): Sử dụng hàm này, ta có thể tìm xem nút mà ta muốn tìm nằm ở tầng nào trong cây. _Hàm xoá (void xoa(tree *&T,int x)): Hàm xoá cho phép ta xoá 1 nút trong cây tìm kiếm nhị phân. _Các hàm hiện nút theo các thứ tự trái_nút_phải, nút_trái_phải, trái_phải_nút (void LNR(tree *&T), void NLR(tree *&T), void LRN(tree *&T)): Hàm này cho ta xem cây nhị phân với các nút hiện theo thứ tự mà ta muốn xem như trái_nút_phải, nút_trái_phải hay là trái_phải_nút. _Các hàm vẽ đồ hoạ giúp ta nhìn ra các nút, các tầng của cây tìm kiếm nhị phân một cách rõ ràng và nhanh hơn. Phần 3: Giới thiệu các phương thức quan trọng trong chương trình 1. Nhập: void tree::nhap(tree *&T) { int n,x,i; cout>n; for(i=0;i<n;i++) { cout>x; xet(T,x); } } ------------------------------------------------------------- void tree::xet(tree *&T,int x) { if(T==NULL) { T=new tree; T->key=x; T->trai=T->phai=NULL; } else if(T->key==x) return; else if(T->key>x) xet(T->trai,x); else xet(T->phai,x); } 2. Hiện: Hiện các nút thuộc tầng K của cây: void tree::hientang(tree *&T,int k) { if(T==NULL) return; if(k==1) coutkey<<setw(3); hientang(T->trai,k-1); hientang(T->phai,k-1); } Hiện các nút theo các thứ tự trái_nút_phải, nút_trái_phải, trái_phải_nút: Trái -> nút -> phải : void tree::LNR(tree *&T) { if(T!=NULL) { LNR(T->trai); coutkey; LNR(T->phai); } } Nút -> trái -> phải : void tree::NLR(tree *&T) { if(T!=NULL) { coutkey; NLR(T->trai); NLR(T->phai); } } Trái -> phải -> Nút : void tree::LRN(tree *&T) { if(T!=NULL) { LRN(T->trai); LRN(T->phai); coutkey; } 3. Thêm: void tree::add(tree *&T,int x) { xet(T,x); } 4. Xoá: void tree::xoa(tree *&T,int x) {tree *t; if(T->keyphai,x); else if(T->key>x) xoa(T->trai,x); else if(T->key==x) if(T->phai!= NULL && T->trai!=NULL) { t=T->phai; T->key=t->key; xoa(T->phai,T->key); } else if(T->phai==NULL && T->trai!=NULL) { t=T->trai; T->key=t->key; xoa(T->trai,T->key); } else if(T->trai==NULL && T->phai!=NULL) { t=T->phai; T->key=t->key; xoa(T->phai,T->key); } else if(T->trai==NULL && T->phai==NULL) { T=T->phai; delete(t); return; } } 5. Tìm kiếm: Tìm 1 nút trong cây: int tree::search(tree *&T,int x) { if(T!=NULL) { if(T->key==x) return 1; else if(T->key>x) return search(T->trai,x); else return search(T->phai,x); } return 0; } Tìm tầng chứa nút x: int tree::timtangnutx(tree *&T,int k,int x) { if(T==NULL) return 0; if(k==1 && T->key==x) return 1; else if(T->key>x) return timtangnutx(T->trai,k-1,x); else return timtangnutx(T->phai,k-1,x); } Phần 4: Kết luận Bằng những kiến thức được thầy Trương Tiến Tùng và thầy Trương Công Đoàn giảng dạy trên lớp cùng sự hướng dẫn nhiệt tình của hai thầy, chúng em đã xây dựng chương trình cây tìm kiếm nhị phân bằng ngôn ngữ C++. Chương trình bao gồm những phương thức cơ bản để xây dựng một cây nhị phân tìm kiếm. Do đó có thể còn nhiều thiếu sót và chưa được mở rộng nhiều về mặt ứng dụng thực tế. Chúng em rất mong các thầy đóng góp ý kiến để chúng em rút kinh nghiệm và bổ sung thêm kiến thức cho những chương trình được xây dựng tiếp sau này. Chúng em xin chân thành cảm ơn.