BST تنفيذ

Question

ما هو الخطأ التالية تنفيذ شجرة البحث الثنائية (BST)?لقد قيل لي أنه من الأفضل استخدام مؤشر إلى مؤشر إلى struct عقدة كحجة في إدراج دالة.

struct node
{
int key_value;
struct node* left;
struct node* right;
};

insert(int key, struct node *leaf)
{
    if( leaf == 0 )
    {
        leaf = (struct node*) malloc( sizeof( struct node ) );
        leaf->key_value = key;
        /* initialize the children to null */
        leaf->left = 0;    
        leaf->right = 0;  
    }
    else if(key < leaf->key_value)
    {
        insert( key, leaf->left );
    }
    else if(key > leaf->key_value)
    {
        insert( key, leaf->right );
    }
}

Answer 1

هذا السطر:

leaf = (struct node*) malloc( sizeof( struct node ) );

يعطي قيمة جديدة leaf, ، لافتا أنه في بعض الذاكرة المخصصة حديثا.ومع ذلك ، فإن القيمة الجديدة لا يترك وظيفة.عندما ترجع الدالة المتصل سوف يكون لا يزال في اشارة الى القديم leaf, و سوف يكون هناك تسرب الذاكرة.

هناك طريقتان يمكنك أن تأخذ لتحديد ذلك:

1. استخدام مؤشر إلى مؤشر مثلا

void insert(int key, struct node **leaf)
{
    if(*leaf == 0 )
    {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
        ...
}

/* In caller -- & is prepended to current_leaf. */
insert(37, &current_leaf);

2. عودة صفحة جديدة (أو أوراق قديمة إذا كان هناك أي تغيير).

struct node *insert(int key, struct node *leaf)
{
    if(leaf == 0 )
    {
        leaf = (struct node*) malloc( sizeof( struct node ) );
        ...
    }

    return leaf;
}

/* In caller -- & is prepended to current_leaf. */
current_leaf = insert(37, current_leaf);

المؤشرات إلى مؤشرات قريبة من عتبة يجري من الصعب أن نفهم.ربما أود أن تذهب للخيار الثاني ، إذا insert حاليا لا تعود أي شيء آخر.

Answer 2

وعندما يتم إدخال عقدة (ورقة == 0)، أنت لم تتغير الأم، وبالتالي فإن عقدة جديدة سوف تصبح يتيما.

في بعبارة أخرى، فإن شجرة الخاص بك لا تزال تبدو وكأنها عقدة واحدة فقط، مهما كانت تسمى العديد من العقد مع إدراج.

Answer 3

  #include<stdio.h>
     typedef struct tnode{
       int data;
       struct tnode *left,*right;
     }TNODE;
     TNODE * createTNode(int key){
       TNODE *nnode;
       nnode=(TNODE *)malloc(sizeof(TNODE));    
       nnode->data=key;
       nnode->left=NULL;
       nnode->right=NULL;
      return nnode;
}

    TNODE * insertBST(TNODE *root,int key){
     TNODE *nnode,*parent,*temp;
     temp=root;
      while(temp){
        parent=temp;
        if(temp->data > key)
            temp=temp->left;
        else
            temp=temp->right;    
    }    
     nnode=createTNode(key);
    if(root==NULL)
        root=nnode;
    else if(parent->data>key)
        parent->left=nnode;
    else
        parent->right=nnode;
    return root;
}

     void preorder(TNODE *root){
       if(root){
         printf("%5d",root->data);    
         preorder(root->left);
         preorder(root->right);
       }    
     }  

    void inorder(TNODE *root){
       if(root){
        inorder(root->left);
        printf("%5d",root->data);    
        inorder(root->right);
      }    
    }

    void postorder(TNODE *root){
       if(root){
        postorder(root->left);    
        postorder(root->right);
        printf("%5d",root->data);
      }    
    }

     main(){
       TNODE *root=NULL;
       int ch,key;
       do{
         printf("\n\n1-Insert\t2-Preorder\n3-Inorder\t4-Postorder\n5-Exit\n");
         printf("Enter Your Choice: ");
         scanf("%d",&ch);  

        switch(ch){ 
            case 1:
                printf("Enter Element: ");
                scanf("%d",&key);
                root=insertBST(root,key);
                break;
            case 2:
                preorder(root);
                break;
            case 3:
                inorder(root);
                break;
            case 4:
                postorder(root);
                break;
            default:
                printf("\nWrong Choice!!");
        }

    }while(ch!=5);
    getch();
    return 0;
}