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

[giang222]

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):

#include <iostream.h>#define MAX 1000typedef struct Node *TREE;struct Node{    int key;    TREE p, left, right;};TREE T; void khoitao (TREE &T){    T = NULL;}//////////////////////////////////duyet cay theo thu tu giuavoid INORDER_TREE_WALK (TREE &T){    if (T != NULL)    {        INORDER_TREE_WALK (T ->left);        cout << T ->key;        INORDER_TREE_WALK (T ->right);    }} TREE TREE_SEARCH (TREE &T, int k){    if (T != NULL || k == T ->key)          return T;    if (k < T ->key)        return TREE_SEARCH (T ->left, k);    else        return TREE_SEARCH (T ->right, k);} TREE TREE_MINIMUM (TREE &T){    while (T ->left != NULL)        T = T ->left;    return T;} TREE TREE_MAXIMUM (TREE &T){    while (T ->right != NULL)        T = T ->right;    return T;} TREE TREE_SUCCESSOR (TREE &T){    if (T ->right != NULL)        return TREE_MINIMUM (T ->right);    TREE y = T ->p;    while (y != NULL && T == y ->right)    {        T = y;        y = y ->p;    }    return y;} TREE TREE_PREDECESSOR (TREE &T){    if (T ->left != NULL)        return TREE_MAXIMUM (T ->left);    TREE y = T ->p;    while (y != NULL && T == y ->left)    {        T = y;        y = y ->p;    }    return y;} void TREE_INSERT (TREE &T, TREE z){    TREE y = NULL;    TREE x = T;    while (x != NULL)    {        y = x;        if (z ->key < x ->key)            x = x ->left;        else            x = x ->right;    }    z ->p = y;    if (y == NULL)        T = z;    else if (z ->key < y ->key)        y ->left = z;    else        y ->right = z; } TREE TREE_DELETE (TREE &T, TREE z){    TREE y, x, r;    if (z ->left == NULL || z ->right == NULL)        y = z;    else        y = TREE_SUCCESSOR (z);     if (y ->left != NULL)        x = y ->left;    else        x = y ->right;     if (x != NULL)        x ->p = y ->p;     r = y ->p;    if (y ->p == NULL)        T = x;    else if (y = r ->left)        r ->left = x;    else         r ->right = x;     if (y != x)        z ->key = y ->key;    return y;} void duyetcay(TREE &T){     if(T != NULL)    {        cout << T ->key << endl;        duyetcay (T ->left);        duyetcay (T ->right);       }} void main (){    int k, delk;    TREE T, z;    khoitao (T);    do    {        cout << "Nhap vao khoa cua cay nhi phan (-1 de ket thuc): ";        cin >> k;        z = new (Node);        z ->key = k;        z ->left = NULL;        z ->right = NULL;        z ->p = NULL;        if (z ->key > 0)            TREE_INSERT (T, z);    }    while (z ->key > 0);    duyetcay (T);        cout << "Nhap vao khoa can xoa: ";    cin >> delk;             // đến đây mình không biết gọi hàm xóa như thế nào?    duyetcay (T); }

[Lugiavn]

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.

[QuangHoang]

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ì.

#include <iostream>using namespace std;#define MAX 1000  struct Node{    int key;    struct Node* left;    struct Node* right;//2 con tro trai phai thoi chu ban};typedef struct Node* TREE; void khoitao (TREE &root){    root = NULL;}//////////////////////////////////duyet cay theo thu tu giuavoid INORDER_TREE_WALK(TREE &root) //goi la Left-Node-Right{    if (root != NULL)    {        INORDER_TREE_WALK (root->left);        cout << root->key << "   ";        INORDER_TREE_WALK (root->right);    }} bool TREE_SEARCH (TREE &T, int k)         /////////Sua ham nay chut, co the tra ve kieu int cung ok{    if (T==NULL) return false;    else if (k == T ->key)        return true;    else if (k < T ->key)        return TREE_SEARCH (T ->left, k);    else        return TREE_SEARCH (T ->right, k);} /*TREE TREE_MINIMUM (TREE &T)   //// 2 ham max min nay minh chang biet dung de lam gi{    while (T ->left != NULL)        T = T ->left;    return T;} TREE TREE_MAXIMUM (TREE &T){    while (T ->right != NULL)        T = T ->right;    return T;} TREE TREE_SUCCESSOR (TREE &T) //Vi luc dau hieu sai van de nen ham nay khong chinh xac roi{                                   //Ham nay de lam gi the, minh se sua them khi hieu y dinh cua ham    if (T ->right != NULL)        return TREE_MINIMUM (T ->right);    TREE y = T;          //////////////    while (y != NULL && T == y ->right)    {        T = y;        y = y ->p;    }    return y;} TREE TREE_PREDECESSOR (TREE &T) /////////cung vay, khong hieu de lam gi{    if (T ->left != NULL)        return TREE_MAXIMUM (T ->left);    TREE y = T ->p;    while (y != NULL && T == y ->left)    {        T = y;        y = y ->p;    }    return y;}*/ void TREE_ADDNODE (TREE &T, TREE z)//add node to tree{    TREE p=T;    if (p==NULL) p=z;    else if(p ->key > z->key) TREE_INSERT (p->left,z);    else TREE_INSERT (p->right,z);    } /*TREE TREE_DELETE (TREE &T, TREE z){    TREE y, x, r;    if (z ->left == NULL || z ->right == NULL)        y = z;    else        y = TREE_SUCCESSOR (z);     if (y ->left != NULL)        x = y ->left;    else        x = y ->right;     if (x != NULL)        x ->p = y ->p;     r = y ->p;    if (y ->p == NULL)        T = x;    else if (y = r ->left)        r ->left = x;    else        r ->right = x;     if (y != x)        z ->key = y ->key;    return y;} void PREORDER_TREE(TREE &T)  // nhu ham inorder thui, day la ham duyet cay: Node-Left-Right{     if(T != NULL)    {        cout << T ->key << endl;        PREORDER_TREE(T ->left);        PREORDER_TREE(T ->right);    }} /*void main (){    int k, delk;    TREE T, z;    khoitao (T);    do    {        cout << "Nhap vao khoa cua cay nhi phan (-1 de ket thuc): ";        cin >> k;        z = new (Node);        z ->key = k;        z ->left = NULL;        z ->right = NULL;        z ->p = NULL;        if (z ->key > 0)            TREE_INSERT (T, z);    }    while (z ->key > 0);    PREORDER_TREE(T);     cout << "Nhap vao khoa can xoa: ";    cin >> delk;             // đến đây mình không biết gọi hàm xóa như thế nào?    PREORDER_TREE(T); }*/

Hope this help!

[giang222]

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!