Đánh giá, nhận xét, review các công ty tuyển dụng
Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Một số thao tác mở rộng về cây nhị phân tìm kiếm

  1. #1
    Ngày gia nhập
    05 2010
    Bài viết
    265

    Mặc định Một số thao tác mở rộng về cây nhị phân tìm kiếm

    Mình có đoạn code về xác định số nút của toàn bộ cây nhị phân, số nút từ đỉnh (mức 1) đến mức k, số nút tại đúng mức k, số nút từ mức k đến hết. Mong các bạn góp ý nha, cám ơn nhiều.
    C Code:
    1. #include <stdio.h>
    2.  
    3. struct node
    4. {
    5.     int x;
    6.     node *left, *right;
    7.     node(int _x = 0){x = _x; left = right = NULL;}
    8. };
    9.  
    10. typedef node * pnode;
    11.  
    12. void insert(pnode &p,int value)
    13. {
    14.     if (p == NULL) p = new node(value);
    15.     else
    16.         if (p->x > value) insert(p->left,value);
    17.         else if (p->x < value)insert(p->right,value);
    18. }
    19.  
    20. void create(pnode &p,int a[], int n)
    21. {
    22.     p = NULL;
    23.     for (int k = 0; k < n; k++)
    24.         insert(p,a[k]);
    25. }
    26.  
    27. void inorder(pnode p)
    28. {
    29.     if (p != NULL)
    30.     {
    31.         inorder(p->left);
    32.         printf("%4d",p->x);
    33.         inorder(p->right);
    34.     }
    35. }
    36.  
    37. void remove(pnode &p)
    38. {
    39.     if (p != NULL)
    40.     {
    41.         remove(p->left);
    42.         remove(p->right);
    43.         delete p;
    44.     }
    45. }
    46.  
    47. int countall(pnode p) // Tỉnh tổng số nút trên cây
    48. {
    49.     if (p == NULL) return 0;
    50.     return 1 +countall(p->left)+ countall(p->right);
    51. }
    52.  
    53. int countup(pnode p, int depth) // Tỉnh tổng số nút từ mức depth ngược về gốc
    54. {
    55.     if (p == NULL || depth==0) return 0;
    56.     return 1 + countup(p->left, depth-1)+ countup(p->right, depth-1);
    57. }
    58.  
    59. int countdown(pnode p, int level) // Tỉnh tổng số nút từ mức level đến hết
    60. {
    61.     return countall(p)- countup(p, level-1);
    62. }
    63.  
    64. int count(pnode p, int level)// // Tỉnh tổng số nút có mức level
    65. {
    66.     if (p == NULL || level == 0) return 0;
    67.     if (level == 1) return 1;
    68.     return count(p->left, level-1)+ count(p->right, level-1);
    69. }
    70.  
    71. void display(int a[], int n)
    72. {
    73.     printf("\nTrinh tu cac gia tri duoc dua vao cay:\n");
    74.     for (int k=0; k < n; k++)
    75.         printf("%4d",a[k]);
    76.     printf("\n");
    77. }
    78.  
    79. void main()
    80. {
    81.     pnode p;   
    82.     int a[] = {5,8,7,4,12,16,13,15,3,18,17,19,2};
    83.     int n = sizeof(a)/sizeof(int);
    84.     display(a,n);
    85.     create(p,a,n);
    86.     printf("\nDuyet cay theo giai thuat Trai-Goc-Phai:\n");
    87.     inorder(p);printf("\n");
    88.     printf("\nToan bo cay co: %d nut\n",countall(p));
    89.     printf("\nTu goc den muc 3 co: %d nut\n",countup(p,3));
    90.     printf("\nTu muc 5 tro di co: %d nut\n",countdown(p,5));
    91.     int level = 1, sum;
    92.     while (sum = count(p, level))
    93.         printf("\nMuc %d co: %d nut\n",level++,count(p,level));
    94.     remove(p); 
    95. }
    Kết quả chạy:
    PHP Code:
    Trinh tu cac gia tri duoc dua vao cay:
       
    5   8   7   4  12  16  13  15   3  18  17  19   2

    Duyet cay theo giai thuat Trai
    -Goc-Phai:
       
    2   3   4   5   7   8  12  13  15  16  17  18  19

    Toan bo cay co
    13 nut

    Tu goc den muc 3 co
    6 nut

    Tu muc 5 tro di co
    5 nut

    Muc 1 co
    1 nut

    Muc 2 co
    2 nut

    Muc 3 co
    3 nut

    Muc 4 co
    2 nut

    Muc 5 co
    2 nut

    Muc 6 co
    3 nut 

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    205Bee
    Bài viết
    231

    Trích dẫn Nguyên bản được gửi bởi donvuon Xem bài viết
    PHP Code:
    int countup(pnode pint depth// Tỉnh tổng số nút từ mức depth ngược về gốc
    {
        if (
    == NULL || depth==0) return 0;
        return 
    countup(p->leftdepth-1)+ countup(p->rightdepth-1);

    Nếu tính số nút từ gốc đến mức depth thì mình có làm thế này nhưng không đúng. Donvuon có cách tính nào khác chỉ giáo với
    PHP Code:
    int CountUpNodePtr pRootint depthint n )
    {
        if ( 
    pRoot == NULL || == ) return 0;
        if ( 
    depth ) return CountUppRoot->pLeftdepth) + CountUppRoot->pRightdepth);


  3. #3
    Ngày gia nhập
    09 2009
    Nơi ở
    205Bee
    Bài viết
    231

    Mấy đoạn code xác định số nút hay ghê!. Nhất là đoạn xác định số nút ở mức k. Chắc phải tốt đệ quy thì mới hiểu được bài của Donvuon. Hic

  4. #4
    Ngày gia nhập
    05 2010
    Bài viết
    265

    Trích dẫn Nguyên bản được gửi bởi trihn_kt Xem bài viết
    Nếu tính số nút từ gốc đến mức depth thì mình có làm thế này nhưng không đúng. Donvuon có cách tính nào khác chỉ giáo với
    Thế này nè, chuẩn luôn. Gọi CountUp(pRoot, depth, 1) nha.

    C Code:
    1. int CountUp( NodePtr pRoot, int depth, int n = 0 )
    2. {
    3.     if ( pRoot == NULL || n == 0 ) return 0;
    4.     if ( n <= depth ) return 1 + CountUp( pRoot->pLeft, depth, n + 1 ) + CountUp( pRoot->pRight, depth, n + 1 );
    5.     else return 0;
    6. }

  5. #5
    Ngày gia nhập
    10 2009
    Nơi ở
    Close All
    Bài viết
    993

    Cây nhị phân tìm kiếm thì ngày xưa lúc mới học lập trình tớ cũng cài đặt.Share anh em koi.Lúc đó tớ gà lăm,có j anh em đừng chém nha.
    Code này là gôm chung Linked list + BST+STack+Queue
    PHP Code:

    #include<stdio.h>
    #include<conio.h>
    #include<string.h>
    #include<dir.h>
    #include<ctype.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <windows.h>
    int __FOREGROUND LIGHTGRAY;
    int __BACKGROUND BLACK;
    /////////////////////////////////////////////
    void gotoxy(int xint y) {
      
    COORD c;
      
    c.1;
      
    c.1;
      
    SetConsoleCursorPosition (GetStdHandle(STD_OUTPUT_HANDLE), c);
    }
    void clrscr() {
      
    COORD coord;
      
    DWORD written;
      
    CONSOLE_SCREEN_BUFFER_INFO info;

      
    coord.0;
      
    coord.0;
      
    GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &info);
      
    FillConsoleOutputCharacter (GetStdHandle(STD_OUTPUT_HANDLE), ' ',
        
    info.dwSize.info.dwSize.Ycoord, &written);
      
    gotoxy (11);
    }
    void textattr(int _attr) {
      
    SetConsoleTextAttribute (GetStdHandle(STD_OUTPUT_HANDLE), _attr);
    //  printf ("%d\n", text_info.screenheight);
    }

    void textbackground(int _color) {
      if (
    _color == BLINK)
         
    _color WHITE;
      
    __BACKGROUND _color;
      
    textattr (__FOREGROUND | (_color 29));
    }

    void textcolor(int _color) {
      if (
    _color == BLINK)
         
    _color WHITE;
      
    __FOREGROUND _color;
      
    textattr(_color __BACKGROUND);
    }
    ///////////////////////////////////////////////////////
    typedef struct tagTNODE 
    {
        
    int k;
        
    struct tagTNODE *pleft,*pright;
    }
    TNODE;
    typedef TNODE *TREE;
    typedef struct tagNODE
    {
        
    TNODE *info;
        
    struct tagNODE *pnext;
    }
    NODE;
    typedef struct 
    {
        
    NODE *phead;
        
    NODE *ptail;
    }LIST;

    //THAO TAC TREN DANH SACH LIEN KET
    NODE *getnode(TNODE *x)
    {
        
    NODE *p;
        
    p=new NODE;
        if(
    p==NULL)return NULL
        
    p->info=x;
        
    p->pnext=NULL;
        return 
    p;
    }
    void addtail(LIST &L,NODE *x)
    {
        if(
    L.phead==NULL)
        {
            
    L.phead=x;
            
    L.ptail=L.phead;
        }
        else
        {
            
    L.ptail->pnext=x;
            
    L.ptail=x;
            
    L.ptail->pnext=NULL;
        }
    }
    void addhead(LIST &L,NODE *x)
    {
        if(
    L.phead==NULL)
        {
            
    L.phead=x;
            
    L.ptail=L.phead;
        }
        else
        {
            
    x->pnext=L.phead;
            
    L.phead=x;
        }
    }
    void xoalist(LIST &L)
    {
        
    NODE *p;
        while(
    L.phead!=NULL)
        {
            
    p=L.phead;
            
    L.phead=p->pnext;
            
    delete p;
        }
    }
    void nhaplist(LIST &L,TREE T)
    {
        
    NODE *x;
        if(
    T)
        {
            
    x=getnode(T);
            
    addtail(L,x);
            
    nhaplist(L,T->pleft);
            
    nhaplist(L,T->pright);
            
        }
    }
    void xuat(LIST &L)
    {
        
    NODE *p;
        
    p=L.phead;
        for(
    p=L.phead;p!=NULL;p=p->pnext)
        {
            if(
    p==L.ptail)  printf("%2d",p->info->k);
            else
            
    printf("%2d ->",p->info->k);
            
        }

        
    }
    ///THAO TAC TREN CAY

    void nhapcay(TREE &T,int x)
    {
        if(
    T)
        {
            if(
    T->k==xprintf("\n   da co roi");
            if(
    T->k>x)  return nhapcay(T->pleft,x);
            if(
    T->k<x)  return nhapcay(T->pright,x);
        }
        
    =new TNODE;
        if(
    T==NULL)printf("\n thieu bo nho ");
        else{
        
    T->k=x;
        
    T->pleft=NULL;
        
    T->pright=NULL;
        }
    }
    void inNLR(TREE T)
    {
        if(
    T)
        {
            
    printf(" %d",T->k);
            
    inNLR(T->pleft);
            
    inNLR(T->pright);
        }
    }
    void inLNR(TREE T)
    {
        if(
    T)
        {
            
            
    inLNR(T->pleft);
            
    printf(" %d",T->k);
            
    inLNR(T->pright);
        }
    }
    void inLRN(TREE T)
    {
        if(
    T)
        {
            
            
    inLRN(T->pleft);
            
    inLRN(T->pright);
            
    printf(" %d",T->k);
        }
    }
    int mx(int a,int b)
    {
        if(
    a>=b) return a;
        else return 
    b;
    }
    int chieucao(TREE T)
    {
        
    int n;
        if(
    T==NULL) return 0;
        if(
    T->pleft==NULL&&T->pright==NULL)
         return 
    1;
        
    n=1+mx(chieucao(T->pleft),chieucao(T->pright));
        return 
    n;
    }
    int sonut(TREE T)
    {
        
    int n;
        if(
    T==NULL) return 0;
        if(
    T->pleft==NULL&&T->pright==NULL) return 1;
        return 
    1+sonut(T->pleft)+sonut(    T->pright);
    }
    void inmuc(TREE T,int i,int k)
    {
        
    TNODE *t;
           
    t=new TNODE;
           
    t->k=0;
           
    t->pleft=t->pright=NULL;
        LIST 
    A,B;
           
    A.phead=A.ptail=NULL;
           
    B.phead=B.ptail=NULL;
        
    NODE *x,*p;
        
    int j;
        
    x=getnode(T);
        
    addtail(A,x);
        for(
    j=1;j<i;j++)
        {
            
    p=A.phead;
            while(
    p!=NULL)
            {
                if(
    p->info->pleft==NULL)
                  
    x=getnode(t);
                else 
                  
    x=getnode(p->info->pleft);
                
    addtail(B,x);
                if(
    p->info->pright==NULL)
                  
    x=getnode(t);
                else
                  
    x=getnode(p->info->pright);
                
    addtail(B,x);
                
    p=p->pnext;
            }
            
    xoalist(A);
            
    p=B.phead;
            while(
    p!=NULL)
            {
                
    x=getnode(p->info);
                
    addtail(A,x);
                
    p=p->pnext;
            }
            
    xoalist(B);
        }
        
    p=A.phead;
        while(
    p!=NULL)
        {
            if(
    p->info->k==0)
             
    printf(" ");
            else
             
    cprintf("%3d",p->info->k);
         for(
    j=1;j<=(2*k+1);j++)
             
    printf(" ");
            
            
    p=p->pnext;
        }
    }
    void xuatcay(TREE T)
    {
        
    int i,j,h,s=1;

        if(
    T==NULLprintf("\n Cay rong.\n");
        else
        {
            
            
    h=chieucao(T);
            for(
    i=1;i<h;i++)
              
    s=s*2;
            
    s-=1;
            for(
    i=1;i<=h;i++)
            {
               for(
    j=1;j<=s;j++)
               
    printf(" ");
               if(
    i%2!=0
               {
                     
    textcolor(YELLOW);
                  
    inmuc(T,i,s);
               }
               else
               {
                     
    textcolor(11);
                  
    inmuc(T,i,s);
               }
               
    printf("\n");
               
    s=s/2;
               
    textcolor(WHITE);
             }
        }
    }
    TNODE *timnut(TREE T,int x)
    {
        
    TNODE *p=T;
        while(
    p!=NULL)
        {
            if(
    x==p->k) return p;
            else
            {
                if(
    x<p->kp=p->pleft;
                else 
    p=p->pright;
            }
        }
        return 
    NULL;

            
    }
    int ktnt(int x)
    {
     
    int i=2;
     if(
    x==1||x==2||x==0)
     { 
        return 
    0;
     }
     else
     {
         
        while(
    i<x&&(x%i)!=0)
        {
           
    i++;     
        }
        if(
    i==x) return 1;
        if(
    i!=x) return 0;
     }
    }

    int demnt(TREE &T)
     {
         
    int n;
       if(
    T==NULL) return 0;
       if(
    ktnt(T->k)==1)
       {
            
    n=1+demnt(T->pleft)+demnt(T->pright);
       }
       if(
    ktnt(T->k)==0)
       {
               
    n=demnt(T->pleft)+demnt(T->pright);
       }
        
        return 
    n;
     }
    int timduong(TREE T,int x)
    {
        
    int n;
        
    n=1;
        while(
    T!=NULL)
        {
            if(
    T->k==x) return n;
            else
            {
                if(
    T->k>x)
                {
                    
    n=n+1;
                   
    T=T->pleft;
                }
                else
                {
                    
    n=n+1;
                   
    T=T->pright;
                }
            }
        }
        return 
    0;
    }
    void sosanh(TREE T,int x,int y)
    {
        if(
    timduong(T,x)!=0&&timduong(T,y)!=0)
        {
            if(
    timduong(T,x)==timduong(T,y))
                 
    printf("\n 2 nut cung muc %d.",timduong(T,x));
            else
                 
    printf("\n 2 nut khac muc.");
        }
        if(
    timduong(T,x)==0||timduong(T,y)==0)
            
    printf("\n gia tri nhap khong hop le.");
    }
    TNODE *timnutcha(TREE T,int x)
    {
        
    TNODE *t;
        
    t=timnut(T,x);
        if(
    t==NULL) return NULL;
        if(
    t!=NULL)
        {
           if(
    T->k==x) return NULL;
           else
           {
                 while(
    T!=NULL)
                 {
                     if(
    T->pleft==t||T->pright==t) return T;
                     else
                     {
                         if(
    T->k>xT=T->pleft;
                         else 
    T=T->pright;
                     }
                 }
           }
        }
    }
    void sua(TREE &T,int n ,int x)
    {
        
    TNODE *t,*c;
        if(
    T==NULLprintf("\n Cay rong.");
        else
        {
            
    t=timnut(T,n);
            if(
    t!=NULL)
            {
                
    c=timnutcha(T,n);
                if(
    c!=NULL)
                {
                    if(
    c->pleft==t)
                    {
                        if(
    x>=c->kprintf("\n Ko sua duoc.");
                        if(
    x<c->k)
                        {
                            if(
    t->pleft==NULL)
                            {
                                if(
    x<t->pright->kt->k=x
                                else 
    printf("\n oklh sua duoc.");
                            }
                            if(
    t->pright==NULL)
                            {
                                if(
    x>t->pleft->kt->k=x
                                else 
    printf("\n kok sua duoc.");
                            }
                            if(
    t->pleft!=NULL&&t->pright!=NULL)
                            {
                                if(
    x>t->pleft->k&&x<t->pright->k)  t->k=x;
                                else 
    printf("\n ko sua duoc.");
                            }
                            if(
    t->pleft==NULL&&t->pright==NULLt->k=x;
                        }
                    }
                    if(
    c->pright==t)
                    {
                        if(
    x<=c->kprintf("\n ko sua duoc.");
                        if(
    x>c->k)
                        {
                            if(
    t->pleft==NULL)
                            {
                                if(
    x<t->pright->kt->k=x
                                else 
    printf("\n oasd sua duoc.");
                            }
                            if(
    t->pright==NULL)
                            {
                                if(
    x>t->pleft->kt->k=x
                                else 
    printf("\n kok sua duoc.");
                            }
                            if(
    t->pleft!=NULL&&t->pright!=NULL)
                            {
                                if(
    x>t->pleft->k&&x<t->pright->k)  t->k=x;
                                else 
    printf("\n ko sua duoc.");
                            }
                            if(
    t->pleft==NULL&&t->pright==NULLt->k=x;
                        }
                    }
                }
                if(
    c==NULL)
                {
                            if(
    T->pleft==NULL)
                            {
                                if(
    x<T->pright->kT->k=x
                                else 
    printf("\n ko sua duoc.");
                            }
                            if(
    T->pright==NULL)
                            {
                                if(
    x>T->pleft->kT->k=x
                                else 
    printf("\n oqwe sua duoc.");
                            }
                            if(
    T->pleft!=NULL&&T->pright!=NULL)
                            {
                                if(
    x>T->pleft->k&&x<T->pright->k)  T->k=x;
                                else 
    printf("\n kok sua duoc.");
                            }
                            if(
    T->pleft==NULL&&T->pright==NULLT->k=x;
                }
            }
            if(
    t==NULL)
             
    printf("\n Khong ton tai root can sua .");
        }
    }
    void timthemang(TREE &p,TREE &q)
    {
        if(
    q->pleft!=NULL)
        {
            
    timthemang(p,q->pleft);
        }
        else
        {
               
    p->k=q->k;
               
    p=q;
               
    q=q->pright;
        }
    }
    void del(TREE &T,int x)
    {
        if(
    T==NULLprintf("Cay rong.");
        if(
    timnut(T,x)!=NULL){
        if(
    T->k>x)return del(T->pleft,x);
        if(
    T->k<x)return del(T->pright,x);
        else
        {
            
    TNODE *p=T;
            if(
    T->pleft==NULLT=T->pright;
            else
            {
                if(
    T->pright==NULLT=T->pleft;
                else
                {
                    
    TNODE *q=T->pright;
                    
    timthemang(p,q);
                    
    delete p;
                
                }
            }
        }
        }
        else 
    printf("Khong co nut can xoa.\n");
        
    }
    void xoanutnt(TREE &T)
    {
        if(
    T==NULL) ;
        if(
    T!=NULL)
        {
            
    xoanutnt(T->pleft);
            
    xoanutnt(T->pright);
            if(
    ktnt(T->k)==1)
            {
                
    del(T,T->k);
            }
        }    
    }
    void huycay(TREE &T)
    {
        if(
    T==NULL);
        if(
    T!=NULL)
        {
            
    huycay(T->pleft);
            
    huycay(T->pright);
            
    del(T,T->k);
        }
    }
    int demchan(TREE T)
    {
        
    int n;
       if(
    T==NULL) return 0;
       if(
    T->k%2==0)
           {
              
    n=1+demchan(T->pleft)+demchan(T->pright);
              
    printf("\n %d" ,T->k);
           }
       if(
    T->k%2!=0)
           {
               
    n=demchan(T->pleft)+demchan(T->pright);
           }
        
        return 
    n;
    }
    int demle(TREE T)
    {
        
    int n;
       if(
    T==NULL) return 0;
       if(
    T->k%2!=0)
           {
               
    n=1+demle(T->pleft)+demle(T->pright);
               
    printf("\n %d" ,T->k);
           }
       if(
    T->k%2==0)
           {
              
    n=demle(T->pleft)+demle(T->pright);
           }
        
        return 
    n;
    }
    TNODE *rootmin(TREE T)
    {
        
    TNODE *min;
        if(
    T==NULL) return NULL;
        else
        {
            
    min=T;
            while(
    T->pleft!=NULL)
            {
               
    T=T->pleft;
               
    min=T;
            }
            return 
    min;
        }
    }
    TNODE *rootmax(TREE T)
    {
        
    TNODE *max;
        if(
    T==NULL) return NULL;
        else
        {
            
    max=T;
            while(
    T->pright!=NULL)
            {
                
    T=T->pright;
                
    max=T;
            }
            return 
    max;
        }
    }
    int nutla(TREE T)
    {
        if(
    T==NULL) return 0;
        else
        {
            if(
    T->pleft==NULL&&T->pright==NULL)
            {  
                
    printf("\n %d",T->k);
                return 
    1;
            }
            else 
                return 
    nutla(T->pleft)+nutla(T->pright);
        }
    }
    int nutnhiphan(TREE T)
    {
        if(
    T==NULL) return 0;
        else
        {
            if((
    T->pleft==NULL&&T->pright!=NULL)||(T->pright==NULL&&T->pleft!=NULL))
            {
                
    printf("\n %d",T->k);
                return 
    1+nutnhiphan(T->pleft)+nutnhiphan(T->pright);
            }
            else
               return 
    nutnhiphan(T->pleft)+nutnhiphan(T->pright);
        }
    }
    int nuttoanphan(TREE T)
    {
        if(
    T==NULL) return 0;
        else
        {
            if(
    T->pleft!=NULL&&T->pright!=NULL)
            {
                
    printf("\n %d",T->k);
                return 
    1+nuttoanphan(T->pleft)+nuttoanphan(T->pright);
                
            }
            else
               return 
    nuttoanphan(T->pleft)+nuttoanphan(T->pright);
        }
    }
    int nutnhohon(TREE T,int x)
    {
        if(
    T==NULL) return 0;
        else
        {
            if(
    T->k<x)
            {
                
    printf("\n %d",T->k);
                return 
    1+nutnhohon(T->pleft,x)+nutnhohon(T->pright,x);
            }
            else
              return 
    nutnhohon(T->pleft,x)+nutnhohon(T->pright,x);
        }
    }
    int nutlonhon(TREE T,int x)
    {
        if(
    T==NULL) return 0;
        else
        {
            if(
    T->k>x)
            {
                
    printf("\n %d",T->k);
                return 
    1+nutlonhon(T->pleft,x)+nutlonhon(T->pright,x);
            }
            else
                return 
    nutlonhon(T->pleft,x)+nutlonhon(T->pright,x);
        }
    }
    int xrooty(TREE T,int x,int y)
    {
        if(
    T==NULL) return 0;
        else
        {
            if(
    T->k>x&&T->k<y)
            {
                
    printf("\n %d",T->k);
                return 
    1+xrooty(T->pleft,x,y)+xrooty(T->pright,x,y);
            }
            else
               return 
    xrooty(T->pleft,x,y)+xrooty(T->pright,x,y);
        }
    }
    /////het phan CAY NHI PHAN.
    ////////////    UNG DUNG QUEUE.
    void enqueue(LIST &Q,NODE *x)
    {
        if(
    Q.phead==NULL)
        {
            
    Q.phead=x;
            
    Q.ptail=Q.phead;
        }
        else
        {
            
    Q.ptail->pnext=x;
            
    Q.ptail=x;
            
    Q.ptail->pnext=NULL;
        }
    }
    TNODE *dequeue(LIST &Q)//lay ra va huy ptu dau queue.
    {
       
    NODE *p;
       if(
    Q.phead==NULL) return NULL;
       else
       {
           
    p=Q.phead;
           
    Q.phead=p->pnext;
           return 
    p->info;
           
    delete p;
       }
    }
    int isempty(LIST Q)
    {
        if(
    Q.phead==NULL) return 1;
        else
         return 
    0;
    }
    TNODE *front(LIST Q)
    {
        if(
    Q.phead==NULL) return NULL;
        else 
          return 
    Q.phead->info;
    }
    void xuatngangcay(TREE T)
    {
        LIST 
    Q;
        
    NODE *t;
        
    TNODE *p;
        
    Q.phead=Q.ptail=NULL;
        if(
    T==NULLprintf("\n Cay rong.");
        else
        {
            
    t=getnode(T);
            
    enqueue(Q,t);
            do
            {
                
    p=dequeue(Q);
                
    printf(" %d",p->k);
                if(
    p->pleft!=NULL)
                {
                    
    t=getnode(p->pleft);
                    
    addtail(Q,t);
                }
                if(
    p->pright!=NULL)
                {
                    
    t=getnode(p->pright);
                    
    addtail(Q,t);
                }
                   
            }while(
    isempty(Q)==0);
            
    printf("\n ");
        }
    }
    void xuatchieusau(TREE T)
    {
        LIST 
    Q;
        
    NODE *t;
        
    TNODE *p;
        
    Q.phead=Q.ptail=NULL;
        if(
    T==NULLprintf("\n Cay rong.");
        else
        {
            
    t=getnode(T);
            
    enqueue(Q,t);
            do
            {
                
    p=dequeue(Q);
                
    printf(" %d",p->k);
                if(
    p->pleft!=NULL)
                {
                    
    xuatchieusau(p->pleft);
                }
                if(
    p->pright!=NULL)
                {
                    
    t=getnode(p->pright);
                    
    addtail(Q,t);
                }
            }while(
    isempty(Q)==0);
        }        
    }

    /////het phan QUEUE.
    /////Ung dung STACK.
    void push(LIST &S,NODE *x)
    {
        
    addhead(S,x);
    }
    TNODE *pop(LIST &S)
    {
        
    NODE *p;
        if(
    S.phead==NULL) return NULL;
        else
        {
            
    p=S.phead;
            
    S.phead=p->pnext;
            return 
    p->info;
            
    delete p;
        }
    }
    int rong(LIST &S)
    {
        if(
    S.phead==NULL) return 1;
        else 
           return 
    0;
    }
    TNODE *top(LIST S)
    {
        if(
    S.phead==NULL) return NULL;
        else return 
    S.phead->info;
    }
    void xuatNLR(TREE T)
    {
        LIST 
    S;
        
    TNODE *p;
        
    NODE *t;
        
    S.phead=S.ptail=NULL;
        if(
    T==NULLprintf("\n Cay rong.");
        else
        {
            
    t=getnode(T);
            
    push(S,t);
            do
            {
                
    p=pop(S);
                
    printf(" %d",p->k);
                if(
    p->pright!=NULL)
                {
                    
    t=getnode(p->pright);
                    
    push(S,t);
                }
                if(
    p->pleft!=NULL)
                {
                    
    t=getnode(p->pleft);
                    
    push(S,t);
                }
            }while(
    rong(S)==0);
        }
    }
    void daonhanh(TREE &T)
    {
        
    TNODE *t;
        if(
    T)
        {
            
    daonhanh(T->pleft);
            
    daonhanh(T->pright);
            
    t=T->pleft;
            
    T->pleft=T->pright;
            
    T->pright=t;
        }
    }
    void chencaytraiphai(TREE &T,int x,TNODE *y,char lr)
    {
        
    TNODE *c;
        
    c=timnut(T,x);
        if(
    c==NULLprintf("\nKhong ton tai nut cha.");
        else
        {
            if(
    lr=='L')
            {
                if(
    c->pleft==NULL&&y->k<xc->pleft=y;
                if(
    c->pleft!=NULL&&y->k<x)
                {
                    if(
    c->pleft->k<y->k
                    {  
                        
    y->pleft=c->pleft;
                    }
                    if(
    c->pleft->k>y->k)
                    {
                        
    y->pright=c->pleft;
                    }
                    
    c->pleft=y;
                    
                }
                else 
    printf("Error !.");
            }
            if(
    lr=='R')
            {
                if(
    c->pright==NULL&&y->k>xc->pright=y;
                if(
    c->pright!=NULL&&y->k>x)
                {
                    if(
    c->pright->k<y->k
                    {  
                        
    y->pleft=c->pright;
                    }
                    if(
    c->pright->k>y->k)
                    {
                        
    y->pright=c->pright;
                    }
                    
    c->pright=y;
                }
                else 
    printf("Error !");
            }
            if(
    lr!='R'&&lr!='L')  printf("Error !");
        }
    }
    main()
    {
        
    TREE T;
        
    TNODE *e;
        LIST 
    L;
        
    int i,x,n,h,c;
        
    char lr;
        
    L.phead=L.ptail=NULL;
        
    T=NULL;
        
    printf("\n                              !!!!!!!!!!!!!!!!                                 ");
        
    printf("\n!-----------------------------------------------------------------------------!");
        
    printf("\n!                                TAUIT_DNMD                                   !");
        
    printf("\n!                       CAY NHI PHAN TIM KIEM TOAN TAP                        !");
        
    printf("\n!                                10.7.09                                      !");
        
    printf("\n!-----------------------------------------------------------------------------!");
        
    printf("\n\n");
             
    printf("\n!-----------------------------------------------!");
             
    printf("\n!                   -MENU-                      !");
             
    printf("\n!-----------------------------------------------!");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 1.Nhap cay                    !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 2.Xuat NLR                    !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 3.Xuat LNR                    !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 4.Xuat LRN                    !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 5.Xuat kieu truc quan        .!               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 6.Them root cho cay           !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 7.Sua noi dung 1 root         !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 8.Ham DEL root                !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 9.Xem root min                !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 10.Xem root max               !               !");
             
    printf("\n!-------------------------------!               !");
              
    printf("\n! 11.Tinh chieu cao cay         !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 12.Tinh tong so root          !               !");
             
    printf("\n!-------------------------------!               !");
              
    printf("\n! 13.Tinh so root nguyen to     !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 14.Tinh so root chan          !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 15.Tinh so root le            !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 16.Do tim                     !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 17.Tinh so muc cua 1 root     !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 18.Tim root cha               !               !");
             
    printf("\n!-------------------------------!               !");
              
    printf("\n! 19.So sanh muc                !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 20.Xoa root nguyen to         !               !");
             
    printf("\n!-------------------------------!               !");
              
    printf("\n! 21.Xuat ngang cay(dung QUEUE) !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 22.Xuat NLR(dung QUEUE)       !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 23.Xuat NLR(dung STACK)       !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 24.Huy cay.                   !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 25.Dem so nut la              !               !");
             
    printf("\n!-------------------------------!               !");
              
    printf("\n! 26.So nut co 1 cay con        !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 27.So nut co du 2 cay con     !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 28.So root nho hon x          !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 29.So root lon hon x          !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 30.So root thoa x < root < y  !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 31.Dao nhanh                  !               !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 32.Chen 1 nut vao cay con trai,phai cua 1 nut !");
             
    printf("\n!-------------------------------!               !");
             
    printf("\n! 0.De thoat khoi menu          !               !");
             
    printf("\n!-------------------------------!---------------!");
             do
             {
                 
    printf("\n  Nhap lua chon.....");
                 
    scanf("%d",&c);
                 switch(
    c)
                 {
                     case 
    1:
                       {
                           
    i=0;
                           
    printf("\nDung khi x=0.");
                           do
                           {
                               
    printf("\n nut %d: ",i+1);
                            
    scanf("%d",&x);
                            if(
    x!=0)
                               
    nhapcay(T,x);
                            else
                               
    printf("Da nhap xong!.");
                            
    i++;
                           }while(
    x!=0);
                           
    printf("\f");
                           break;
                       }
                       case 
    2:
                    {
                        
    printf("\n Cay: ");
                        
    inNLR(T);
                           break;
                    }
                    case 
    3:
                    {
                        
    printf("\n Cay: ");
                        
    inLNR(T);
                           break;
                    }         
                    case 
    4:
                    {
                        
    printf("\n Cay: ");
                        
    inLRN(T);
                           break;
                    }
                    case 
    5:
                    {
                        
    printf("\n Cay:\n");
                        
    xuatcay(T);
                        break;
                    }
                     case 
    6:
                     {
                           
    i=0;
                           
    printf("\nDung khi x=0.");
                           do
                           {
                               
    printf("\n nut %d: ",i+1);
                            
    scanf("%d",&x);
                            
    nhapcay(T,x);
                            
    i++;
                           }while(
    x!=0);
                           break;
                       }   
                    case 
    7:
                       
    printf("\n Ban sua root nao :info= ");
                        
    scanf("%d",&x);
                        
    printf("\n Gia tri :x= ");
                        
    scanf(" %d",&n);
                        
    sua(T,x,n);
                        
    printf("\n Cay sau khi sua:\n");
                        
    xuatcay(T);
                       break;      
                       case 
    8:
                          
    printf("\n Nhap root can DEL:x= ");
                          
    scanf("%d",&x);
                          
    del(T,x);
                          
    printf("\nCay sau khi DEL :\n");
                          
    xuatcay(T);
                          break;
                       case 
    9:
                          
    e=rootmin(T);
                          if(
    e==NULLprintf("\n Cay rong.");
                          else
                          {
                                 
    printf("\n Result:= %d",e->k);
                          }
                          
    printf("\n ");
                          
    xuatcay(e);                          
                          break;
                       case 
    10:
                          
    e=rootmax(T);
                          if(
    e==NULLprintf("\n Cay rong.");
                          else
                          {
                                 
    printf("\n Result:= %d",e->k);
                          }
                          
    printf("\n ");
                          
    xuatcay(e);
                          break;
                       case 
    11:
                          
    printf("\n Chieu cao: h= %d",chieucao(T));
                          break;
                       case 
    12:
                          
    printf("\nTong so root: = %d",sonut(T));
                          break;
                       case 
    13:
                          
    printf("\nTong so root nguyen to: = %d",demnt(T));
                          break;
                       case 
    14:
                          
    printf("\nTong so root chan: = %d",demchan(T));
                          break;
                    case 
    15:
                       
    printf("\nTong so root le: = %d",demle(T));
                       break;
                    case 
    16:
                       
    printf("\n nhap root can tim.\n");
                       
    scanf("\n%d",&x);
                       
    e=timnut(T,x);
                       if(
    e==NULL)
                       {
                          
    printf("\n nut ko ton tai.");
                       }
                       else
                       {
                          
    printf("\n Result :%d",e->k);
                          if(
    e->pleft==NULL)
                          {
                              
    printf("\n    Nut trai: NULL");
                          }
                          else
                              
    printf("\n    Nut trai: %d",e->pleft->k);
                          if(
    e->pright==NULL)
                              
    printf("\n    Nut phai: NULL");
                          else 
                              
    printf("\n    Nut phai: %d",e->pright->k);
                       }
                       
    printf("\nCay cua root do tim la:\n");
                       
    xuatcay(e);
                       break;
                    case 
    17:
                       
    printf("\nNhap root can tim muc: root= ");
                       
    scanf("%d",&x);
                       
    printf("\nMuc : %d",timduong(T,x));
                       break;
                    case 
    18:
                       
    printf("\n nhap root can tim root cha.\n");
                       
    scanf("\n%d",&x);
                       
    e=timnutcha(T,x);
                       if(
    e==NULL)
                       {
                          
    printf("\n nut cha ko ton tai.");
                       }
                       else
                       {
                          
    printf("\n Result :%d",e->k);
                          if(
    e->pleft==NULL)
                          {
                              
    printf("\n    Nut trai: NULL");
                          }
                          else
                              
    printf("\n    Nut trai: %d",e->pleft->k);
                          if(
    e->pright==NULL)
                              
    printf("\n    Nut phai: NULL");
                          else 
                              
    printf("\n    Nut phai: %d",e->pright->k);
                       }
                       
    printf("\nCay cua root cha:\n");
                       
    xuatcay(e);
                       break;
                    case 
    19:
                       
    printf("\n Lan luot nhap 2 root can so sanh: ");
                       
    scanf(" %d%d",&x,&n);
                       
    sosanh(T,x,n);
                       break;
                    case 
    20:
                       
    xoanutnt(T);
                       
    printf("\n Cay sau khi del nguyen to la.\n");
                       
    xuatcay(T);
                       break;
                    case 
    21:
                       
    printf("\nXuat ngang cay.\n");
                       
    xuatngangcay(T);
                       break;
                    case 
    22:
                       
    printf("\n Xuat NLR dung QUEUE:\n");
                       
    xuatchieusau(T);
                       break;
                    case 
    23:
                       
    printf("\n Xuat NLR dung STACK:\n");
                       
    xuatNLR(T);
                       break;
                    case 
    24:
                       
    huycay(T);
                       
    xuatcay(T);
                       break;
                    case 
    25:
                       
    printf("\n Tong so nut la: = %d",nutla(T));
                       break;
                    case 
    26:
                       
    printf("\n Tong so nut nhi phan la: = %d",nutnhiphan(T));
                       break;
                    case 
    27:
                       
    printf("\n Tong so nut toan phan la: = %d",nuttoanphan(T));
                       break;
                    case 
    28:
                       
    printf("\n Nhap x= ");
                       
    scanf("%d",&x);
                       
    printf("\n Tong so nut nho hon %d la: = %d",x,nutnhohon(T,x));
                       break;
                    case 
    29:
                       
    printf("\n Nhap x= ");
                       
    scanf("%d",&x);
                       
    printf("\n Tong so nut lon hon %d la: = %d",x,nutlonhon(T,x));
                       break;
                    case 
    30:
                       
    printf("\n Tim so root thoa: x < root < y");
                       
    printf("\n Nhap x= ");
                       
    scanf("%d",&x);
                       
    printf("\n Nhap y= ");
                       
    scanf("%d",&n);
                       
    printf("\n Tong so nut thoa la: = %d",xrooty(T,x,n));
                       break;
                    case 
    31:
                       
    daonhanh(T);
                       
    xuatcay(T);
                       break;
                    case 
    32:
                       
    printf("\nNhap gia tri nut cha,nut muon chen vao:");scanf("%d%d",&i,&n);
                       
    printf("Ban muon chen vao cay con ben nao (L/R)?:");
                       
    fflush(stdin);
                       
    lr=getchar();
                       
    e=new TNODE;
                       
    e->k=n;
                       
    e->pleft=e->pright=NULL;
                       if(
    timnut(T,n)!=NULLprintf("Khong chen duoc.");
                       else
                       {
                             
    chencaytraiphai(T,i,e,lr);
                       }
                       
    xuatcay(T);
                       break;
                       
                 }
             }while(
    c!=0);
        
    getch();

    Đã được chỉnh sửa lần cuối bởi tauit_dnmd : 06-07-2010 lúc 11:58 PM.

  6. #6
    Ngày gia nhập
    04 2010
    Nơi ở
    TP.HCM
    Bài viết
    39

    Mặc định Một số thao tác mở rộng về cây nhị phân tìm kiếm

    Trích dẫn Nguyên bản được gửi bởi donvuon Xem bài viết

    int count(pnode p, int level)// // Tỉnh tổng số nút có mức level
    {
    if (p == NULL || level == 0) return 0;
    if (level == 1) return 1;
    return count(p->left, level-1)+ count(p->right, level-1);
    }

    [/php]
    Coba góp 1 cách tính tổng số nút có mức level nữa này (trong bài Coba sẽ xét là mức k nhé)

    Code:
    ---------------Phần cài đặt tree-------------
    
    typedef struct nodet {
    			elem data;
    			struct nodet *left, *right;
    		} node;
    
    typedef node *tree;
    
    
    ------------------dem so nut tren muc k--------
    int NutMuc_k(tree t, int k)
    {
    	if(t==NULL)
    		return 0;
    	if(k>1)
    		return NutMuc_k(t->left,k-1) + NutMuc_k(t->right,k-1);
    	return 1;
    }
    "Không có chiến thắng nào vĩ đại hơn chiến thắng chính bản thân mình!"

  7. #7
    Ngày gia nhập
    09 2009
    Nơi ở
    205Bee
    Bài viết
    231

    Trích dẫn Nguyên bản được gửi bởi donvuon Xem bài viết
    Thế này nè, chuẩn luôn. Gọi CountUp(pRoot, depth, 1) nha.

    C Code:
    1. int CountUp( NodePtr pRoot, int depth, int n = 0 )
    2. {
    3.     if ( pRoot == NULL || n == 0 ) return 0;
    4.     if ( n <= depth ) return 1 + CountUp( pRoot->pLeft, depth, n + 1 ) + CountUp( pRoot->pRight, depth, n + 1 );
    5.     else return 0;
    6. }
    Đã xong vụ ĐH. Thanks Donvuon nha! nếu gọi từ n = 1 thì đâu cần
    PHP Code:
    if ( ||  == 
    nhỉ ? Cái hàm tính số nút ở mức K vẫn khó hiểu ghê!

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