이진 검색 트리에 노드를 임의로 추가하면 노드

Question

스택이 무작위로 삭제됩니다. TYPE (TYPE은 데이터의 typedef입니다.) 요소를 추가하고 제거 할 수있는 이진 트리가 있습니다. 그러나 어떤 이유로 인해 추가 된 특정 값은 이전 요소를 덮어 씁니다. 여기에 요소를 덮어 쓰지 않고 요소를 겹쳐 쓰지 않고 삽입하는 예가 나와 있습니다.

데이터 내가 저장 해요 :

struct data { 
int number; 
char *name; 
}; 

typedef struct data data; 

# ifndef TYPE 
# define TYPE  data* 
# define TYPE_SIZE sizeof(data*) 
# endif 

트리 구조체 : 데이터에 대한

struct Node { 
TYPE   val; 
struct Node *left; 
struct Node *rght; 
}; 

struct BSTree { 
struct Node *root; 
int   cnt; 
}; 

비교기.

int compare(TYPE left, TYPE right) { 
    int left_len; int right_len; int shortest_string; 

    /* find longest string */ 
    left_len = strlen(left->name); 
    right_len = strlen(right->name); 
    if(right_len < left_len) { shortest_string = right_len; } else { shortest_string = left_len; } 

    /* compare strings */ 
    if(strncmp(left->name, right->name, shortest_string) > 1) { 
     return 1; 
    } 
    else if(strncmp(left->name, right->name, shortest_string) < 1) { 
     return -1; 
    } 
    else { 
     /* strings are equal */ 

     if(left->number > right->number) { 
      return 1; 
     } 
     else if(left->number < right->number) { 
      return -1; 
     } 
     else { 
      return 0; 
     } 
    } 
} 

그리고 추가 방법

struct Node* _addNode(struct Node* cur, TYPE val) { 
    if(cur == NULL) { 
     /* no root has been made */ 
     cur = _createNode(val); 

     return cur; 
    } 
    else { 
     int cmp; 

     cmp = compare(cur->val, val); 
     if(cmp == -1) { 
      /* go left */ 

      if(cur->left == NULL) { 
       printf("adding on left node val %d\n", cur->val->number); 
       cur->left = _createNode(val); 
      } 
      else { 
       return _addNode(cur->left, val); 
      } 
     } 
     else if(cmp >= 0) { 
      /* go right */ 

      if(cur->rght == NULL) { 
       printf("adding on right node val %d\n", cur->val->number); 
       cur->rght = _createNode(val); 
      } 
      else { 
       return _addNode(cur->rght, val); 
      } 
     } 

     return cur; 
    } 
} 

void addBSTree(struct BSTree *tree, TYPE val) 
{ 
tree->root = _addNode(tree->root, val); 
tree->cnt++; 
} 

새 노드 생성하는 방법 :

struct Node* _createNode(TYPE val) { 
struct Node* new_node; 
new_node = (struct Node*)malloc(sizeof(struct Node*)); 
new_node->val = val; 
new_node->left = NULL; 
new_node->rght = NULL; 

return new_node; 
} 

기능은 트리 인쇄 : 여기

void printTree(struct Node *cur) { 
    if (cur == 0) { 
     printf("\n"); 
    } 
    else { 
     printf("("); 
     printTree(cur->left); 
     printf(" %s, %d ", cur->val->name, cur->val->number); 
     printTree(cur->rght); 
     printf(")\n"); 
    } 
} 

은 예입니다 덮어 쓸 데이터 일부 이전 요소 :

struct BSTree myTree; 
struct data myData1, myData2, myData3; 

myData1.number = 5; 
myData1.name = "rooty"; 
myData2.number = 1; 
myData2.name = "lefty"; 
myData3.number = 10; 
myData3.name = "righty"; 

initBSTree(&myTree); 
addBSTree(&myTree, &myData1); 
addBSTree(&myTree, &myData2); 
addBSTree(&myTree, &myData3); 
    printTree(myTree.root); 

인쇄합니다 : 마지막으로 여기

((
righty, 10 
) 
lefty, 1 
) 

는 이전 데이터와 동일한 자리에 가서 몇 가지 테스트 데이터,하지만 이번에는 데이터가 덮어 쓰기되지 않습니다 :

struct BSTree myTree; 
struct data myData1, myData2, myData3; 

myData1.number = 5; 
myData1.name = "i"; 
myData2.number = 5; 
myData2.name = "h"; 
myData3.number = 5; 
myData3.name = "j"; 

initBSTree(&myTree); 
addBSTree(&myTree, &myData1); 
addBSTree(&myTree, &myData2); 
addBSTree(&myTree, &myData3); 
printTree(myTree.root); 

인쇄 어느 :

((
j, 5 
) 
i, 5 (
h, 5 
) 
) 

누가 잘못 될지 알 수 있습니까? 죄송합니다.이 게시물이 길었습니다.

Answer 1

_addNode 절차에 오류가있는 것 같습니다. 트리에 새 노드 참조를 제대로 저장하지 못하는 것 같습니다.

struct Node* _addNode(struct Node* cur, TYPE val) { 
if(cur == NULL) { 
    /* no root has been made */ 
    cur = _createNode(val); 
    return cur; 
} 
else { 
    int cmp; 

    cmp = compare(cur->val, val); 
    if(cmp == -1) { 
     /* go left */ 
     cur->left = _addNode(cur->left, val); 
    } 
    else if(cmp >= 0) { 
     /* go right */ 
     cur->left = _addNode(cur->right, val); 
    } 

    return cur; 
} 

_addnode 함수는 반환 값을 일관성없이 사용했기 때문에 다소 혼란 스러웠습니다. 나는이 버전이 모든 노드를 잃어 버리지 않아야한다고 생각한다.

Answer 2

명백한 결함이 보이지 않습니다. 나는 당신의 현재 데이터보다 더 단순한 int 또는 뭔가를 보유하기 위해 트리를 재 작업하는 것이 좋습니다. 트리가 정상적으로 작동하면 적어도 어디서 볼 것인지를 결정하고 일반 트리 코드는 걱정하지 않아야합니다.

_createNode()가 의심 스럽습니까? 코드를 추가 할 수 있습니까?