BST 구현

Question

다음 구현에서 binary search tree (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; 
}