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

Đề tài: Cây và cây nhị phân trong lập trình C

  1. #1
    Ngày gia nhập
    11 2008
    Nơi ở
    Pháo đài số
    Bài viết
    41

    Mặc định Cây và cây nhị phân trong lập trình C

    Hi...lại làm phiền mấy anh nữa rùi

    Lần này,em xin hỏi về cây và cây nhị phân.Híc học ở trường thì hĩu sơ sơ về cách biểu diễn cây nhị phân trong Danh sách liên kết bằng sư dụng 2 con trỏ trong struct để chỉ đến cây con trái và cây con phải của 1 nút.

    Vì ông thầy dồn hết zoo 1 buổi,nên chã hiểu rõ j,thế nên nhờ mấy anh chĩ dùm cho em về cây nhị phân

    Bắt đầu từ cách nhập và biểu diễn 1 cây.Vì thấy,thầy dạy có 3 cách biểu diễn,nhưng toàn là 1 dãy số hay 1 dãy ký tự,cái ni thấy khó nhìn với lại muốn kiển tra thì chã biết đc

    vd:như duyệt trước 1 cây nhị phân

    PHP Code:
    void DuyettruocTree T)
       {  
            if(
    T!=NULL)
               { 
    printf("%s",(*t).data);
                  
    Duyettruoc( (*t).left );
                  
    Duyettruoc( (*t).right );
                }
       }

      
    //Khai báo cây
    struct element
        
    {   char data;
             
    element *left,*right;
         }
    typedef element *Tree;
    Tree T
    mấy anh đừng nói về (*t).data hay left....nghe....em học viết struct kiểu này ah`

    Mấy anh có thể chỉ giúp cách biểu diễn khác cho dễ xem lại cây của mình trên màng hình.Và cách nhập cây nữa

    Cảm ơn mấy anh trước !!!

  2. #2
    Ngày gia nhập
    08 2008
    Nơi ở
    ha noi
    Bài viết
    79

    C Code:
    1. #include "stdio.h"
    2. #include "conio.h"
    3. #include "stdlib.h"
    4.  
    5. struct node
    6.     {
    7.         int infor;
    8.         struct node *left;
    9.         struct node *right;
    10.     };
    11.  
    12.  
    13. void insear(node *&root,node *p)
    14.     {
    15.         if (root == NULL)    root = p;
    16.         else if (p->infor < root->infor)    insear(root->left,p);
    17.         else if (p->infor > root->infor)    insear(root->right,p);
    18.     }
    19.  
    20. void nhap_cay(node *&root)
    21.     {
    22.         int e;
    23.         node *p;
    24.         root=NULL;
    25.         do
    26.         {
    27.             printf("Nhap vao cay(nhap nut -1 de ket thuc): ");
    28.             scanf("%d",&e);
    29.             if(e != -1)
    30.             {
    31.                 p = (node*)malloc(sizeof(node));
    32.                 p->infor = e;
    33.                 p->left= NULL;
    34.                 p->right = NULL;
    35.                 insear(root,p);
    36.             }
    37.         }
    38.         while (e!= -1);
    39.     }
    40.  
    41. void NLR(node *root)
    42.     {
    43.         if(root != NULL)
    44.             {
    45.                 printf(" %d ",root->infor);
    46.                 NLR(root->left);
    47.                 NLR(root->right);
    48.             }
    49.     }
    50.  
    51. void NRL(node *root)
    52.     {
    53.         if(root!=NULL)
    54.             {
    55.                 printf(" %d ",root->infor);
    56.                 NRL(root->right);
    57.                 NRL(root->left);
    58.             }
    59.     }
    60.  
    61.  
    62.  
    63. void RNL(node *root)
    64.     {
    65.         if(root!=NULL)
    66.             {
    67.                 RNL(root->right);
    68.                 printf(" %d ",root->infor);
    69.                 RNL(root->left);
    70.             }
    71.     }
    72.  
    73. void RLN(node *root)
    74.     {
    75.         if(root!=NULL)
    76.             {
    77.                 RLN(root->right);
    78.                 RLN(root->left);
    79.                 printf(" %d ",root->infor);
    80.             }
    81.     }
    82.  
    83.  
    84. void LRN(node *root)
    85.     {
    86.         if(root!=NULL)
    87.             {
    88.                 LRN(root->left);
    89.                 LRN(root->right);
    90.                 printf(" %d ",root->infor);
    91.             }
    92.     }
    93.  
    94. void LNR(node *root)
    95.     {
    96.         if(root!=NULL)
    97.             {
    98.                 LNR(root->left);
    99.                 printf(" %d ",root->infor);
    100.                 LNR(root->right);
    101.             }
    102.     }
    103.  
    104. void main(void)
    105.     {
    106.         clrscr();
    107.         node *root;
    108.         nhap_cay(root);
    109.         printf("Sap Xep Cay Nhi Phan Theo NLR: ");
    110.         NLR(root);
    111.         printf("\nSap Xep Cay Nhi Phan Theo NRL: ");
    112.         NRL(root);
    113.         printf("\nSap Xep Cay Nhi Phan Theo RLN: ");
    114.         RLN(root);
    115.         printf("\nSap Xep Cay Nhi Phan Theo RNL: ");
    116.         RLN(root);
    117.         printf("\nSap Xep Cay Nhi Phan Theo LNR: ");
    118.         LNR(root);
    119.         printf("\nSap Xep Cay Nhi Phan Theo LRN: ");
    120.         LRN(root);
    121.         printf("\nCay Sau Khi Xoa Dc Sap Xep Theo NLR: ");
    122.         NLR(root);
    123.         getch();
    124.     }

    Mình cũng mới học về cây đây là code mình cũng mới làm thôi mình post lên cho bạn tham khảo
    u never know

  3. #3
    Ngày gia nhập
    11 2008
    Nơi ở
    Pháo đài số
    Bài viết
    41

    híc...dù sao cũng cảm ơn...nhưng mình nghĩ chắc mình với bạn học khác cách biễu diễn rùi...híc ,đang cần giãi thích chứ code thì nhìu rùi....để còn tự viết chứ...hi...dù sao cũng cảm ơn bạn lần nữa

  4. #4
    Ngày gia nhập
    08 2008
    Nơi ở
    ha noi
    Bài viết
    79

    thế bạn cần giải thích phần nào trog code trên của mình nào :s mình có thể giải thích cho bạn bất cứ chỗ nào trg code của mình
    u never know

  5. #5
    Ngày gia nhập
    02 2008
    Nơi ở
    AYS 107
    Bài viết
    41

    Trích dẫn Nguyên bản được gửi bởi Chuột Xem bài viết
    Hi...lại làm phiền mấy anh nữa rùi

    Lần này,em xin hỏi về cây và cây nhị phân.Híc học ở trường thì hĩu sơ sơ về cách biểu diễn cây nhị phân trong Danh sách liên kết bằng sư dụng 2 con trỏ trong struct để chỉ đến cây con trái và cây con phải của 1 nút.

    Vì ông thầy dồn hết zoo 1 buổi,nên chã hiểu rõ j,thế nên nhờ mấy anh chĩ dùm cho em về cây nhị phân

    Bắt đầu từ cách nhập và biểu diễn 1 cây.Vì thấy,thầy dạy có 3 cách biểu diễn,nhưng toàn là 1 dãy số hay 1 dãy ký tự,cái ni thấy khó nhìn với lại muốn kiển tra thì chã biết đc

    vd:như duyệt trước 1 cây nhị phân

    PHP Code:
    void DuyettruocTree T)
       {  
            if(
    T!=NULL)
               { 
    printf("%s",(*t).data);
                  
    Duyettruoc( (*t).left );
                  
    Duyettruoc( (*t).right );
                }
       }

      
    //Khai báo cây
    struct element
        
    {   char data;
             
    element *left,*right;
         }
    typedef element *Tree;
    Tree T
    mấy anh đừng nói về (*t).data hay left....nghe....em học viết struct kiểu này ah`

    Mấy anh có thể chỉ giúp cách biểu diễn khác cho dễ xem lại cây của mình trên màng hình.Và cách nhập cây nữa

    Cảm ơn mấy anh trước !!!
    Trước hết là về cách biểu diễn cây nhị phân thì bạn làm như vậy là được rồi. Còn mình không rõ lắm ý của bạn ở chỗ "cho dễ xem lại cây của mình trên màn hình". Bạn viết chương trình đúng thì cây nhị phân bạn vẽ ra giống hệt như cây nhị phân mà chương trình đang biểu diễn thôi

    Đi vào vẫn đề chính là cách nhập cây:
    - Cấu trúc dữ liệu để lưu một cây nhị phân như thế kia là được rồi:
    (mình sửa lại trường data kiểu int cho dễ nói ở đoạn sau thôi)
    C Code:
    1. struct element
    2. {   int data;
    3.     struct element *left,*right;
    4. };
    5. typedef struct element *Tree;
    - Cách chèn một node vào cây thì sẽ dùng giải thuật đệ qui: nếu node cần thêm đó có giá trị nhỏ hơn nút gốc thì chèn nút đó vào cây con trái, ngược lại chèn vào cây con phải.
    C Code:
    1. void insert_node(int x,Tree *root)
    2. {
    3.   /*Kiểm tra nếu cây chưa được khởi tạo*/
    4.   if(*root==NULL){
    5.     (*root)=(treetype)malloc(sizeof(treetype));
    6.     (*root)->key=x;
    7.     (*root)->left=NULL;
    8.     (*root)->right=NULL;
    9.   }else if(x<(*root)->key) /*Giá trị khóa nhỏ hơn giá trị nút gốc: Chèn vào cây con trái*/
    10.     insert_node(x,&(*root)->left);
    11.   else if(x>(*root)->key)   /*Ngược lại chèn vào cây con phảii*/
    12.     insert_node(x,&(*root)->right);
    13. }
    Nói chung ở đây chỉ là dùng giải thuật đệ qui thôi. Hầu như các thao tác liên quan tới cây nhị phân đều phải dùng đệ qui. Các code khác thì 1 bạn ở trên đã post đủ hết rồi. Mình nghĩ bạn có thể tham khảo thêm
    I don't wanna waste another day

  6. #6
    Ngày gia nhập
    11 2008
    Nơi ở
    Pháo đài số
    Bài viết
    41

    Mặc định Cây và cây nhị phân trong lập trình C

    cảm ơn anh nhìu.

    Bạn có thể nói về cái sắp xếp,vì bản thân khi tạo ra cây nhị phân thì nó đã sắp xếp rùi (bên trái < nút < bên phải ),cái ni mi mình còn mờ mờ

    còn về tạo cây nhị phân thì hĩu rùi

  7. #7
    Ngày gia nhập
    11 2008
    Nơi ở
    Pháo đài số
    Bài viết
    41

    PHP Code:
    void insear(node *&root,node *p)
        {
            if (
    root == NULL)    root p;
            else if (
    p->infor root->infor)    insear(root->left,p);
            else if (
    p->infor root->infor)    insear(root->right,p);
        }

    void nhap_cay(node *&root)
        {
            
    int e;
            
    node *p;
            
    root=NULL;
            do
            {
                
    printf("Nhap vao cay(nhap nut -1 de ket thuc): ");
                
    scanf("%d",&e);
                if(
    != -1)
                {
                    
    = (node*)malloc(sizeof(node));
                    
    p->infor e;
                    
    p->leftNULL;
                    
    p->right NULL;
                    
    insear(root,p);
                }
            }
            while (
    e!= -1);
        } 
    như bài phái trên của bạn đó viết thì tạo 1 cây nhị phân tìm kiếm thì lúc đầu là tạo gốc và cho 2 nhánh của nó là NULL
    đến bước tiếp theo thì xét điều kiện để them gốc vào phía trái hay phãi

    thế thì ok rùi

    còn phần sắp xếp cây nhị phân ra sao,theo bài của bạn đó thì chĩ là duyệt cây nhị phân theo các thứ tự thui

    còn 1 câu hỏi nhỏ: mấy anh cho em bít có bao nhiêu phép toán cơ bản trên cấy nhị phân (như thêm xóa tìm...v..v....)

    thanks mấy anh trước

  8. #8
    Ngày gia nhập
    08 2008
    Nơi ở
    ha noi
    Bài viết
    79

    ý của bạn có phải là sắp xếp lại cây theo kiểu nhỏ hơn nút chính thì nằm ở bên trái lớn hon thì ở bên phải ko :s.
    cái này thì mình đã sử lý trong hàm insear rồi đó

    Code:
    void insear(node *&root,node *p)
        {
            if (root == NULL)    root = p;
            else if (p->infor < root->infor)    insear(root->left,p);
            else if (p->infor > root->infor)    insear(root->right,p);
        }
    đầu tiên mình kiểm tra xem cây có phải là cây rỗng hay ko. sau khi kiểm tra nếu cây không phải là cây rỗng thì mình cho so sánh các phần tử sau với phần tử đầu tiên thì có 2 trường hợp mình đã viết rõ trong bài
    TH1:
    Code:
    else if (p->infor < root->infor)    insear(root->left,p);
    nếu phần tử tiếp theo mà nhỏ hơn giá trị nút ban đầu thì mình gọi đệ quy chèn nó ở bên trái của cây.

    TH2: Tương tự như trường hợp 1 thôi
    u never know

  9. #9
    Ngày gia nhập
    11 2008
    Nơi ở
    Pháo đài số
    Bài viết
    41

    cái đó thì hĩu rối,nhưng mình thấy bản thân cây nhị phân tìm kiếm đã có sẳn là các nút cây con trái nhỏ hơn gốc và gốc nhỏ hơn các nút của cây con phải...thế thì chỉ cần Duyệt cây nhị phân thui,chứ nếu như thế thì sắp xếp là có sẳn rồi.

    còn như tìm kiếm cũng dùng luôn mấy hàm duyệt cây lun ah`...(LNR,NLR....)

    như thế thì trên cây nhị phân tìm kiếm chỉ còn có kiểm tra xem cây có cân bằng hay cân bằng hoàn toàn ,tìm số nút,độ cao của cây,xóa 1 nút trên cây....(còn cái nào nữa thì nhờ mấy anh chĩ dùm)

    thôi phần tao,xuất,và sắp xếp cũng như duyệt cây coi như tạm rồi,nhưng mình vẫn chưa hĩu cách xóa 1 nút mà sao cho để cây đó vẫn là cây nhị phân tìm kiếm...mấy anh chĩ giúp em phần đó đc kô ah`....thanks mấy anh trước

    P/s:nếu như thế này,nhập 1 cây nhị phân bình thường (số thôi) và sắp xếp nó thành cấy nhị phân tìm kiếm...câu hỏi lớn trong đầu...híc
    Đã được chỉnh sửa lần cuối bởi Chuột : 23-05-2009 lúc 02:44 PM.

  10. #10
    Ngày gia nhập
    08 2008
    Nơi ở
    ha noi
    Bài viết
    79

    để xóa 1 nút trong cây bạn thực hiện các bước sau

    Buoc1: Khai Bao 2 Con Tro Phu La P va P1 nhiem Vu Cua2 Con Tro Nay La Tro Den Vi Tri Can Xoa Trong Do Con Tro P Tro Den Vi Tri Can Xoa

    Buoc1: Tim ptu can xoa nam o ben nao cua cay

    Buoc2: Kiem Tra Xem Cay Con Ben Trai Or Ben Phai Co RongHay Khong.Neu Cay Ben Trai Ma Rong Thi Gan p Cho Node Hien Tai Sau Do Gan Node Hien Tai Cho Node Ben Cay Con Phai.Lam The Nguoc Lai Voi Cay ben Phai

    Buoc3: Truong Hop Con Lai: Khi Cay Co Ca Cay Con Ben Trai Va Cay Con Ben Phai Khi Nay Ta Co The Xoa 1 Trong 2 Cach Sau
    1> Xoa Cay Con Ben Trai Cua Node Goc
    2> Xoa Cay Con Ben Phai Cua Node Goc
    +> Chon Phuong An 1 Xoa Cay Con Ben Trai Cua Nut Goc.
    Gan p=node->left Luc Nay P Nhan Gia Tri Cua Nut Goc Ben Trai Cua Cay Sau Do Kiem Tra Xem Ben Cac Nut Con.Ben Phai Cua Nut Goc Ben Trai Dang Xet Co Bang Rong Hay ko. Truong Hop Neu Nut Con Ben Phai Cua Nut Goc Trai Rong Thi Gan Nut Tiep Theo Cho Nut Goc Ben Trai Tiep
    Theo Sau Do Gan Nut Ben Trai Cho Nut Goc Trai Nam O ben Trai Cua Cay
    Truong Hop Ngc Lai Neu Nut Con Ben Phai Cua Nut Goc Ben Trai Khac Rong Thi Dung 1 Vong Lap Do While De Tim Phan Tu CUoi Cung Ben Phai Cua Cay Con Ben Trai Trong Than Vog Lap Gan P1=P Va P=P->Right Khi Nay P Da Tro Den Phan Tu Can Xoa Trong Cay Thoat Vong Lap Gan Phan Tu Tiep Theo Cho P Tiep Gan P1->Right Cho Thang P->Left Giai Phong Bo Nho Cho P

    còn đây là code cuả mình
    Code:
    if(root!=NULL)
    			{
    				if(root->infor<x)
    					Xoa_Node(root->right,x);
    				else if(root->infor>x)
    					Xoa_Node(root->left,x);
    				else if(root->left==NULL)
    					{
    						p=root;
    						root=root->right;
    					}
    				else if(root->right==NULL)
    					{
    						p=root;
    						root=root->left;
    					}
    				else
    					{
    						p=root->left;
    						if(p->right==NULL)
    							{
    								root->infor=p->infor;
    								root->left=p->left;
    							}
    						else
    							{
    								do
    								{
    									p1=p;
    									p=p->right;
    								}while(p->right!=NULL);
    								root->infor=p->infor;
    								p1->right=p->left;
    							}
    					}
    				free(p);
    u never know

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