Thực hành ngôn ngữ lập trình C++ - Gợi ý cài đặt lớp BSearchTree

TH Ngôn ngữ lập trình C++ Học kì I, năm học 2007-2008 
Hoàng Thị Điệp, Bộ môn Khoa học Máy tính 
Gợi ý cài đặt lớp BSearchTree (tuần 13) 
 Hàm hủy: gọi tới hàm delTree xóa đệ quy cây nhị phân (delTree duyệt cây kiểu pre-order) 
 Hàm dựng sao chép: gọi tới hàm copyTree sao đệ quy cây nhị phân (copyTree duyệt cây kiểu 
post-order) 
 Hàm show: gọi tới hàm showInorder in đệ quy cây nhị phân (showInorder duyệt cây kiểu in-
order) 
A- LÝ THUYẾT: BA CÁCH DUYỆT CÂY NHỊ PHÂN 
Hình 1 Minh họa cây tìm kiếm nhị phân 
1) Duyệt trung thứ tự (Inorder Traversal Algorithm) 
Các bước duyệt trung thứ tự: 
1. Duyệt trung thứ tự đối với cây con trái 
2. Xử lý ở nút hiện tại (in giá trị của data) 
3. Duyệt trung thứ tự đối với cây con phải. 
Nếu cây con trái của một nút chưa được xử lý thì giá trị của nó sẽ chưa được xử lý. Kết quả duyệt 
trung thứ tự của cây trong Hình 1 là 6 13 17 27 33 42 48 
Chú ý: duyệt trung thứ tự trên một cây tìm kiếm nhị phân sẽ cho kết quả là các giá trị tăng dần. Vì 
vậy, việc tạo một cây tìm kiếm nhị phân thực chất là sắp xếp dữ liệu, nó được gọi là sắp xếp bằng 
cây nhị phân. 
2) Duyệt tiền thứ tự (Preorder Traversal Algorithm) 
Các bước duyệt tiền thứ tự: 
1. Xử lý ở nút hiện tại 
2. Duyệt tiền thứ tự với cây con trái 
3. Duyệt tiền thứ tự với cây con phải 
Giá trị của mỗi nút được xử lý ngay khi nó được thăm. Sau khi giá trị ở một nút cho trước được 
xử lý thì các giá trị ở cây con trái được xử lý. Sau đó các giá trị ở cây con phải được xử lý. Kết 
quả duyệt tiền thứ tự ở cây trong Hình 1 là 27 13 6 17 42 33 48 
3) Duyệt hậu thứ tự (Postorder Traversal Algorithm) 
Các bước duyệt hậu thứ tự: 
1. Duyệt hậu thứ tự với cây con trái 
2. Duyệt hậu thứ tự với cây con phải 
TH Ngôn ngữ lập trình C++ Học kì I, năm học 2007-2008 
Hoàng Thị Điệp, Bộ môn Khoa học Máy tính 
3. Xử lý ở nút hiện tại 
Giá trị ở mỗi nút chỉ được in ra khi tất cả các con của nó đã được in. Kết quả duyệt hậu thứ tự của 
cây trong Hình 1 là 6 17 13 33 48 42 27 
B- MỘT LỜI GIẢI CHO LỚP BSEARCHTREE 
// Tac gia: Hoang Thi Diep 
// Muc dich: Mot loi giai cho lop BSearchTree 
//---------------------------------------------------------------------------- 
#include 
#include 
using namespace std; 
//---------------------------------------------------------------------------- 
// struct Node cai dat cac nut trong cay tk nhi phan 
//---------------------------------------------------------------------------- 
struct Node{ 
 int data; 
 Node * left; 
 Node * right; 
}; 
//---------------------------------------------------------------------------- 
// Lop BSearchTree cai dat cay tk nhi phan 
//---------------------------------------------------------------------------- 
class BSearchTree 
{ 
public: 
 BSearchTree(); 
 BSearchTree(const BSearchTree & atree); // pre-order 
 ~BSearchTree(); // post-order 
 void add(int x); 
 int find(int x); 
 string show(); // in-order 
// void test(); 
private: 
 void delTree(Node * & anode); // de quy 
 void copyTree(Node * const & snode, Node * & dnode); // de quy 
 string showInorder(Node * & anode); // de quy 
 Node * root; 
}; 
BSearchTree::BSearchTree() 
{ 
 root = NULL; 
} 
BSearchTree::BSearchTree(const BSearchTree & atree) 
{ 
TH Ngôn ngữ lập trình C++ Học kì I, năm học 2007-2008 
Hoàng Thị Điệp, Bộ môn Khoa học Máy tính 
 copyTree(atree.root, root); 
 cout << "Xong ham huy!" << endl; 
} 
void BSearchTree::copyTree(Node * const & snode, Node * & dnode) 
{ 
 if(snode == NULL){ 
 dnode = NULL; 
 return; 
 } 
 dnode = new Node; 
 dnode->data = snode->data; 
 copyTree(snode->left, dnode->left); 
 copyTree(snode->right, dnode->right); 
} 
BSearchTree::~BSearchTree() 
{ 
 delTree(root); 
} 
void BSearchTree::delTree(Node * & anode) 
{ 
 if(anode == NULL) return; 
 Node * delLeft = anode->left; 
 Node * delRight = anode->right; 
 anode->left = NULL; 
 delTree(delLeft); 
 anode->right = NULL; 
 delTree(delRight); 
 delete anode; 
 anode = NULL; 
} 
void BSearchTree::add(int x) 
{ 
 Node * p = new Node; 
 p->data = x; 
 p->left = NULL; 
 p->right = NULL; 
 if(root == NULL){ 
 root = p; 
 return; 
 } 
 Node * pos = root; 
 Node * prev = root; 
 bool left = true; 
 while(pos != NULL){ 
 prev = pos; 
 if(x data){ 
 pos = pos->left; 
TH Ngôn ngữ lập trình C++ Học kì I, năm học 2007-2008 
Hoàng Thị Điệp, Bộ môn Khoa học Máy tính 
 left = true; 
 }else{ 
 pos = pos->right; 
 left = false; 
 } 
 } 
 if(left) prev->left = p; 
 else prev->right = p; 
} 
int BSearchTree::find(int x) 
{ 
 Node * p = root; 
 while(p != NULL){ 
 if(p->data == x) return 1; 
 else if(p->data left; 
 else p = p->right; 
 } 
 return -1; 
} 
string BSearchTree::show() 
{ 
 cout << "\nIn cay nhi phan: " << endl; 
 return showInorder(root); 
} 
string BSearchTree::showInorder(Node * & anode) 
{ 
 if(anode == NULL) return ""; 
 ostringstream oss; 
 oss left); 
 oss data << " "; 
 oss right); 
 return oss.str(); 
} 
/* 
void BSearchTree::test() 
{ 
 delTree(root); 
} 
*/ 
//---------------------------------------------------------------------------- 
// Chuong trinh test 
//---------------------------------------------------------------------------- 
int main() 
{ 
 BSearchTree btree; 
 btree.add(5); 
 btree.add(4); 
 btree.add(7); 
TH Ngôn ngữ lập trình C++ Học kì I, năm học 2007-2008 
Hoàng Thị Điệp, Bộ môn Khoa học Máy tính 
 btree.add(12); 
 btree.add(3); 
 btree.add(6); 
 btree.add(1); 
 cout << btree.show(); 
 int key = 15; 
 cout << "\nTim kiem key = " << key << endl << "Ket qua: "; 
 if(btree.find(key) == 1) cout << "Thay!" << endl; 
 else cout << "Khong thay!" << endl; 
 BSearchTree btree2(btree); 
 cout << btree2.show(); 
 btree2.add(7); 
 BSearchTree * btree3Ptr = new BSearchTree(btree2); 
 cout show(); 
 delete btree3Ptr; 
 btree3Ptr = NULL; 
 cin.get(); 
 return 0; 
}