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

Đề tài: Thuật toán binary search tree trong lập trình C

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

    Mặc định Thuật toán binary search tree trong lập trình C

    C Code:
    1. #include "stdio.h"
    2. #include "conio.h"
    3. #include "alloc.h"
    4. struct bsts_node {
    5.     bsts_node *left;
    6.     bsts_node *right;
    7.     int data;
    8. };
    9. struct bsts_node *tmalloc(size_t size){
    10.     struct bsts_node *p;
    11.     p=(bsts_node *) malloc(size);
    12.     if(p ==NULL)
    13.     printf("\n out of memory");
    14.     else return p;
    15. }
    16.    
    17.    
    18. struct bsts_node *createnode(size_t size){
    19.     struct bsts_node *n;
    20.     n = tmalloc(size);
    21.     n->left=n->right=NULL;
    22.     return n;
    23. }
    24. void bsts_insert(bsts_node *node_root,int datanew){
    25.     struct bsts_node *p;
    26.     p=node_root;
    27.  
    28.  
    29.     if(node_root == NULL) {
    30.         node_root=createnode(sizeof(bsts_node));
    31.         node_root->data = datanew;
    32.     }
    33.     else {
    34.         while(p!=NULL){
    35.             if(datanew == p->data) return;
    36.             else{
    37.                 if(datanew > p->data) p=p->right;
    38.                 else p=p->left;
    39.             }
    40.         }
    41.    
    42.         p=createnode(sizeof(bsts_node));
    43.         p->data= datanew;
    44.     }
    45.  
    46. }
    47. void printfPreorder(struct bsts_node *node_root){
    48.     if(node_root !=NULL) {
    49.         printf("%d\n",node_root->data);
    50.         printfPreorder(node_root->left);
    51.        
    52.         printfPreorder(node_root->right);
    53.     }
    54. }
    55. void main(){
    56.     struct bsts_node *root=createnode(sizeof(bsts_node));
    57.     root->data= 25;
    58.     int i;
    59.     for(i=1;i<=50;i++){
    60.         bsts_insert(root,i);
    61.     }
    62.     printfPreorder(root);
    63.     getch();
    64. }
    <---- sao em chạy cái này màn hình nó chỉ in ra mỗi số 25 là sao :((
    có ai giải thích giùm xem em sai ở đâu cái :((
    thanks nhiều

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

    Cái này bạn bị sai ở chổ hàm bsts_insert. Cái bạn sai là lúc thêm vào một Node thì chỉ có biết Node đang hiện hành là nó thôi chứ không biết Node cha của nó là ai. => sau khi bạn thêm vào một node thì nó bị mất dấu vết nên bạn chỉ in ra được phần tử Root của cây này thôi. đây là đoạn code Insert của mình:


    C Code:
    1. void bsts_insert(bsts_node *node_root,int datanew){
    2.     struct bsts_node *p,*pChild;
    3.     p=node_root;
    4.  
    5.  
    6.     if(node_root == NULL) {
    7.         node_root=createnode(datanew);
    8.     }
    9.     else {
    10.         while(p!=NULL){
    11.             if(datanew == p->data) return;
    12.             else{
    13.  
    14.  
    15.                 if(datanew > p->data){
    16.                     pChild=p->right;
    17.                     if(!pChild)
    18.                     {
    19.                         struct bsts_node *newNode;
    20.                         newNode = createnode(datanew);
    21.                         p->right = newNode;
    22.                         return;
    23.                     }
    24.  
    25.                 }
    26.                 else{
    27.  
    28.                     pChild=p->left;
    29.                     if(!pChild)
    30.                     {
    31.                         struct bsts_node *newNode;
    32.                         newNode = createnode(datanew);
    33.                         newNode->data = datanew;
    34.                         p->left = newNode;
    35.                         return;
    36.                     }
    37.                 }
    38.                 p = pChild;
    39.             }
    40.         }
    41.  
    42. }

    mà mình đã sửa lại hàm createnode(datanew); để phù hợp với vc6.0 khi mình test
    đây là code của nó để bạn test;

    C Code:
    1. struct bsts_node *createnode(int key){
    2.     struct bsts_node *n;
    3.     n = new bsts_node;
    4.     n->data = key;
    5.     n->left=n->right=NULL;
    6.     return n;
    7. }

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    ke cái này chẳng qua là 1 phép duyệt thôi. Nhưng khi duyệt thì thực hiện phép tính luôn. Có nghĩa là ở các mức lẻ thay vì chưa dữ liệu số sẽ chưa các phép tính , còn mức chẵn là các toán hạng. Nếu cậu duyệt rồi thì sẽ làm được cái này .

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

    Trích dẫn Nguyên bản được gửi bởi kidkid Xem bài viết
    ke cái này chẳng qua là 1 phép duyệt thôi. Nhưng khi duyệt thì thực hiện phép tính luôn. Có nghĩa là ở các mức lẻ thay vì chưa dữ liệu số sẽ chưa các phép tính , còn mức chẵn là các toán hạng. Nếu cậu duyệt rồi thì sẽ làm được cái này .
    Giả sử có phép toán này: (a*b)\(c+d)-(e+f)\(g-i)+(h*k) khi mới nhập dữ liệu vào thì có cần xác định phép toán nào là gốc của cây?

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

    Trích dẫn Nguyên bản được gửi bởi kidkid Xem bài viết
    ke cái này chẳng qua là 1 phép duyệt thôi. Nhưng khi duyệt thì thực hiện phép tính luôn. Có nghĩa là ở các mức lẻ thay vì chưa dữ liệu số sẽ chưa các phép tính , còn mức chẵn là các toán hạng. Nếu cậu duyệt rồi thì sẽ làm được cái này .
    Nói vắn tắt như bạn thì khó hiểu quá. Đúng là 1 phép duyệt cây (inorder) thì là bài toán tính biểu thức trung tố.
    Nhưng trong cây nhị phân thì gốc là phép toán, con trái(phải) là toán hạng. Giả sử cần tính biểu thức này:(a*b)\(c+d)-(e+f)\(g-i)+(h*k) thì khi tạo biểu thức đó thành 1 cây thì phải tìm được phép toán ưu tiên cuối cùng làm gốc (ở đây là 1 biểu thức bất kỳ). " ( )" rõ ràng khi nhập biểu thức thì có nhưng trong cây thì không. Vậy phải loại bỏ thế nào đây khi tạo cây???
    Trong biểu thức có cả phép toán nên lúc đầu tui nhập vào là kiểu char:
    C Code:
    1. int input_bt()
    2. {
    3.  char *s;
    4.  cout<<"nhap bt: s=";
    5.  cin.igore(1);
    6.  cin.get(s);
    7.  return 1;
    8. }
    Sau đó đưa biểu thức nhập trên tạo thành cây và dữ liệu vào vẫn là kiểu char:
    C Code:
    1. struct node
    2. {
    3.  char *s;
    4.  node *left, *right;
    5. } *p;
    Vậy để nhập số cụ thể cho các toán hạng (a,b,c.....) thì tui dùng hàm atoi(s) khi nào đây?
    Cho tui hướng giải quyết tốt nhất hem?

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

  1. Binary search tree với số lượng phần tử lớn bị stack overflow?
    Gửi bởi kyozanuro trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 2
    Bài viết cuối: 16-12-2011, 10:19 PM
  2. Hàm insert giảm dần trong binary search tree
    Gửi bởi sieuthanh trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 13-11-2011, 12:55 AM
  3. Cài đặt Binary Search Tree bằng C#
    Gửi bởi Yin Yang trong diễn đàn Tutorials và Thủ thuật lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 16-01-2011, 04:42 PM
  4. Đọc file đưa vào Binary search tree như thế nào?
    Gửi bởi hoangnn90 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 17-11-2010, 08:21 AM
  5. binary search tree.
    Gửi bởi pocolo trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 14-09-2009, 04:55 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