Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Xin giải thích dum code duyệt cây tổng quát

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

    Mặc định Xin giải thích dum code duyệt cây tổng quát

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    #include <alloc.h>
    
    #define TRUE 1
    #define FALSE 0
    #define ORDER 4  // bac cua cay
    
    // Khai bao cau truc cua mot nut
         struct node
            {
             int numtrees;             // so cay con cua mot nut
            int key[ORDER-1];         // cac khoa cua mot nut  
            struct node *son[ORDER];  // cac con tro chi cac nut con cua mot nut
    };    
    
        typedef struct node *NODEPTR;
    
         NODEPTR ptree;     // con tro chi nut goc cua cay
    
    // Tac vu getnode: cap phat mot nut cho cay
      NODEPTR getnode(void)
    {
         NODEPTR p;
          p = (NODEPTR)malloc(sizeof(struct node));
         return(p);
    }
    
    // Tac vu freenode: huy nut da cap phat
          void freenode(NODEPTR p)
    {
                    free(p);
    }
    
    // Tac vu initialize: khoi dong cay
         void initialize()
    {
                 ptree = NULL;
    }
    
    // Tac vu makenode: tao nut moi tren cay, nut moi co mot khoa k
    NODEPTR makenode(int k)
    {
                int i;
                NODEPTR p;
                p = getnode();
                 p->numtrees = 2;           // xem nut moi co hai cay con
                 p->key[0] = k;             // nut moi co mot khoa la k
       for(i = 0; i < ORDER; i++) // nut moi chua co nut con
          p->son[i] = NULL;
       return(p);
    }
    
    /* Tac vu nodesearch: tim trong nut vi tri cua khoa cua khoa bat dau >= k.
       Truong hop k lon hon tat ca cac khoa trong nut thi tra ve vi tri
       p->numtrees-1 */
    int nodesearch(NODEPTR p, int k)
    {
       int i;
       for(i = 0; i < p->numtrees-1 && p->key[i] < k; i++)
          ;
       return(i);
    }
    
    /* Tac vu search: tim khoa k co tren cay chua
       Neu co:
          - Bien found tra ve gia tri TRUE
          - Ham search() tra ve con tro chi nut co chua khoa k
          - Bien position tra ve vi tri cua khoa k co tren nut nay
       Neu khong co:
          - Bien found tra ve gia tri FALSE
          - Ham search() tra ve con tro chi nut co the them khoa k vao
          - Bien position tra ve vi tri them khoa k vao nut nay */
    NODEPTR search(int k, int *pposition, int *pfound)
    {
       int i;
       NODEPTR p, q;   // q la nut cha, p la nut con
       q = NULL;
       p = ptree;
       while(p != NULL)
       {
          i = nodesearch(p, k);
          if(i < p->numtrees-1 && k == p->key[i])    // tim thay
          {
    	      *pfound = TRUE;
    	      *pposition = i;
    	      return(p);
          }
          q = p;
          p = p->son[i];
       }
       /* Khi thoat khoi vong lap la khong tim thay, luc nay p = NULL, q la nut
          nua la (semileaf) co the them khoa k vao nut nay, position la vi tri
          co the chen khoa k */
       *pfound = FALSE;
       *pposition = i;
       return(q);      // tra ve nut nua la
    }
    
    // Tac vu traverse: duyet cay bang phuong phap de qui
    void traverse(NODEPTR proot)
    {
       int i, nt;
       if(proot == NULL)         // dieu kien dung
          return;
       else                      // buoc de qui
       {
          nt = proot->numtrees;  // nt la so cay con cua nut proot
    
          // vong lap duyet cay con son[i] va in khoa key[i] cua nut proot
          for(i = 0; i < nt-1; i++)
          {
    	      traverse(proot->son[i]);
    	      printf("%8d", proot->key[i]);
          }
    
          // duyet cay con cuoi cua nut proot
          traverse(proot->son[nt-1]);
       }
    }
    
    // Tac vu viewnodes: xem noi dung cac nut cua nhanh cay con co nut goc proot
    void viewnodes(NODEPTR proot, int level)
    {
       int i;
       if(proot == NULL)              // dieu kien dung
          return;
       else                           // buoc de qui
       {
          // in cac khoa cua nut proot
          printf("Nut %p (muc %d): ", proot, level);
          for(i = 0; i < proot->numtrees-1; i++)
             printf("%4d ", proot->key[i]);
          printf("\n");
          // vong lap goi de qui de xem noi dung cac nhanh cay con son[i]
          for(i = 0; i < proot->numtrees; i++)
    	      viewnodes(proot->son[i], level+1);
       }
    }
    
    /* Tac vu insleaf: Tac vu nay giup chen khoa k vao nut s. (Nut s la nut la
       va chua day) */
    void insleaf(NODEPTR s, int k, int pos)
    {
       int i, nt;
       nt = s->numtrees;
       s->numtrees = nt+1;       // tang so cay con cua nut s len 1
    
       // doi cac khoa tu vi tri pos den nt-2 xuong mot vi tri
       for(i = nt-1; i > pos; i--)
          s->key[i] = s->key[i-1];
    
       // Chen khoa k vao vi tri pos
       s->key[pos] = k;
    }
    
    // Tac vu insert: Them khoa k vao cay.
    NODEPTR insert(int k)
    {
       NODEPTR s, p;
       int position, found;
    
       // Truong hop cay bi rong thi tao nut goc
       if(ptree == NULL)
       {
          ptree = makenode(k);
          return(ptree);
       }
    
       // cay khong bi rong, tim khoa k co trong cay hay khong
       s = search(k, &position, &found);
    
       // Neu tim thay, bao trung khoa
       if(found == TRUE)
       {
          printf("\nBi trung khoa, khong them khoa %d vao cay duoc", k);
          return(s);
       }
    
       // Them khoa vao nut s
       if(s->numtrees < ORDER)   // truong hop nut s chua day
       {
          insleaf(s, k, position);
          return(s);
       }
       p = makenode(k);          // truong hop nut s da day, cap phat nut moi
       s->son[position] = p;
       return(p);
    }
    
    // Chuong trinh chinh
    void main()
    {
       int i, n, k, pos, timthay, chucnang;
       char c;
       NODEPTR p;
    
       clrscr();
       initialize();   // khoi dong cay
    
       do
       {
          // menu chinh cua chuong trinh
          printf("\n\nCAY NHIEU NHANH TIM KIEM TREN-XUONG (TOP-DOWN MULTIWAY SEARCH TREE)");
          printf("\n\nCac chuc nang cua chuong trinh:\n");
          printf("   1: Them mot khoa\n");
          printf("   2: Them ngau nhien nhieu khoa\n");
          printf("   3: Duyet cay theo thu tu tu nho den lon\n");
          printf("   4: Xem noi dung tung nut cua cay tren-xuong\n");
          printf("   5: Tim kiem\n");
          printf("   0: Ket thuc chuong trinh\n");
          printf("Chuc nang ban chon: ");
          scanf("%d", &chucnang);
          switch(chucnang)
          {
    	      case 1:
    	      {
    	         printf("\nNoi dung khoa moi: ");
    	         scanf("%d", &k);
    	         insert(k);
    	         break;
    	      }
    	      case 2:
    	      {
    	         printf("\nBan muon them vao bao nhieu khoa: ");
    	         scanf("%d", &n);
    	         for
                (int i = 0; i < n; i++)
    	        insert(random(10000));
    	         printf("\nDa them vao cay %d so ngau nhien", n);
    	         break;
    	      }
    	      case 3:
    	      {
    	         printf("\nDuyet cay theo thu tu tu nho den lon\n");
    	         if(!ptree)
    	            printf("Cay bi rong");
    	         else
    	            traverse(ptree);
    	         break;
    	      }
    	      case 4:
    	      {
                clrscr();
    	         printf("\nXem noi dung tung nut cua cay tren-xuong\n");
    	         if(!ptree)
    	            printf("Cay rong");
    	         else
                {
    	            viewnodes(ptree, 0);
                   getch();
                }
    	         break;
    	      }
    	      case 5:
    	      {
    	         printf("\nKhoa can tim: ");
    	         scanf("%d", &k);
    	         p = search(k, &pos, &timthay);
    	         if(timthay)
    	            printf("Tim thay tai vi tri %d cua nut co con tro %d", pos, p);
    	         else
    	            printf("Khong tim thay");
    	         break;
    	      }
          }
       } while(chucnang != 0);
    }


    mình không hiểu tại sao trong phần
    struct node
    {
    int numtrees; // so cay con cua mot nut
    int key[ORDER-1]; // cac khoa cua mot nut cái này là cái gì vậy mỗi nút chỉ có 1 khóa thôi cơ mà
    struct node *son[ORDER]; // cac con tro chi cac nut con cua mot nut
    };

  2. #2
    Ngày gia nhập
    09 2007
    Bài viết
    724

    cái này đơn giản mà bạn

    1 node có n khoá thì có n+1 cây con .

    ví dụ cây nhị phân: 1 node có 1 key thì sẽ có 2 cây con.

    1 node có ORDER cây con thì sẽ có ORDER-1 key.

    ví dụ:
    ___________
    |___|____|___|
    | | | |
    | | | |

    node có 3 key thì sẽ có 4 cây con

    P.s làm biếng vẽ hình cái hình nó nhảy lung tung

  3. #3
    Ngày gia nhập
    11 2012
    Nơi ở
    bac ninh
    Bài viết
    0

    Mặc định duyệt cây tổng quát qua cây nhị phân

    hic có ai giải giúp tớ bài này với: duyệt cây tổng quát qua cây nhị phân

Các đề tài tương tự

  1. Code tự động xóa cookie của trình duyệt
    Gửi bởi thangemhamhochoi trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 5
    Bài viết cuối: 16-04-2015, 03:12 PM
  2. Trình duyệt Opera, giúp bạn trải nghiệm tốt hơn khi duyệt wap
    Gửi bởi hailuacuibep trong diễn đàn Software (Phần mềm) | Ebooks
    Trả lời: 2
    Bài viết cuối: 02-01-2013, 12:12 PM
  3. UC Browser- Trình duyệt cho di động - đơn giản mà mạnh mẽ
    Gửi bởi google_android 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-12-2012, 10:01 PM
  4. Chuyển code duyệt file từ vc++.net sang vc#?
    Gửi bởi luongtankhang123 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 12-03-2012, 09:14 PM
  5. đệ quy-->duyệt cây nhi phan không đơn giản!
    Gửi bởi qhai_2009 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 10
    Bài viết cuối: 23-05-2011, 04:39 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