Thuật toán binary search tree trong lập trình C

[kingdark115]

#include "stdio.h"#include "conio.h"#include "alloc.h"struct bsts_node {    bsts_node *left;    bsts_node *right;    int data;};struct bsts_node *tmalloc(size_t size){    struct bsts_node *p;    p=(bsts_node *) malloc(size);    if(p ==NULL)    printf("\n out of memory");    else return p;}        struct bsts_node *createnode(size_t size){    struct bsts_node *n;    n = tmalloc(size);    n->left=n->right=NULL;    return n;}void bsts_insert(bsts_node *node_root,int datanew){    struct bsts_node *p;    p=node_root;      if(node_root == NULL) {        node_root=createnode(sizeof(bsts_node));        node_root->data = datanew;    }    else {        while(p!=NULL){            if(datanew == p->data) return;            else{                if(datanew > p->data) p=p->right;                else p=p->left;            }        }            p=createnode(sizeof(bsts_node));        p->data= datanew;    } }void printfPreorder(struct bsts_node *node_root){    if(node_root !=NULL) {        printf("%d\n",node_root->data);        printfPreorder(node_root->left);                printfPreorder(node_root->right);    }}void main(){    struct bsts_node *root=createnode(sizeof(bsts_node));    root->data= 25;    int i;    for(i=1;i<=50;i++){        bsts_insert(root,i);    }    printfPreorder(root);    getch();}

<---- 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

[zkday2686]

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:

void bsts_insert(bsts_node *node_root,int datanew){    struct bsts_node *p,*pChild;    p=node_root;      if(node_root == NULL) {        node_root=createnode(datanew);    }    else {        while(p!=NULL){            if(datanew == p->data) return;            else{                  if(datanew > p->data){                    pChild=p->right;                    if(!pChild)                    {                        struct bsts_node *newNode;                        newNode = createnode(datanew);                        p->right = newNode;                        return;                    }                 }                else{                     pChild=p->left;                    if(!pChild)                    {                        struct bsts_node *newNode;                        newNode = createnode(datanew);                        newNode->data = datanew;                        p->left = newNode;                        return;                    }                }                p = pChild;            }        } }

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;

struct bsts_node *createnode(int key){    struct bsts_node *n;    n = new bsts_node;    n->data = key;    n->left=n->right=NULL;    return n;}

[kidkid]

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 .

[chuonggio_mailaniemdau]

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?

[chuonggio_mailaniemdau]

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:

int input_bt(){ char *s; cout<<"nhap bt: s="; cin.igore(1); cin.get(s); return 1;}

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:

struct node{ char *s; node *left, *right; } *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?