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ố 18 kết quả

Đề tài: cây nhị phân

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

    Mặc định cây nhị phân

    các bạn cho mình hỏi về thuật toán:
    a) kiểm tra 2 cây nhị phân giống nhau k?( giống cả về giá trị luôn)
    b) kiểm tra 2 cây nhị phân coi giống nhau về hình dáng k?

    và cách để duyệt 2 cây nhị phân cùng 1 lúc.

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

    a) kiểm tra 2 cây nhị phân giống nhau k?( giống cả về giá trị luôn)
    Bạn duyệt cây theo một thứ tự nào đó rồi so sánh từng giá trị
    C Code:
    1. int Preorder(ptree tree1, ptree tree2)
    2. {
    3.      if (tree1->data != tree2->data) return 0;
    4.      Preorder(tree1->left,tree2->left);
    5.      Preorder(tree1->right,tree2->right);
    6.      return 1;
    7. }
    Chắc như vậy là được, mình chưa test thử.

    b) kiểm tra 2 cây nhị phân coi giống nhau về hình dáng k?
    Cái này có vẻ khó, trong mỗi node của cây cần có thêm 1 biến để đánh số cho node.

    Thực hiện duyệt một lúc 2 cây để đánh số rồi duyện lại kiểu khác để kt, vd:

    C Code:
    1. void Inorder(ptree tree1, ptree tree2,  int i)
    2. {
    3.      Inorder(tree1->left,tree2->left,i+1);
    4.      tree1->data = tree2 -> data=i;
    5.      Inorder(tree1->right,tree2->right,i+1);
    6. }
    7. int Preorder(ptree tree1, ptree tree2)
    8. {
    9.      if (tree1->data != tree2->data) return 0;
    10.      Preorder(tree1->left,tree2->left);
    11.      Preorder(tree1->right,tree2->right);
    12.      return 1;
    13. }

    Ý tưởng như vậy chứ code thì chưa chính xác!

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

    Mình nghĩ bạn mod thiếu sót trường hợp rồi, coi chừng báo lỗi tham chiếu treo!
    Code:
    int Preorder(ptree *tree1, ptree *tree2)
    {
         if (*tree1!= *tree2) return 0;
         Preorder(tree1->left,tree2->left);
         Preorder(tree1->right,tree2->right);
         return 1;
    }
    Mình nghĩ vầy đúng hơn

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

    Mình nghĩ bạn mod thiếu sót trường hợp rồi, coi chừng báo lỗi tham chiếu treo!
    Ah, code chỉ mang tính demo, ptree ở đây là pointer tree và so sánh là tree->data

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

    mình là wawa, mình đã thử theo cách của bạn nhưng vẫn chưa được

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

    Mặc định cây nhị phân

    Có thể đưa code của bạn lên đây được không, khi mình code chưa test. Đưa code lên test cho nhanh chứ viết test nguyên bài thì lâu lém.

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

    PHP Code:
    #include <stdio.h>
    #include <conio.h>
    typedef int elem;
    typedef struct nodet {
                
    elem data;
                
    struct nodet *left, *right;
            } 
    node;
    typedef node *tree;

    //////////////// Dem so nut tren cay
    int sonut(tree t)
    {
        if (
    t==NULL) return 0;
        return 
    1+sonut(t->left)+sonut(t->right);
    }

    //////////////// Dem so nut la tren cay
    int sonutla(tree t)
    {
        if (
    t==NULL) return 0;
        if (
    t->left==NULL && t->right==NULL)
            return 
    1;
        return 
    sonutla(t->left)+sonutla(t->right);
    }

    //////////////// Dem so nut trong tren cay
    int sonuttrg(tree t)
    {
        if (
    t==NULL) return 0;
        if (
    t->left==NULL && t->right==NULL)
            return 
    0;
        return 
    1+sonuttrg(t->left)+sonuttrg(t->right);
    }

    //////////////// Tong gia tri tren cay
    int tong(tree t)
    {
        if (
    t==NULL) return 0;
        return 
    t->data tong(t->left)+tong(t->right);
    }
    int max(int aint b)
    {
        return (
    a>b?a:b);
    }

    //////////////// Do cao cay
    int h(tree t)
    {
        if (
    t==NULL) return 0;
        return 
    max(h(t->left), h(t->right));
    }


    //////////////// Insert BST
    void insertBST(tree &t,elem x)
    {
        if(
    t==NULL)
        {
            
    = new node;
            
    t->data x;
            
    t->left t->right NULL;
        }
        else
        {
            if(
    xt->data)
                
    insertBST(t->left,x);
            else
                
    insertBST(t->right,x);
        }
    }

    ///////////////nhap BST
    void nhapBST(tree &t)
    {
        
    elem x;
        
    NULL;
        do
        {
            
    scanf("%d",&x);
            if(
    x>0)
                
    insertBST(t,x);
        }while(
    x>0);

    }

    ///////////////// ham in nut la
    void inla(tree t,int k)
    {
        if(!
    t)
            return;
        if(
    k==0)
        {
            
    printf("3%d",t->data);
            return;
        }
        
    inla(t->left,k-1);
        
    inla(t->right,k-1);

    }

    //////////////// In cay
    void incay(tree tint m=1)
    {
        if (
    t!=NULL)
        {
            
    incay(t->leftm+1);
            
    printf("\n");
            for (
    int i=0i<mi++)
                
    printf("    ");
            
    printf("%4d"t->data);
            
    incay(t->rightm+1);
        }
    }

    //////////////// Xoa cay
    void xoacay(tree &t)
    {
        if (
    t!=NULL)
        {
            
    xoacay(t->left);
            
    xoacay(t->right);
            
    delete t;
            
    NULL;
        }
    }



    /////////////// duyet kiem tra giong nhau
    int LNR_giong(tree t1,tree t2)
    {
        
    int count1 =1;
        if(
    t1==NULL && t2==NULL)
            return 
    1;
        else    if((
    t1==NULL && t2!=NULL)||(t1!=NULL && t2==NULL))
                      return 
    0;
        else
        {
            
    LNR_giong(t1->left,t2->left);
            if(
    t1->data != t2->data)
            
    count1++;
            
    LNR_giong(t1->right,t2->right);
        }
        return 
    count1;

    }

    ///////////////kiem tra
    void kiemtra(tree t1,tree t2)
    {
        if(
    LNR_giong(t1,t2)>1)
            
    printf("\n 2 cay khac nhau\n");
        
    printf("\n2 cay giong nhau\n");
    }
    void main()
    {    
        
    tree t1,t2;
        
        
    nhapBST(t1);
        
    incay(t1,5);
        
    printf("\n\n");

        
    nhapBST(t2);
        
    incay(t2,5);
        
    printf("\n\n");
        
        
    printf("\nkiem tra 2 cay\n");
        
    kiemtra(t1,t2);

    bạn kiểm tra dùm mình, vì mình làm mà vẫn vướng 1 số lỗi, mình mới làm kiểm tra giống , còn cái hình dáng thì chưa làm. nhân tiện bạn cho mình hỏi cách để nhận biết được nút lá nào là nút lá ở mức thấp nhất.

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

    PHP Code:
    //////////////// In cay
    void incay(tree tint m=1)
    {
        if (
    t!=NULL)
        {
            
    incay(t->rightm+1); // left
            
    printf("\n");
            for (
    int i=0i<mi++)
                
    printf("    ");
            
    printf("%4d"t->data);
            
    incay(t->leftm+1); //right
        
    }

    chỗ hàm incay bạn sửa lại cho mình như ở dưới để dễ nhìn hơn xíu :P

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

    Tớ đã thử kiểm tra 2 cây giống nhau, cậu thử test lại coi, còn phần kia cũng tương tự, code ở trên của tớ, thêm chút đk.

    Còn hàm tính chiều cao của cậy, có chút vấn đề đó. Chẳng biết có tính được kết quả không nữa.

    C Code:
    1. #include <stdio.h>
    2. //#include <conio.h>
    3.  
    4.  
    5. struct node {
    6.             int data;
    7.             struct node *left, *right;
    8.         };
    9. typedef struct node* tree;
    10.  
    11. //////////////// Dem so nut tren cay
    12. int sonut(tree t)
    13. {
    14.     if (t==NULL) return 0;
    15.     return 1+sonut(t->left)+sonut(t->right);
    16. }
    17.  
    18. //////////////// Dem so nut la tren cay
    19. int sonutla(tree t)
    20. {
    21.     if (t==NULL) return 0;
    22.     if (t->left==NULL && t->right==NULL)
    23.         return 1;
    24.     return sonutla(t->left)+sonutla(t->right);
    25. }
    26.  
    27. //////////////// Dem so nut trong tren cay
    28. int sonuttrg(tree t)
    29. {
    30.     if (t==NULL) return 0;
    31.     if (t->left==NULL && t->right==NULL)
    32.         return 0;
    33.     return 1+sonuttrg(t->left)+sonuttrg(t->right);
    34. }
    35.  
    36. //////////////// Tong gia tri tren cay
    37. int tong(tree t)
    38. {
    39.     if (t==NULL) return 0;
    40.     return t->data + tong(t->left) + tong(t->right);
    41. }
    42.  
    43. int max(int a, int b)
    44. {
    45.     return (a>b?a:b);
    46. }
    47.  
    48. //////////////// Do cao cay
    49. int h(tree t)                       ///??????????
    50. {
    51.     if (t==NULL) return 0;
    52.     return 1 + max(h(t->left), h(t->right));
    53. }
    54.  
    55. //////////////// Insert BST
    56. void insertBST(tree &t,int x)
    57. {
    58.     if(t==NULL)
    59.     {
    60.         t = new struct node;
    61.         t->data = x;
    62.         t->left = t->right = NULL;
    63.     }
    64.     else
    65.     {
    66.         if(x < t->data)
    67.             insertBST(t->left,x);
    68.         else
    69.             insertBST(t->right,x);
    70.     }
    71. }
    72.  
    73. ///////////////nhap BST
    74. void nhapBST(tree &t)
    75. {
    76.     int x;
    77.     t = NULL;
    78.     do
    79.     {
    80.         scanf("%d",&x);
    81.         if(x>0)
    82.             insertBST(t,x);
    83.     }while(x>0);
    84.  
    85. }
    86.  
    87. ///////////////// ham in nut la
    88. void inla(tree t,int k)
    89. {
    90.     if(!t)
    91.         return;
    92.     if(k==0)
    93.     {
    94.         printf("3%d",t->data);
    95.         return;
    96.     }
    97.     inla(t->left,k-1);
    98.     inla(t->right,k-1);
    99.  
    100. }
    101.  
    102. //////////////// In cay
    103. void incay(tree t, int m=1)
    104. {
    105.     if (t!=NULL)
    106.     {
    107.         incay(t->right, m+1); // left
    108.         printf("\n");
    109.         for (int i=0; i<m; i++)
    110.             printf("    ");
    111.         printf("%4d", t->data);
    112.         incay(t->left, m+1); //right
    113.     }
    114. }
    115.  
    116. //////////////// Xoa cay
    117. void xoacay(tree &t)
    118. {
    119.     if (t!=NULL)
    120.     {
    121.         xoacay(t->left);
    122.         xoacay(t->right);
    123.         delete t;
    124.         t = NULL;
    125.     }
    126. }
    127.  
    128. //Kt 2 cay giong nhau
    129. int Preorder(tree t1, tree t2)
    130. {
    131.      if (t1!=NULL && t2!=NULL)
    132.      {
    133.      if (t1->data != t2->data) return 0;
    134.      Preorder(t1->left,t2->left);
    135.      Preorder(t1->right,t2->right);
    136.      }
    137.      return 1;
    138. }
    139.  
    140. int main()
    141. {
    142.     tree t1,t2;
    143.  
    144.     nhapBST(t1);
    145.     incay(t1,5);
    146.     printf("\n\n");
    147.  
    148.     nhapBST(t2);
    149.     incay(t2,5);
    150.     printf("\n\n");
    151.  
    152.     printf("\nkiem tra 2 cay\n");
    153.     if (Preorder(t1,t2)) printf("OK");
    154.     else printf("not OK");
    155.     //kiemtra(t1,t2);
    156. }

  10. #10
    Ngày gia nhập
    12 2007
    Bài viết
    5

    Không biết các bác đã test hay chưa, tình hình chung khi em test là thấy chưa đúng, nghiềm ngẫm lại thui.

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