將插入函數插入AVL樹不會插入

我正在使用字符串作爲鍵的avl樹上工作。打印語句指示插入正在發生，但在測試功能中，它報告根的左右節點保留爲空。將插入函數插入AVL樹不會插入

這裏是我的AVL樹代碼：

#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); 
     } 
    }

測試程序：

#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」左，右節點爲空。爲什麼是這樣？

來源

2014-11-23 tke

密切關注'insert'函數的返回值。當你調用'insert（root-> leftNode，newValue）'和'insert（root-> rightNode，newValue）;'這兩者當前都忽略結果時，你認爲這很重要嗎？ – WhozCraig 2014-11-23 01:53:07

謝謝你告訴我在哪裏看不到答案，它仍然花了我一分鐘哈哈。我仍然困難的時間圍繞遞歸功能。 – tke 2014-11-23 01:59:43

不用擔心。當你第一次接觸它時，遞歸是一件易變的事情。記住調用堆棧和/或返回值通常是在下降過程中「存儲」的地方，使得它們在出路後可以恢復。祝你好運。 – WhozCraig 2014-11-23 02:01:51

在search()功能，不知道爲什麼你做

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

如果node是外部的，也就是沒有任何的葉子，你仍然要比較其nodeValue到searchVal並返回root如果匹配。

在initNode()功能，下一個到的，最後一行應

newNode->count = 1;

，而不是

newNode->height = 1;

而且，在我看來，在insert()功能，initNode()的回報值應分配給root以將指針存儲到樹中新添加的node，即您應該有：

return root = initNode(newValue);

，而不是

return(initNode(newValue));

（你還沒有的方式把返回值在括號中）。

WhozCraig已經指出遞歸insert()調用的返回值的問題。

來源

2014-11-23 02:33:09

將插入函數插入AVL樹不會插入

回答

相關問題