c - 如何修复未打印树中节点的错误

Question

我正在尝试将 4 个名称插入到 bst 中。我有打印语句，说明名称在树上经过的位置，然后有一个打印语句，当名称找到有效位置时输出“null”。例如:

如果根是 Dennis 并且下一个插入的节点是 Armin，则打印

左 空

但是，当我尝试按顺序打印树时，我缺少一个名称。

我尝试手动打印节点，就像 printf("%s", node->data); 那样但我只是遇到了段错误。

我要打印的名字是 apple、cris、dennis、loki。但输出是:apple、cris、loki。它总是跳过丹尼斯。

bstNode* insertNode(bstNode *root, char *data){

    if(root == NULL){
        printf("null, %s\n", data);

        root = newNode(data);
        return;
        }

    else if(wordSort(root->data, data) == -1){
        printf("right, %s\n", data);
        root->right = insertNode(root->right, data);
    }
    else if(wordSort(root->data, data) == 1){
        printf("left, %s\n", data);
        root->left = insertNode(root->left, data);
    }
}

  void printTree(bstNode *node){
//printf("%s\n", node->left->data);
//printf("%s\n", node->data);
//printf("%s\n", node->right->data);
//printf("%s\n", node->right->right->data);


 if (node == NULL)
          return;

     printTree(node->left);


     printf("%s\n", node->data);


     printTree(node->right);

}

bstNode* newNode(char *data){

bstNode* newnode = (bstNode*)malloc(sizeof(bstNode));
newnode->data =  (char*)malloc(100 * sizeof(char));
strcpy(newnode->data, data);
newnode->left = NULL;
newnode->right = NULL;
strcpy(newnode->data, data);
newnode->count = 1;
return newnode;
}

Answer 1

函数 insertNode 具有未定义的行为，因为它没有返回任何内容，尽管它的返回类型为 bstNode *。

可以按如下方式定义和调用，如演示程序所示。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct bstNode
{
    char *data;
    struct bstNode *left;
    struct bstNode *right;
} bstNode;

bstNode * newNode( const char *data )
{
    bstNode *node = malloc( sizeof( bstNode ) );

    if ( node != NULL )
    {
        node->left  = NULL;
        node->right = NULL;

        size_t n = strlen( data );
        node->data = malloc( n + 1 );

        if ( node->data != NULL )
        {
            strcpy( node->data, data );
        }
        else
        {
            free( node );
        }
    }

    return node;
}

bstNode * insertNode( bstNode *root, const char *data )
{
    if ( root == NULL )
    {
        root = newNode( data );
    }
    else if ( strcmp( root->data, data ) < 0 )
    {
        root->left = insertNode( root->left, data );
    }
    else
    {
        root->right = insertNode( root->right, data );
    }

    return root;
}

void printTree( const bstNode *root )
{
    if ( root != NULL )
    {
        printTree( root->left );
        puts( root->data );
        printTree( root->right );
    }
}
int main(void) 
{
    bstNode *root = NULL;

    root = insertNode( root, "pple" );
    root = insertNode( root, "cris" );
    root = insertNode( root, "dennis" );
    root = insertNode( root, "lok" );

    printTree( root );

    return 0;
}

程序输出为

pple
lok
dennis
cris