Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Xin hỏi về cây nhị phân tìm kiếm

  1. #1
    No Avatar
    giang222 Khách

    Smile Xin hỏi về cây nhị phân tìm kiếm

    Mình đang học về Cấu trúc dữ liệu, đến phần cây nhị phân tìm kiếm. Do mình lập trình hơi yếu nên hơi mơ hồ về cái này. Mình xây dựng được một số hàm, test thì mình chưa, nhưng nghĩ cũng đúng. Quan trọng là mình còn hàm để xóa một nút của cây, cái này mình có test nhưng không được, mình cũng không biết thiếu gì nữa. Các bạn xem và test giùm mình nha (chủ yếu là hàm delete và hàm main):
    C++ Code:
    1. #include <iostream.h>
    2. #define MAX 1000
    3. typedef struct Node *TREE;
    4. struct Node
    5. {
    6.     int key;
    7.     TREE p, left, right;
    8. };
    9. TREE T;
    10.  
    11. void khoitao (TREE &T)
    12. {
    13.     T = NULL;
    14. }
    15. //////////////////////////////////duyet cay theo thu tu giua
    16. void INORDER_TREE_WALK (TREE &T)
    17. {
    18.     if (T != NULL)
    19.     {
    20.         INORDER_TREE_WALK (T ->left);
    21.         cout << T ->key;
    22.         INORDER_TREE_WALK (T ->right);
    23.     }
    24. }
    25.  
    26. TREE TREE_SEARCH (TREE &T, int k)
    27. {
    28.     if (T != NULL || k == T ->key) 
    29.         return T;
    30.     if (k < T ->key)
    31.         return TREE_SEARCH (T ->left, k);
    32.     else
    33.         return TREE_SEARCH (T ->right, k);
    34. }
    35.  
    36. TREE TREE_MINIMUM (TREE &T)
    37. {
    38.     while (T ->left != NULL)
    39.         T = T ->left;
    40.     return T;
    41. }
    42.  
    43. TREE TREE_MAXIMUM (TREE &T)
    44. {
    45.     while (T ->right != NULL)
    46.         T = T ->right;
    47.     return T;
    48. }
    49.  
    50. TREE TREE_SUCCESSOR (TREE &T)
    51. {
    52.     if (T ->right != NULL)
    53.         return TREE_MINIMUM (T ->right);
    54.     TREE y = T ->p;
    55.     while (y != NULL && T == y ->right)
    56.     {
    57.         T = y;
    58.         y = y ->p;
    59.     }
    60.     return y;
    61. }
    62.  
    63. TREE TREE_PREDECESSOR (TREE &T)
    64. {
    65.     if (T ->left != NULL)
    66.         return TREE_MAXIMUM (T ->left);
    67.     TREE y = T ->p;
    68.     while (y != NULL && T == y ->left)
    69.     {
    70.         T = y;
    71.         y = y ->p;
    72.     }
    73.     return y;
    74. }
    75.  
    76. void TREE_INSERT (TREE &T, TREE z)
    77. {
    78.     TREE y = NULL;
    79.     TREE x = T;
    80.     while (x != NULL)
    81.     {
    82.         y = x;
    83.         if (z ->key < x ->key)
    84.             x = x ->left;
    85.         else
    86.             x = x ->right;
    87.     }
    88.     z ->p = y;
    89.     if (y == NULL)
    90.         T = z;
    91.     else if (z ->key < y ->key)
    92.         y ->left = z;
    93.     else
    94.         y ->right = z;
    95.  
    96. }
    97.  
    98. TREE TREE_DELETE (TREE &T, TREE z)
    99. {
    100.     TREE y, x, r;
    101.     if (z ->left == NULL || z ->right == NULL)
    102.         y = z;
    103.     else
    104.         y = TREE_SUCCESSOR (z);
    105.  
    106.     if (y ->left != NULL)
    107.         x = y ->left;
    108.     else
    109.         x = y ->right;
    110.  
    111.     if (x != NULL)
    112.         x ->p = y ->p;
    113.  
    114.     r = y ->p;
    115.     if (y ->p == NULL)
    116.         T = x;
    117.     else if (y = r ->left)
    118.         r ->left = x;
    119.     else
    120.         r ->right = x;
    121.  
    122.     if (y != x)
    123.         z ->key = y ->key;
    124.     return y;
    125. }
    126.  
    127. void duyetcay(TREE &T)
    128. {
    129.  
    130.     if(T != NULL)
    131.     {
    132.         cout << T ->key << endl;
    133.         duyetcay (T ->left);
    134.         duyetcay (T ->right);  
    135.     }
    136. }
    137.  
    138. void main ()
    139. {
    140.     int k, delk;
    141.     TREE T, z;
    142.     khoitao (T);
    143.     do
    144.     {
    145.         cout << "Nhap vao khoa cua cay nhi phan (-1 de ket thuc): ";
    146.         cin >> k;
    147.         z = new (Node);
    148.         z ->key = k;
    149.         z ->left = NULL;
    150.         z ->right = NULL;
    151.         z ->p = NULL;
    152.         if (z ->key > 0)
    153.             TREE_INSERT (T, z);
    154.     }
    155.     while (z ->key > 0);
    156.     duyetcay (T);
    157.    
    158.     cout << "Nhap vao khoa can xoa: ";
    159.     cin >> delk;
    160.              // đến đây mình không biết gọi hàm xóa như thế nào?
    161.     duyetcay (T);
    162.  
    163. }

  2. #2
    Ngày gia nhập
    06 2008
    Bài viết
    25

    Viết đến đâu test đến đó, đến hàm nào bị lỗi thì nói, chứ làm 1 đống rồi bảo "test thì mình chưa, nhưng nghĩ cũng đúng" chẳng khác nào "mình lười test wá, các bạn rãnh thì làm hộ mình đi" à?

    Vả lại đổi tên biến cho nó có nghĩa đi, code rắc rồi mà tên biến lại còn x, y, z thì quả là khó cho người khác đọc. Hàm delete mình đọc chưa hiểu dc nữa.

  3. #3
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Bạn đã hiểu không chính xác lý thuyết về cây rùi. Xem lại phần khai báo và lý thuyết tại đây.

    Một số hàm của bạn mình không hiểu mục đích của nó. Bạn mô tả lại cho mình mình sẽ sửa lại nó cho thích hợp.

    Còn thiếu một số ham trong bài như: GetNode() tạo một node mới, FreeNode() xóa node nào đó.

    Cả bài không hề sử dụng cấp phát và thu hồi bộ nhớ, bạn xem lại điều này nhé.

    Hàm main mình chưa sửa gì, bạn tạo lại nhé!

    Vì là cây nhị phân nên mình Add Node chứ không Insert Node. Hàm Del có liên quan mấy hàm trên nên không sửa gì.

    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. #define MAX 1000
    4.  
    5.  
    6. struct Node
    7. {
    8.     int key;
    9.     struct Node* left;
    10.     struct Node* right;//2 con tro trai phai thoi chu ban
    11. };
    12. typedef struct Node* TREE;
    13.  
    14. void khoitao (TREE &root)
    15. {
    16.     root = NULL;
    17. }
    18. //////////////////////////////////duyet cay theo thu tu giua
    19. void INORDER_TREE_WALK(TREE &root) //goi la Left-Node-Right
    20. {
    21.     if (root != NULL)
    22.     {
    23.         INORDER_TREE_WALK (root->left);
    24.         cout << root->key << "   ";
    25.         INORDER_TREE_WALK (root->right);
    26.     }
    27. }
    28.  
    29. bool TREE_SEARCH (TREE &T, int k)         /////////Sua ham nay chut, co the tra ve kieu int cung ok
    30. {
    31.     if (T==NULL) return false;
    32.     else if (k == T ->key)
    33.         return true;
    34.     else if (k < T ->key)
    35.         return TREE_SEARCH (T ->left, k);
    36.     else
    37.         return TREE_SEARCH (T ->right, k);
    38. }
    39.  
    40. /*TREE TREE_MINIMUM (TREE &T)   //// 2 ham max min nay minh chang biet dung de lam gi
    41. {
    42.     while (T ->left != NULL)
    43.         T = T ->left;
    44.     return T;
    45. }
    46.  
    47. TREE TREE_MAXIMUM (TREE &T)
    48. {
    49.     while (T ->right != NULL)
    50.         T = T ->right;
    51.     return T;
    52. }
    53.  
    54. TREE TREE_SUCCESSOR (TREE &T) //Vi luc dau hieu sai van de nen ham nay khong chinh xac roi
    55. {                                   //Ham nay de lam gi the, minh se sua them khi hieu y dinh cua ham
    56.     if (T ->right != NULL)
    57.         return TREE_MINIMUM (T ->right);
    58.     TREE y = T;          //////////////
    59.     while (y != NULL && T == y ->right)
    60.     {
    61.         T = y;
    62.         y = y ->p;
    63.     }
    64.     return y;
    65. }
    66.  
    67. TREE TREE_PREDECESSOR (TREE &T) /////////cung vay, khong hieu de lam gi
    68. {
    69.     if (T ->left != NULL)
    70.         return TREE_MAXIMUM (T ->left);
    71.     TREE y = T ->p;
    72.     while (y != NULL && T == y ->left)
    73.     {
    74.         T = y;
    75.         y = y ->p;
    76.     }
    77.     return y;
    78. }*/
    79.  
    80. void TREE_ADDNODE (TREE &T, TREE z)//add node to tree
    81. {
    82.     TREE p=T;
    83.     if (p==NULL) p=z;
    84.     else if(p ->key > z->key) TREE_INSERT (p->left,z);
    85.     else TREE_INSERT (p->right,z);
    86.    
    87. }
    88.  
    89. /*TREE TREE_DELETE (TREE &T, TREE z)
    90. {
    91.     TREE y, x, r;
    92.     if (z ->left == NULL || z ->right == NULL)
    93.         y = z;
    94.     else
    95.         y = TREE_SUCCESSOR (z);
    96.  
    97.     if (y ->left != NULL)
    98.         x = y ->left;
    99.     else
    100.         x = y ->right;
    101.  
    102.     if (x != NULL)
    103.         x ->p = y ->p;
    104.  
    105.     r = y ->p;
    106.     if (y ->p == NULL)
    107.         T = x;
    108.     else if (y = r ->left)
    109.         r ->left = x;
    110.     else
    111.         r ->right = x;
    112.  
    113.     if (y != x)
    114.         z ->key = y ->key;
    115.     return y;
    116. }
    117.  
    118. void PREORDER_TREE(TREE &T)  // nhu ham inorder thui, day la ham duyet cay: Node-Left-Right
    119. {
    120.  
    121.     if(T != NULL)
    122.     {
    123.         cout << T ->key << endl;
    124.         PREORDER_TREE(T ->left);
    125.         PREORDER_TREE(T ->right);
    126.     }
    127. }
    128.  
    129. /*void main ()
    130. {
    131.     int k, delk;
    132.     TREE T, z;
    133.     khoitao (T);
    134.     do
    135.     {
    136.         cout << "Nhap vao khoa cua cay nhi phan (-1 de ket thuc): ";
    137.         cin >> k;
    138.         z = new (Node);
    139.         z ->key = k;
    140.         z ->left = NULL;
    141.         z ->right = NULL;
    142.         z ->p = NULL;
    143.         if (z ->key > 0)
    144.             TREE_INSERT (T, z);
    145.     }
    146.     while (z ->key > 0);
    147.     PREORDER_TREE(T);
    148.  
    149.     cout << "Nhap vao khoa can xoa: ";
    150.     cin >> delk;
    151.              // đến đây mình không biết gọi hàm xóa như thế nào?
    152.     PREORDER_TREE(T);
    153.  
    154. }*/
    Hope this help!

  4. #4
    No Avatar
    giang222 Khách

    Những phần mình làm ở trên là theo bài học của thầy mình dạy. các hàm như TREE-MINIMUM: Tìm phần tửcó khoá nhỏ nhất, TREE-MAXIMUM: Tìm phần tử có khoá lớn nhất, TREE-SUCCESSOR: Tìm phần tử đi sau một phần tử, TREE-PREDECESSOR: Tìm phần tử đi trước một phần tử. các tên hàm cũng do thầy mình đặt, còn có tên hàm tiếng Việt là do mình đặt cho dễ hiểu. thầy yêu cầu mình hiện thực các hàm đã học của cây nhị phân tìm kiếm trong C++. Mình viết 1 hồi rồi viết không được hàm Delete nữa!

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. [Kiếm Thế] Kiếm Thế Kiếm Linh Chạy Thử Nghiệm vào 10h ngày 4/7
    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: 1
    Bài viết cuối: 05-07-2013, 12:16 PM
  3. [Kiếm Thế] Kiếm Thế Kiếm Linh Chạy Thử Nghiệm vào 10h ngày 4/7
    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: 0
    Bài viết cuối: 03-07-2013, 10:30 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