AVL 트리에 삽입 기능이 삽입되지 않습니다.

Question

문자열을 키로 사용하여 avl 트리를 작업하고 있습니다. print 문은 삽입이 일어나고 있음을 나타내지 만 테스트 기능에서는 루트의 왼쪽과 오른쪽 노드가 null로 남아 있다고보고합니다.

#include "AVLAdt.h" 

void printVal(node * toPrint){ 
    printf("\n node value: %s\n", toPrint->nodeValue); 
} 

node * search(node * root, char * searchVal){ 
    if(isExternal(root) == 1) return NULL; 
    if(strcmp(searchVal,root->nodeValue)<0){ 
     return(search(root->leftNode,searchVal)); 
    } 
    else if(strcmp(searchVal,root->nodeValue)==0){ 
     return(root); 
    } 
    else { 
     return(search(root->rightNode,searchVal)); 
    } 
} 



/*initialize a node*/ 
node * initNode(char * toAdd){ 
    node * newNode = malloc(sizeof(node)); 
    strcpy(newNode->nodeValue, toAdd); 
    newNode->leftNode = NULL; 
    newNode->rightNode = NULL; 
    newNode->height = 1; 
    return newNode; 
} 



/*function to insert a new node into tree and rebalance if necessary*/ 
node * insert(node * root, char * newValue){ 


    if(root == NULL){ 
     printf("\n Inserting %s. \n", newValue); 
     return(initNode(newValue)); 

    } 
    else{ 

     if(strcmp(newValue,root->nodeValue)<0){ 
      printf("go left"); 
      insert(root->leftNode, newValue); 
     } 
     else if(strcmp(newValue,root->nodeValue)>0){ 
      printf("go to right node of %s", root->nodeValue); 
      insert(root->rightNode, newValue); 
     } 
     else{ 
      root->count++; 
      return (root); 
     } 
    } 

테스트 프로그램 :

여기 내 AVL 트리 코드

#include "AVLAdt.h" 

int main(){ 


    node * root = NULL; 

    char * testString = malloc(sizeof(char)*50); 
    strcpy(testString, "aa"); 

    char * testString1 = malloc(sizeof(char)*50); 
    strcpy(testString1, "bb"); 


    printf("does it try to insert?"); 

    root = insert(root, testString); 
    root = insert(root, testString1); 

    printVal(root); 

    if(getRight(root) == NULL) printf("right is null"); 
    else{ 

     printf("right is"); 
     printVal(getRight(root)); 
    } 

    if(getLeft(root) == NULL) printf("left is null"); 
    else{ 

     printf("left is"); 
     printVal(getRight(root)); 
    } 



    return(0); 
} 

코드는 "AA"모두 왼쪽과 오른쪽 노드가 null 있음을 반환합니다. 왜 이런거야? 하지 있는지 node이 외부 경우

if(isExternal(root) == 1) return NULL; 

할 이유, 즉 어떤 잎이없는 search() 기능에

Answer 1

, 당신은 여전히 ​​nodeValuesearchVal에 비교하고 root을 반환 할 것 일치하는 경우. initNode() 기능에서

, 다음 - 투 - 마지막 줄

newNode->count = 1; 

대신 또한

newNode->height = 1; 

해야한다, 그것은 나에게 보인다 그 insert() 함수에서 initNode()의 반환 값을 root에 할당하여 트리에 새로 추가 된 node에 대한 포인터를 저장해야합니다. 예 :

(210)

return root = initNode(newValue); 

대신

return(initNode(newValue)); 

(당신은 또한 방법으로 괄호 안에 반환 값을 넣을 필요가 없습니다).

WhozCraig는 이미 재귀 호출 insert() 호출의 문제점을 지적했습니다.