Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 28 kết quả

Đề tài: Phân biệt các cây Nhị phân như thế nào?

  1. #1
    Ngày gia nhập
    02 2007
    Bài viết
    27

    Mặc định Phân biệt các cây Nhị phân như thế nào?

    Em mới học CTDL và đang rối rắm với các loại cây, mong các huynh xem giúp em hiểu thế này có đúng không:
    1. Cây nhị phân bình thường: thao tác thoải mái, có thể bị lệch
    2. Cây nhị phân cân bằng:
    __a. Khi xóa một node bất kỳ: phải tìm một node lá thế mạng, hoán đổi vị trí 2 node rồi tiến hành xóa.
    __b. Thêm node: tự tìm một vị trí thích hợp để thêm vào.
    __c. Cân bằng cây: bằng cách nào nhỉ?
    3. Cây nhị phân tìm kiếm:
    __a. Xóa ??
    __b. Thêm ??
    __c. Cân bằng ??

    Có một vài chỗ em không biết, mong cách huynh chỉ giúp, bằng mã giả cũng được. Em sắp phải thi rồi, đang cần gấp. Thanks


    Tucõi phước
    Tìnhdây oan

  2. #2
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Tui nghĩ như vầy:

    1. Cây nhị phân bình thường: thao tác thoải mái, có thể bị lệch

    2. Cây nhị phân tìm kiếm: là 1 trường hợp đặc biệt của cây nhị phân (giá trị con trái < nút < giá trị con phải)
    Bạn tìm trên mạng với từ khóa "binary search tree"

    3. Cây nhị phân cân bằng: là 1 trường hợp đặc biệt của cây nhị phân tìm kiếm (chênh lệch về chiều cao giữa con trái và con phải không quá 1)
    Bạn tìm trên mạng vói từ khóa "AVL tree"

    (hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

    -thân
    Đã được chỉnh sửa lần cuối bởi bete : 04-01-2008 lúc 01:37 AM.

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    1

    em cũng đang học CTDL.Em nhờ mấy a chỉ giúp em cây Human thế nào zậy?
    Em chân thành cảm ơn mấy anh!!!!!!!!!!!!!!!!

  4. #4
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Cây nhị phân: là cây mà mỗi nút có tối đa 2 cây con
    Cây nhị phân tìm kiếm : là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn tất cả các nút thuộc cây con phải.
    Cây nhị phân tìm kiếm cân bằng : là cây mà tại mỗi nút của nó độ cao của cây con trái và cây con phải chênh lệch không quá một
    Cây nhị phân cân bằng hoàn toàn : là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch không quá một với số nút của cây con phải ( AVL TREE)

  5. #5
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Mặc định Cấu trúc dữ liệu và phương pháp duyệt của cây nhị phân

    Cấu trúc dữ liệu của cây nhị phân

    C Code:
    1. struct node
    2. {
    3.       KDL info; // KDL kiểu dữ liệu có thể là int, char ...
    4.       struct node *pLeft;
    5.       struct node *pRight;
    6. };
    7. typedef struct node NODE;
    8. typedef NODE *TREE;

    ví dụ:
    1. khia báo cấu trúc dữ liệu cho cây nhị phân các số nguyên

    C Code:
    1. struct node
    2. {
    3.       int info;
    4.       struct node *pLeft;
    5.       struct node *pRight;
    6. };
    7. typedef struct node NODE;
    8. typedef NODE *TREE;

    2. khai báo CTDL cho CNP các phân số

    C Code:
    1. struct phanso
    2. {
    3.       int tu;
    4.       int mau;
    5. };
    6. typedef struct phanso PHANSO;
    C Code:
    1. struct node
    2. {
    3.       PHANSO info;
    4.       struct node *pLeft;
    5.       struct node *pRight;
    6. };
    7. typedef struct node NODE;
    8. typedef NODE *TREE;

    Duyệt cây nhị phân: là thăm qua tất cả các phần tử trong cây mỗi phần tử một lần

    1.Phương pháp Left Node Right:(thứ tự giữa)

    C Code:
    1. void LNR(TREE t)
    2. {
    3.     if(t == NULL)
    4.         return;
    5.     LNR(t->pLeft);
    6.     < xử lý t >;
    7.     LNR(t->pRight);
    8. }

    2.Phương pháp Right Node Left:

    C Code:
    1. void RNL(TREE t)
    2. {
    3.     if(t == NULL)
    4.         return;
    5.     RNL(t->pRight);
    6.         < xử lý t >;
    7.     RNL(t->pLeft);
    8. }

    3.Phương pháp Node Left Right:(thứ tự trước )

    C Code:
    1. void NLR(TREE t)
    2. {
    3.     if(t == NULL)
    4.         return;
    5.     < xử lý t >;
    6.         NLR(t->pLeft);
    7.     NLR(t->pRight);
    8. }

    4.Phương pháp Node Right Left :

    C Code:
    1. void NRL(TREE t)
    2. {
    3.     if(t == NULL)
    4.         return;
    5.     < xử lý t >;
    6.         NRL(t->pRight);
    7.     NRL(t->pLeft);
    8. }

    5.Phương pháp Right Left Node :

    C Code:
    1. void RLN(TREE t)
    2. {
    3.     if(t == NULL)
    4.         return;
    5.         RLN(t->pRight);
    6.     RLN(t->pLeft);
    7.         < xử lý t >;
    8. }

    6.Phương pháp Left Right Node :(thứ tự sau)

    C Code:
    1. void RLN(TREE t)
    2. {
    3.     if(t == NULL)
    4.         return;
    5.         RLN(t->pLeft);
    6.     RLN(t->pRight);
    7.         < xử lý t >;
    8. }

  6. #6
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Mặc định Phân biệt các cây Nhị phân như thế nào?

    Ví dụ phương pháp duyệt cây:

    Bài 1: Hãy định nghĩa hàm xuất cây nhị phân các số nguyên theo phương pháp Left Node Right

    C Code:
    1. void xuat(TREE T)
    2. {
    3.     if(t==NULL)
    4.         return;
    5.     xuat(T->pLeft);
    6.     printf("%4d",T->info);
    7.     xuat(T->pRight);
    8. }
    Bài 2: Viết hàm xuất các giá trị chẵn trong cây

    C Code:
    1. void xuatchan(TREE T)
    2. {
    3.     if(t==NULL)
    4.         return;
    5.     xuat(T->pLeft);
    6.     if(T->info %2==0)
    7.         printf("%4d",T->info);
    8.     xuat(T->pRight);
    9. }
    Bài 3: Định nghĩa hàm đếm số lượng node có trong cây

    C Code:
    1. int DemNode(TREE T)
    2. {
    3.     if(t==NULL)
    4.         return;
    5.     int x = DemNode(T->pLeft);
    6.     int y = DemNode(T->pRight);
    7.     return (x+y+1);
    8. }

    Bài 4: Viết hàm tính chiều cao cây
    C Code:
    1. int ChieuCao(TREE T)
    2. {
    3.     if(!t)
    4.         return 0;
    5.     int a = ChieuCao(T->pLeft);
    6.     int b = ChieuCao(T->pRight);
    7.     if(a>b)
    8.         return (a+1);
    9.     return (b+1);
    10. }
    Bài 5: Xuất tất cả các nút trên tầng thứ k của cây
    Ghi chú: các tầng trong cây được đánh chỉ số bắt đầu từ 0. Nếu một cây có chiều cao h thì các tầng trong cây được đánh chỉ số từ 0 đến h-1
    Nhận xét: Một nút nằm ở tầng thứ k của cây thì nó sẽ nằm ở tầng thứ k- 1 của cây con trái hoặc ở tầng thứ k-1 của cây con phải (k>0)

    C Code:
    1. void intangk(TREE t, int k)
    2. {
    3.     if(!t)
    4.         return;
    5.     if(k==0)
    6.     {
    7.         printf("%4d",t->info);
    8.         return;
    9.     }
    10.  
    11.     intangk(t->pLeft,k-1);
    12.     intangk(t->pRight,k-1);
    13. }

  7. #7
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Mặc định Bài tập làm thêm về cây nhị phân tìm kiếm

    nếu có thời gian các bạn hãy làm thử các bài tập này.

    Kỹ thuật nhập, xuất liệt kê.
    Bài 1: Viết hàm xuất các số hoàn thiện trong cây
    Bài 2: Viết hàm xuất tất cả các nút trên cây theo thứ tự từ tầng 0 --> h-1 của cây

    Kỹ thuật đếm.
    Bài 3: Đếm số lượng nút có đúng một con
    Bài 4: Đếm số lượng nút lá mà thông tin tại đó là giá trị chẵn.
    Bài 5: Đếm số lượng nút trên tầng thứ k của cây
    Bài 6: Đếm số lượng nút trên tầng cao hơn tầng thứ k của cây

    Kỹ thuật tính toán
    Bài 7: Tính tổng các nút trong cây
    Bài 8: Tính tổng các nút lẻ trong cây
    Bài 9: Tính tổng các nút mà thông tin tại đó là giá trị chẵn

    Kỹ thuật đặt cờ hiệu
    Bài 10: Kiểm tra cây nhị phân T có phải là cây nhị phân tìm kiếm không
    Bài 11: Kiểm tra cây nhị phân T có phải là cây nhị phân cân bằng không
    Bài 10: Kiểm tra cây nhị phân T có phải là cây cân bằng hoàn toàn không
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 05-03-2008 lúc 09:27 PM.

  8. #8
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Mặc định Tìm Một phần tử có khóa x trong cây

    C Code:
    1. NODE* SearchNode(TREE T, Data x)
    2. {
    3.     if(!T)
    4.         return NULL;
    5.     if(T->info == x)
    6.         return T;
    7.     if(T->info > x)
    8.         return SearchNode(T->pLeft,x);
    9.     return SearchNode(T->pRight,x);
    10. }
    11.  
    12. Ta có thể xây dựng một hàm tìm kiếm tương đương khong đệ quy như sau
    13.  
    14. NODE* SearchNode(TREE T, Data x)
    15. {
    16.     NODE *p = T;
    17.     while(!p)
    18.     {
    19.         if(p->info == x)
    20.             return p;
    21.         else
    22.         {
    23.             if(p->info > x)
    24.                 p = p->pLeft;
    25.             else
    26.                 p = p->pRight;
    27.         }
    28.     }
    29.     return NULL;
    30. }
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 05-03-2008 lúc 08:13 PM.

  9. #9
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Red face Tìm một phần tử có khóa x trong cây

    Ví dụ 1: cho cây NP khác rỗng . Hãy viết hàm tìm giá trị lớn nhất trong cây NP các số nguyên

    C Code:
    1. int lonnhat(TREE t)
    2. {
    3.     if(t->pLeft == NULL && t->pRight == NULL)
    4.         return t->info;
    5.     int left = lonnhat(t->pLeft);
    6.     int right = lonnhat(t->pRight);
    7.     int ln = t->info;
    8.     if(left>ln)
    9.         ln = left;
    10.     if(right <ln)
    11.         ln = right;
    12.     return ln;
    13. }
    Ví dụ 2: Cho CNP T các số thực hãy viết hàm kiểm tra trong cây có tồn tại giá trị 0 hay không ?

    C Code:
    1. int kiemtra(TREE t)
    2. {
    3.     if(!t)
    4.         return 0;
    5.     if(kiemtra(t->pLeft == 1)
    6.         return 1;
    7.     if(kiemtra(t->pRight == 1)
    8.         return 1;
    9.     if(t->info == 0)
    10.         return 1;
    11.     return 0;
    12. }
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 05-03-2008 lúc 08:10 PM.

  10. #10
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Thumbs up Thêm một phần tử x vào cây

    Việc thêm một phần tử x vào cây phải đảm bảo điều kiện ràng buộc CNPTK. Ta có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ tiện lợi nhất do ta có thể thực hiện quá trình tương tự thao tác tìm kiếm . Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm.

    Theo cách mà mình đã được học thì cần một hàm trung gian được đặt tên là getnode. Hàm này có nhiệm vụ khởi tạo một node mới có khóa là x
    C++ Code:
    1. NODE *GetNode(KDL x)
    2. {
    3.     NODE *n= new NODE;
    4.     if(n)
    5.     {
    6.         n->info=x;
    7.         n->pLeft=n->pRight=NULL;
    8.         return n;
    9.     }
    10.     return NULL;
    11. }
    12.  
    13. void addnode(TREE &t, KDL x)
    14. {
    15.     if(!t)
    16.     {
    17.         t=GetNode(x);
    18.         return;
    19.     }
    20.     if(t->info==x)
    21.         return;
    22.     if(x>t->info)
    23.         addnode(t->pRight,x);
    24.     else
    25.         addnode(t->pLeft,x);
    26. }

    Tạo một cây NPTK: ta có thể tạo một cây nhị phân tìm kiếm bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 06-03-2008 lúc 09:27 AM.

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