Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: ADT - Cây nhị phân tìm kiếm - Cách cài đặt trong C++

  1. #1
    Ngày gia nhập
    10 2007
    Nơi ở
    Lang thang
    Bài viết
    7

    Mặc định ADT - Cây nhị phân tìm kiếm - Cách cài đặt trong C++

    Mấy hôm nay subforum Cấu trúc dữ liệu hình như nóng lên thì phải,em mới gia nhập diễn đàn thôi,mí hôm nọ định đóng góp thêm bài viết về Stack và Queue cài đặt dùng Danh sách liên kết,nhưng mờ lại đang thi tư tưởng HCM,hôm này tưng hửng về định đăng thì các bác lại chuyển sang chủ đề khác mất roài,thôi thì iem mới nghiên cứu về ADT Cây nhị phân tìm kiếm,đăng lun để mọi người góp ý cho iem,và nếu ai đang nghiên cứu thì bàn luận.

    Định nghĩa :Cây nhị phân tìm kiếm là cây nhị phân mà trong đó giá trị khoá của mọi nút là lớn hơn giá trị khoá trong các nút thuộc cây con trái,và nhỏ hơn giá trị khoá trong các nút thuộc cây con phải của nó.
    Chú ý : Ta có thể xem mỗi nút như một nút gốc,mà cây con trái và cây con phải bao gồm các nút con trái và con phải tương ứng của nó.

    -Để thuận tiện cho việc cài đặt ta có thể định nghĩa cấu trúc của một nút đơn giản như sau :
    + Con trỏ left trỏ tới cây con trái.
    + Con trỏ right trỏ tới cây con phải.
    + Trường info dùng để lưu trữ dữ liệu người dùng.

    C++ Code:
    1. struct TreeNode
    2. {
    3.     ItemType info;// ItemType la kieu du lieu.
    4.     TreeNode *left;
    5.     TreeNode *right;
    6. };
    Trong các bài toán phức tạp hơn ta có thể định nghĩa cấu trúc của nút một cách tuơng tự.


    Các phép toán cơ bản
    1.MakeEmpty()
    +Chức năng: Khởi tạo cây tới trạng thái rỗng.
    +Điều kiện sau : Cây tồn tại và ở trạng thái rỗng

    2.Boolean IsEmpty()
    +Chức năng: Kiểm tra xem liệu cây có rỗng hay không.
    +Điều kiện sau : Giá trị hàm = ( cây là rỗng ? ).

    3.Boolean IsFull()
    +Chức năng: Kiểm tra xem cây có đầy hay không.
    +Điều kiện sau : Giá trị hàm = ( cây là đầy ? ).

    4.int LengthTree()
    +Chức năng : Cho biết số lượng phần tử hiện có trong cây.
    +Điều kiện sau : Giá trị hàm = Số lượng phần tử trong cây.

    -Số lượng nút trên cây nhị phân là xác định nếu như ta biết được số lượng nút trên cây con trái và số lượng nút trên cây con phải.Khi đó
    Nút trên cây = Nút trên cây con trái + nút trên cây con phải + 1.
    -Điều này gợi ý cho ta cài đặt dùng thuật toán đệ quy.Sử dụng hàm CountNodes để đếm số lượng nút, sau đó hàm LengthTree() sẽ gọi và truyền con trỏ root tới CountNodes như một đối số.
    Hàm CountNodes
    + Chức năng : Đếm số lượng Nút.
    + BS : Nếu cây rỗng trả lại 0.
    + RS : Trả lại CountNodes( left-> subtree) + CountNodes( right-> subtree) + 1.

    5.RetrieveItem( ItemType& item, bool& found )
    +Chức năng : Truy tìm trong cây phần tử có key giống với key của item.
    +Điều kiện trước:Khoá của item đã được khởi tạo.
    +Điều kiện sau : Nếu như tồn tại một phần tử someItem mà key của nó giống với key của item thì found = true,và item là một bản sao của someItem, nếu không found = false.

    -Để tìm kiếm một phần tử item nào đó với thành phần key đã xác định trên cây nhị phân tìm kiếm.Trước hết, ta so sánh key của nó với key của nút gốc để quyết định xem liệu nút cần tìm có phải là nút gốc hay không, nếu không thì sẽ tiếp tục quá trình tìm kiếm trên cây con trái hay cây con phải.
    -Việc tìm kiếm trên cây con trái hay cây con phải cũng được thực hiện tương tự cho tới khi tìm kiếm được,hoặc là không.
    Như vậy, quá trình tìm kiếm có thể được thực hiện một cách đệ quy.Trường hợp cở sở xuất hiện khi hoặc nút cần tìm là nút gốc hoặc cây là rỗng (item không được tìm thấy trên cây).
    -Ta có thể cài đặt hàm đệ quy Retrieve() mà hàm RetrieveItem() gọi tới và truyền cho nó con trỏ root như một đối số.

    Hàm Retrieve
    + Chức năng : Truy tìm trên cây phân tử có key giống với key của item.
    + BS : (1) key của item bằng với key của nút gốc, khi đó thiết lập
    found = true và lưu item vào tree -> info( cập nhật lại).
    (2) Nếu cây là rỗng thì found = false.
    + RS : Nếu key của item nhỏ hơn key của tree -> info thì
    Retrieve( tree -> left,item,found), nếu không
    Retrieve( tree -> right,item,found).
    6.InsertItem( ItemType item )
    +Chức năng : Thêm một phần tử vào cây.
    +Điều kiện trước: Cây chưa đầy.
    +Điều kiện sau: item được chèn vào vị trí thích hợp trên cây đảm bảo duy trì thuộc tìm kiếm nhị phân

    -Chèn một phần tử mới vào cây không những đòi hỏi phải duy trì thuộc tính hình dạng của cây mà còn phải đảm bảo thuộc tính tìm kiếm nhị phân của nó.Ta sẽ chèn thêm một nút mới vào cây tại một vị trí thích hợp như một nút lá.
    -Cũng như các thuật toán đã cài đặt ở trên,ta viết hàm đệ quy Insert để chèn một phần tử vào cây,hàm mang theo một con trỏ tree tới nút gốc của cây.Hàm InsertItem đơn giản gọi tới hàm này và truyền cho nó con trỏ root như một tham chiếu

    7.DeleteItem( ItemType item )
    +Chức năng : Xoá phần tử có key giống với key của item.
    +Điều kiện trước : Thành phần key của item đã được khởi tạo
    Có duy nhất một phần tử trên cây có key giống với key của item.
    +Điền kiện sau : Không tồn tại phần tử nào trên cây có key giống với key của item

    - Trước hết, ta viết hàm Delete mang theo một con trỏ tree tới gốc của một cây để xoá đi một nút trên cây.Hàm DeleteItem đơn giản gọi tới và truyền cho hàm này con trỏ root như một tham chiếu.
    - Để xoá đi một nút trên cây hàm Delete cần thực hiện hai bước sau :
    + Tìm nút cần xoá trên cây.
    + Loại bỏ nút cần xoá khỏi cây.
    -Bước thứ nhất được thực hiện hoàn toàn giống như đã thực hiện khi cài đặt hàm Retrieve.Bước thứ hai phức tạp hơn xong ta có thể khái quát thành ba trường hợp cơ bản sau, tuỳ thuộc vào nút cần xoá:
    • Nút cần xoá là một nút lá : Việc xoá nó được thực hiện hết sức đơn giản, ta chỉ cần thiết lập liên kết cha của nút đó thành NULL.
    • Nút cần xoá chỉ có một con : Việc xoá được thực hiện bằng cách thiết lập liên kết giữa cha của nút cần xoá tới con của nó.
    • Nút cần xoá có hai con : Trường hợp này phức tạp hơn,ta không thể áp dụng phương pháp đã thực hiện khi xoá nút với chỉ một con, vì như thế sẽ làm mất đi thuộc tính hình dạng của cây nhị phân tìm kiếm.Thay vào đó ta đưa ra giải pháp thay thế thành phần info của nút cần xoá bằng thành phần info từ một nút khác mà vẫn duy trì được thuộc tính tìm kiếm nhị phân.,sau đó nút khác này sẽ được xoá đi.Như vậy, ta chỉ cần giải quyết vấn đề nút được thay thế. Đó chính là nút mà giá trị key của nó gần nhất nhưng nhỏ hơn ( hoặc lớn hơn )giá trị key nút cần xoá,nút này còn được gọi là tiền nhiệm –predecessor ( kế nhiệm-successor).Nút tiền nhiệm (cũng như kế nhiệm ) này chỉ có thể có một nút con hoặc không có nút con nào,việc xoá nó sau đó được thực hiện đơn giản.
    -Trong phân tích trên,hàm Delete sẽ cần tới một thủ tục xoá đi một nút, để chương trình được sáng sủa ta viết hàm DeleteNode để xoá đi một nút, hàm này sẽ được Delete gọi tới,và một hàm GetPredecessor để tìm người tiền nhiệm.

    8.PrintOrderTree
    +Chức năng : In ra các phần tử theo kiểu duyệt cây.

    -Để duyệt một danh sách tuyến tính chỉ có hai cách : tiến (forward) hoặc lùi (backward).Song đối với cây nhị phân ta có nhiều cách ,phổ dụng nhất là :
    + Duyệt theo thứ tự trước (PreOrder) .
    + Duyệt theo thứ tự giữa ( InOrder).
    + Duyệt theo thứ tự sau (PostOrder).
    -Mỗi cách duyệt thể hiện ưu điểm riêng của nó tuỳ trong trường hợp cụ thể.Chẳng hạn như để in ra các phần tử theo thứ tự tăng dần ta duyệt cây theo thứ tự giữa, hay để huỷ một cây thì duyệt theo thứ tự sau là thích hợp nhất,mỗi nút sẽ được xoá đi nếu như cây con trái và cây con phải của nó đã được phá huỷ.
    -Việc duyệt cây có thể được định nghĩa đệ quy một cách khái quát như sau :

    PreOrder(tree)
    Nếu tree # NULL thì :
    Thăm tree->info;
    PreOrder(tree->left);
    PreOrder(tree->right);

    InOrder(tree)
    Nếu tree # NULL thì :
    InOrder(tree->left);
    Thăm tree->info;
    InOrder(tree  left);

    PostOrder(tree)
    Nếu tree # NULL thì :
    PostOrder(tree->left);
    PostOrder(tree->right);
    Thăm tree->info;

    -Khi ta nói “Thăm” một nút ,điều đó được hiểu là những thao tác trên nút,chẳng hạn in ra giá trị,tính tổng của các thành phần,hay cập nhật lại một trường nào đó trong thành phần info của mỗi nút.
    -Để minh hoạ cho các phép duyệt, ta viết hàm PrintOrderTree để in ra giá trị của các nút theo kiểu duyệt do người dùng nhập vào,và tuỳ vào kiểu duyệt mà hàm gọi tới các hàm hỗ trợ tương ứng.
    [/TEX]
    Và dưới đây là toàn bộ mã của ADT BST:

    Khai báo lớp ADT BST được đặt trong file TreeType.h

    C++ Code:
    1. // Khai bao lop ADT Cay nhi phan tim kiem.
    2. #include<iostream>
    3.  
    4. struct TreeNode;
    5.  
    6. enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };
    7.  
    8. typedef int ItemType;
    9. // Gia su rang thanh phan key chua trong moi nut co kieu don gian int
    10. // Doi voi nhung kieu phuc tap hon ta co the dinh nghia tuong tu.
    11.  
    12. #ifndef TREETYPE_H
    13. #define TREETYPE_H
    14.  
    15. class TreeType
    16. {
    17. public:
    18.     TreeType(); // Constructor.
    19.     ~TreeType(); // Destructor.
    20.     TreeType( const TreeType& originalTree );// Copy Constructor.
    21.         void operator=( const TreeType& originalTree );
    22.         // Ham nap chong toan tu.
    23.     void MakeEmpty(); // Dua cay ve trang thai rong.
    24.     bool IsEmpty() const; // Kiem tra xem cay co rong hay khong.
    25.     bool IsFull() const; // Kiem tra xem cay co day hay khong.
    26.     int LengthTree();// Ham tra lai so phan tu co tren cay.
    27.     int DepthTree(); // Ham tra lai chieu sau cua cay.
    28.     void RetrieveItem( ItemType& item,bool &found );
    29.     // Ham truy luc toi phan tu tren cay co key giong voi key cua item.
    30.     void InsertItem( ItemType item ); // Chen mot phan tu vao cay.
    31.     void DeleteItem( ItemType item);
    32.     // Xoa phan tu tren cay co key giong voi key cua item.
    33.     void Print( std::ofstream& outFile);
    34.     // In ra outFile cac phan tu theo thu tu tang dan.
    35.     void PrintOrderTree( OrderType order );
    36.     // In ra noi dung cac nut theo kieu duyet order.
    37. private:
    38.     TreeNode *root;
    39. };
    40.  
    41. #endif

    Định nghĩa ADT BST được đặt trong file TreeType.cpp
    C++ Code:
    1. #include<iostream>
    2. #include<cstddef>
    3. #include<iomanip>
    4. #include<fstream>
    5.  
    6. using namespace std;
    7.  
    8. #include "TreeType.h"
    9.  
    10. struct TreeNode
    11. {
    12.     ItemType info;// Thong tin tren node;
    13.     TreeNode *left;// Con tro toi cay con trai.
    14.     TreeNode *right;// Con tro toi cay con  phai.
    15. };
    16.  
    17. // Nguyên mẫu của các hàm bổ trợ
    18.  
    19. void Destroy(TreeNode*& tree);
    20. void CopyTree( TreeNode*& copy,const TreeNode *originalTree );
    21. int  CountNodes(TreeNode *tree);
    22. int  Depth(TreeNode *tree);
    23. void Retrieve( TreeNode *tree, ItemType& item, bool& found);
    24. void Insert( TreeNode*& tree, ItemType item);
    25. void Delete( TreeNode*& tree, ItemType item);
    26. void DeleteNode(TreeNode*& tree);
    27. void GetPredecessor(TreeNode *tree, ItemType& data);
    28. void PrintTree( TreeNode *tree, std::ofstream& outFile );
    29. void PrintPreOrder( TreeNode *tree );
    30. void PrintInOrder( TreeNode *tree );
    31. void PrintPostOrder( TreeNode *tree );
    32.  
    33.  
    34. // Dinh nghia cac ham cua lop.
    35.  
    36. TreeType::TreeType()
    37. {
    38.     root = NULL;
    39. }
    40.  
    41. TreeType::~TreeType()
    42. {
    43.     Destroy(root);
    44. }
    45.  
    46. TreeType::TreeType( const TreeType& originalTree )
    47. {
    48.     CopyTree( root, originalTree.root );
    49. }
    50.  
    51. void TreeType::operator=( const TreeType& originalTree )
    52. {
    53.     if(&originalTree == this)
    54.         return;
    55.    
    56.     Destroy(root);
    57.     CopyTree(root,originalTree.root);
    58. }
    59.  
    60. void TreeType::MakeEmpty()
    61. {
    62.     Destroy(root);
    63.     root = NULL;
    64. }
    65.  
    66. bool TreeType::IsEmpty() const
    67. {
    68.     return(root == NULL);
    69. }
    70.  
    71. bool TreeType::IsFull() const
    72. {
    73.     TreeNode *location;
    74.  
    75.     location = new TreeNode;
    76.  
    77.     if(location == NULL)
    78.         return true;
    79.     else
    80.         return false;
    81.     delete location;
    82. }
    83.  
    84. int TreeType::LengthTree()
    85. {
    86.     return CountNodes(root);
    87. }
    88.  
    89. int TreeType::DepthTree()
    90. {
    91.     return Depth(root);
    92. }
    93.  
    94. void TreeType::RetrieveItem( ItemType& item, bool& found)
    95. {
    96.     Retrieve(root,item,found);
    97. }
    98.  
    99. void TreeType::InsertItem(ItemType item)
    100. {
    101.     if( IsFull() )
    102.     {
    103.         cout << "Het bo nho de cap phat !\n";
    104.         exit(1);
    105.     }
    106.  
    107.     Insert(root,item);
    108. }
    109.  
    110. void TreeType::DeleteItem( ItemType item)
    111. {
    112.     if( IsEmpty() )
    113.     {
    114.         cout << setw(25) << " " << "Cay rong !\n";
    115.         return;
    116.     }
    117.    
    118.     Delete(root,item);
    119. }
    120.  
    121. void TreeType::Print(std::ofstream& outFile)
    122. {
    123.     PrintTree(root,outFile);
    124. }
    125.  
    126. void TreeType::PrintOrderTree( OrderType order )
    127. {
    128.     switch(order)
    129.     {
    130.     case PRE_ORDER:   PrintPreOrder(root);
    131.                       break;
    132.     case IN_ORDER:
    133.                       PrintInOrder(root);
    134.                       break;
    135.     case POST_ORDER : PrintPostOrder(root);
    136.                       break;
    137.     }
    138. }
    139.                          
    140.                      
    141. // Dinh nghia cac ham ho tro.
    142.  
    143.  
    144. void Destroy(TreeNode*& tree)
    145. {
    146.     if(tree != NULL)
    147.     {
    148.         Destroy(tree->left);
    149.         Destroy(tree->right);
    150.         delete tree;
    151.     }
    152. }
    153.  
    154. void CopyTree( TreeNode*& copy,const TreeNode *originalTree )
    155. {
    156.     if(originalTree == NULL )
    157.         copy = NULL;
    158.     else
    159.     {
    160.         copy = new TreeNode;
    161.         copy->info = originalTree->info;
    162.  
    163.         CopyTree(copy->left,originalTree->left);
    164.         CopyTree(copy->right,originalTree->right);
    165.     }
    166. }
    167.  
    168. int CountNodes(TreeNode *tree)
    169. {
    170.     if(tree == NULL)
    171.         return 0;
    172.     else
    173.         return CountNodes(tree->left) + CountNodes(tree->right) + 1;
    174. }
    175.  
    176. int Depth(TreeNode *tree)
    177. {
    178.     if(tree == NULL)
    179.         return 0;
    180.     int leftSubTreeDepth = Depth(tree->left);
    181.     int rightSubTreeDepth = Depth(tree->right);
    182.  
    183.     return (1 + (leftSubTreeDepth > rightSubTreeDepth ? leftSubTreeDepth : rightSubTreeDepth));
    184. }
    185.  
    186. void Retrieve( TreeNode *tree, ItemType& item, bool& found)
    187. {
    188.     if(tree == NULL)
    189.         found = false;
    190.     else if(item < tree->info)
    191.         Retrieve(tree->left,item,found);
    192.     else if(item > tree->info)
    193.         Retrieve(tree->right,item,found);
    194.     else
    195.     {
    196.         found = true;
    197.         item = tree->info;
    198.     }
    199. }
    200.  
    201. void Insert( TreeNode*& tree, ItemType item)
    202. {
    203.     if(tree == NULL)
    204.     {
    205.         tree = new TreeNode;
    206.  
    207.         tree->info = item;
    208.         tree->left = NULL;
    209.         tree->right = NULL;
    210.     }
    211.  
    212.     else if(item < tree->info)
    213.         Insert(tree->left,item);// Chen vao cay con trai.
    214.     else if(item > tree->info)
    215.         Insert(tree->right,item);// Chen vao cay con phai.
    216. }
    217.  
    218. void Delete( TreeNode*& tree, ItemType item )
    219. {
    220.     if(item < tree->info)
    221.         Delete(tree->left,item);
    222.     else if(item > tree->info)
    223.         Delete(tree->right,item);
    224.     else
    225.         DeleteNode(tree);
    226. }
    227.  
    228. void DeleteNode(TreeNode*& tree)
    229. {
    230.     ItemType data;
    231.     TreeNode *temPtr;
    232.  
    233.     temPtr = tree;
    234.  
    235.     if(tree->left == NULL)
    236.     {
    237.         tree = tree->right;
    238.         delete temPtr;
    239.     }
    240.     else if(tree->right == NULL)
    241.     {
    242.         tree = tree->left;
    243.         delete temPtr;
    244.     }
    245.     else
    246.     {
    247.         GetPredecessor(tree->left,data);
    248.        
    249.         tree->info = data;
    250.         Delete(tree->left,data);
    251.     }
    252. }
    253.  
    254. void GetPredecessor( TreeNode *tree, ItemType& data )
    255. {
    256.     while(tree->right != NULL)
    257.         tree = tree->right;
    258.    
    259.     data = tree->info;
    260. }
    261.  
    262. void PrintTree( TreeNode *tree, std::ofstream& outFile )
    263. {
    264.     if(tree != NULL)
    265.     {
    266.         PrintTree(tree->left,outFile);
    267.         outFile << tree->info;
    268.         PrintTree(tree->right,outFile);
    269.     }
    270. }
    271.  
    272. void PrintPreOrder( TreeNode *tree )
    273. {
    274.     if( tree != NULL )
    275.     {
    276.         cout << setw(3) << tree->info;
    277.         PrintPreOrder( tree->left );
    278.         PrintPreOrder( tree->right );
    279.     }
    280. }
    281.  
    282. void PrintInOrder( TreeNode *tree )
    283. {
    284.     if( tree != NULL )
    285.     {
    286.         PrintInOrder( tree->left );
    287.         cout << setw(3) << tree->info;
    288.         PrintInOrder( tree-> right );
    289.     }
    290. }
    291.  
    292. void PrintPostOrder( TreeNode *tree )
    293. {
    294.     if( tree != NULL )
    295.     {
    296.         PrintPostOrder( tree->left );
    297.         PrintPostOrder( tree->right );
    298.         cout << setw(3) << tree->info;
    299.     }
    300. }

    Hàm main có thể được cài đặt như sau để kiểm tra cây nhị phân mà ta vừa cài đặt trên.

    C++ Code:
    1. // Test thu cac ham thao tac tren Cay nhi phan tim kiem.
    2. #include<iostream>
    3. #include<iomanip>
    4.  
    5. using namespace std;
    6.  
    7. #include "TreeType.h"
    8.  
    9. int main()
    10. {
    11.     TreeType myTree;
    12.     ItemType item;
    13.     OrderType order;
    14.     int choice,option;
    15.     bool found;
    16.  
    17.     cout << setw(15) << " " << "CHUONG TRINH TEST THU CAY NHI PHAN TIM KIEM\n"
    18.          << setw(15) << " " << "==========================================="
    19.          << "\n\n\n";
    20.     cout << setw(20) << " " << "1:Tao cay ADT BST\n"
    21.          << setw(20) << " " << "2:Chen phan tu moi vao cay BST\n"
    22.          << setw(20) << " " << "3:Xoa phan tu khoi cay BST\n"
    23.          << setw(20) << " " << "4:Truy tim phan tu\n"
    24.          << setw(20) << " " << "5:In ra tong so phan tu\n"
    25.          << setw(20) << " " << "6:In ra chieu sau cua cay\n"
    26.          << setw(20) << " " << "7:In ra cac phan tu theo kieu duyet\n"
    27.          << setw(20) << " " << "8:Huy cay da duoc tao\n"
    28.          << setw(20) << " " << "9:Thoat khoi ung dung\n\n";
    29.  
    30.     while(1)
    31.     {
    32.         cout << "Nhap vao lua chon cua ban:";
    33.         cin >> choice;
    34.  
    35.         switch(choice)
    36.         {
    37.         case 1: int number;
    38.                 cout << "Nhap so luong nut :";
    39.                 cin >> number;
    40.                
    41.                 while(number > 0)
    42.                 {
    43.                     cout << "Nhap gia tri :";
    44.                     cin >> item;
    45.  
    46.                     myTree.InsertItem(item);
    47.                     number--;
    48.                 }
    49.                 break;
    50.  
    51.         case 2: cout << "Nhap vao mot so nguyen :";
    52.                    cin >> item;
    53.            
    54.                myTree.InsertItem(item);
    55.                break;
    56.    
    57.             case 3: cout << "Nhap vao phan tu can xoa :";
    58.                    cin >> item;
    59.                myTree.DeleteItem(item);
    60.                break;
    61.    
    62.             case 4: cout << "Nhap phan tu can tim kiem :";
    63.                    cin >> item;
    64.            
    65.                 myTree.RetrieveItem(item,found);
    66.            
    67.                 if( found == true)
    68.                     cout << "Phan tu co mat tren cay !\n";
    69.                 else
    70.                     cout << "Phan tu khong co tren cay !\n";
    71.                 break;
    72.    
    73.             case 5: cout << "So phan tu hien co tren cay la: "
    74.                           << myTree.LengthTree() << endl;
    75.                    break;
    76.    
    77.             case 6: cout << "Chieu sau cua cay la: "
    78.                   << myTree.DepthTree() << endl;
    79.                    break;
    80.    
    81.             case 7: cout << setw(20) << " " << "1:Duyet theo thu tu truoc\n"
    82.                      << setw(20) << " " << "2:Duyet theo thu tu giua\n"
    83.                      << setw(20) << " " << "3:Duyet theo thu tu sau\n";
    84.            
    85.                 cout << "Nhap vao lua chon cua ban:";
    86.                 cin >> option;
    87.            
    88.                 order = (OrderType) (option-1);
    89.            
    90.                 if( myTree.IsEmpty() )
    91.                 {
    92.                     cout << "Cay rong!\n";
    93.                     break;
    94.                 }
    95.            
    96.                 else
    97.                     myTree.PrintOrderTree(order);
    98.                     cout << endl;
    99.                 break;
    100.            case 8: myTree.MakeEmpty();
    101.                   break;
    102.            case 9: return 0;
    103.    
    104.         }
    105.     }
    106.  
    107.     return 0;
    108. }

    Hì hì muộn roài,có chi các bác cho ý kiến,lần sau iem xin cài đặt một số hàm hok dùng đệ quy.
    Người đẹp lại lấy người xinh.bao nhiêu kẻ xấu rập rình lấy nhau !!!

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Cậu viết BST mà lại ko có chức năng rotation thì làm sao đảm bảo cây balance được. Updates gấp nhé.

    Thế này , hôm nào tớ viết cái này rồi mang lên đây cùng thảo luận giờ tớ nói chay nhé.

    Cái hàm delete của cậu theo tớ có chút vấn đề, vấn đề nhỏ thôi vì chả có sách nào nói cả .

    Nếu mà Node cần del có 2 lá. Thì cậu đi tìm nút tiền nhiệm (min leftSubTree) hoặc nút kế nhiệm ( max rightSubTree ) đúng ko ? Điều tớ muốn nói là ở chỗ chữ hoặc. Chính nó là nguyên nhân khiến cây mất cân bằng mà với thao tác này ( tớ nghĩ ra ) sẽ giảm khả năng đó đi.

    ví dụ tớ cho cây con subRoot (A,B) với độ cao A= B - 1 hay A nhỏ hơn B 1. giờ xóa subRoot , node này có 2 subTree A,B mặc định theo funtion của cậu thì sẽ delete node tiền nhiệm có nghĩa là độ cao có khả năng = B - 2 dẫn đến mất cân bằng . Nhưng nếu thay vào đó cậu tìm nút kế nhiệm thì có phải là độ cao A=B ko ?

    Điều tớ muốn nói là tại sao sách nào cũng OR mà không phải là AND, nếu cài đặt theo kiểu của tớ thì có phải là khả năng mất cần bằng sẽ giảm rất nhiều. Bằng cách:
    if(H(leftSubTree =< rightSubTree)
    {tim nút tiền nhiệm}
    else
    {tìm nút kế nhiệm}

    Đặc biệt là các hàm giúp cho cây cân bằng . Ngoài 2 phép quay chuẩn trên liệu có cách nào nữa không ?

    Cuối cùng xin thay mặt anh em cảm ơn bài viết rất chi tiết của cậu. Mong được thảo luận nhiều hơn . Thân KidKid.
    Đã được chỉnh sửa lần cuối bởi iamvtn : 29-11-2007 lúc 01:06 PM.

  3. #3
    Ngày gia nhập
    09 2006
    Bài viết
    16

    đây là cây BST chứ ko phải AVL nên ko cần balance. Nhưng nếu có balance thì càng tốt.
    nothing is impossible

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    Lang thang
    Bài viết
    7

    thanks bác kidkid đã góp ý.Nhưng theo iem,nhược điểm lớn nhất của ADT BST chính là trường hợp cây mất cân bằng,mà việc này do từ dữ liệu đầu vào,nếu người dùng nhập cây theo thứ tự tăng dần hay giảm dần,thì cây thu được là cây suy biến,việc tìm kiếm một key trên cây giống nhu trong danh sách liên kết vậy 0(N).Ý tưởng trong hàm xóa của bác cũng là một ý kiến hay,có thể sửa code đơn gian như sau,ta thêm một hàm GetSuccessor để tìm người kế nhiệm,chỉnh trong hàm DeleteNode điều kiện như bác nêu ra,nhưng nếu người dùng nhập dữ liệu như iem nói trên thì hok hiệu quả lắm.Nói chung mỗi cấu trúc có một điểm mạnh riêng,ta có thể thấy sự khắc phục tính mất cân bằng trong cây AVL hay trong Heap,Priority Queue, Black-Red tree,có dịp iem xin trình bày
    Người đẹp lại lấy người xinh.bao nhiêu kẻ xấu rập rình lấy nhau !!!

  5. #5
    Ngày gia nhập
    06 2007
    Nơi ở
    Hà Nội
    Bài viết
    361

    cây avl , cây đỏ đen, search trên wikipedia ấy, sẽ có giới thiệu khá tổng quát, cái này khắc phục mất cân bằng của cây nhị phân còn code thế nào thì tìm mấy ebook đầy ra đấy
    Blog tổng quan kiến thức về viễn thông : http://tongquanvienthong.blogspot.com/

    mSPDict từ điển android hỗ trợ liên kết tra trên các trình đọc sách điện tử và tra sách giấy thông qua camera
    http://www.tinhte.vn/threads/691731/

  6. #6
    Ngày gia nhập
    12 2009
    Bài viết
    27

    Mặc định Hàm IsFull()

    Các anh chị cho em hỏi chút ạ.Ở hàm IsFull() thì có nghĩa là cây chỉ đầy khi mà máy tính không còn đủ bộ nhớ đề cấp phát cho chương trình ạ? Và khi đó nếu yêu cầu cấp phát 1 vung nhớ thì nó sẽ trỏ đến NULL ạ?
    Tại em đọc 1 vài tài liệu thì chỉ thấy khi cài đặt bằng mảng người ta mới có Hàm IsFull() thôi
    Mong anh chị giúp đỡ !

  7. #7
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    165

    Trích dẫn Nguyên bản được gửi bởi fuji13 Xem bài viết
    Các anh chị cho em hỏi chút ạ.Ở hàm IsFull() thì có nghĩa là cây chỉ đầy khi mà máy tính không còn đủ bộ nhớ đề cấp phát cho chương trình ạ? Và khi đó nếu yêu cầu cấp phát 1 vung nhớ thì nó sẽ trỏ đến NULL ạ?
    Tại em đọc 1 vài tài liệu thì chỉ thấy khi cài đặt bằng mảng người ta mới có Hàm IsFull() thôi
    Mong anh chị giúp đỡ !

    cây đầy đủ là cây mà có mọi nút lá đều có bậc bằng nhau.ko phải hết bộ nhớ.
    HT117-5277

  8. #8
    Ngày gia nhập
    12 2009
    Bài viết
    27

    Trích dẫn Nguyên bản được gửi bởi treatmaster Xem bài viết
    cây đầy đủ là cây mà có mọi nút lá đều có bậc bằng nhau.ko phải hết bộ nhớ.
    bool IsFull() const; // Kiem tra xem cay co day hay khong.
    Bạn hiểu sai ý mình hỏi thì phải

  9. #9
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    165

    cây chỉ đầy khi mà máy tính không còn đủ bộ nhớ đề cấp phát cho chương trình ạ?

    mình đọc đoạn này.
    thế ko hiểu ý của bạn là gì nữa nhỉ.
    HT117-5277

  10. #10
    Ngày gia nhập
    10 2011
    Bài viết
    2

    thankz pro ::beauty:

Các đề tài tương tự

  1. [Kiếm Thế] Kiếm Thế Ngạo Thiên Kiếm Chạy Thử Nghiệm vào 10h ngày 15/09
    Gửi bởi c0jskull trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 5
    Bài viết cuối: 29-09-2013, 10:45 AM
  2. Cách hiển thị KQ tìm kiếm trên trang Tìm kiếm trong MVC
    Gửi bởi nobita2009hp trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 0
    Bài viết cuối: 02-07-2012, 04:19 PM
  3. Tìm kiếm trong c# như tìm kiếm của google ( auto complete )
    Gửi bởi bigstone trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 24
    Bài viết cuối: 08-09-2011, 11:52 PM
  4. Code tìm kiếm trong cây nhị phân trong C++. Lỗi chỉ tìm được từ đầu tiên trong file thôi sửa thế nào?
    Gửi bởi elvish trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 1
    Bài viết cuối: 11-04-2010, 09:43 PM
  5. [LT][Tìm kiếm]Xóa node trong cây nhị phân tìm kiếm
    Gửi bởi schtroumpfs trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 05-06-2007, 05:47 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn