二进制搜索树插入不起作用 [英] Binary Search Tree insertion doesn't work

问题描述

我正在看书《问题解决与解决》.使用C进行程序设计，以学习C.在本书中，他们给出了构建二进制搜索树的所有必要部分. 但是，我的实现没有用.这是插入部分；

I am following a book ,Problem Solving & Program Design in C, to learn C. In this book, they gave all necessary parts to build a binary search tree.... But, My implementation didn't work. Here is insertion part;

void
add_to_t(tree_node_t *oldTreep, // input/output - binary search tree
        tree_element_t ele)       // input - element to add
{
    oldTreep = tree_insert(oldTreep, ele);
}
tree_node_t * tree_insert(tree_node_t *oldTreep, tree_element_t ele)
{
    if(oldTreep == NULL){
        oldTreep = TYPED_ALLOC(tree_node_t);
        strcpy(oldTreep->element.name, ele.name);
        strcpy(oldTreep->element.sName, ele.sName);
        oldTreep->element.seatClass = ele.seatClass;
        oldTreep->leftp = NULL;
        oldTreep->rightp = NULL;
    }
    else if (strcmp(oldTreep->element.name, ele.name)==0){
        /* duplicate key - no insertion */
    }
    else if (strcmp(oldTreep->element.name, ele.name)>0){
        oldTreep->rightp = tree_insert(oldTreep->rightp, ele);
    }
    else
    {
        oldTreep->leftp = tree_insert(oldTreep->leftp, ele);
    }
    return(oldTreep);

}

我的scan_passenger函数(我正在从此函数调用的结果中传递ele)；

My scan_passenger funvtion(I am passing ele from result of this function call);

void scan_passenger(tree_element_t *pass)
{
    char passName[10], passSname[10];
    int classNum;
    printf("\nEnter the Name of passenger to add the binary search tree> ");
    scanf("%s", passName);
    printf("Enter the Surname of passenger to add the binary search tree> ");
    scanf("%s", passSname);
    printf("Enter the class number of passenger to add the binary search tree> ");
    scanf("%d", &classNum);
    strcpy(pass->name, passName);
    strcpy(pass->sName, passSname);
    pass->seatClass = classNum;
}

还有我的typdef和标头；

And my typdefs and headers if needs;

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define TYPED_ALLOC(type) (type *)malloc(sizeof (type))
typedef struct tree_element_s {
    char name[10];
    char sName[10];
    int seatClass;
}tree_element_t;

typedef struct tree_node_s {
    tree_element_t element;
    struct tree_node_s *leftp, *rightp;
}tree_node_t;

我的问题是它没有创建二进制搜索树的根.当我尝试向堆中添加新元素时，它似乎会创建一个新节点.当我跟踪代码时，似乎此函数的每个实例都返回NULL.我想说的是每次我调用tree_insert时，如果语句(认为root为NULL)首先出现…… 对不起，我的英语不好.在谈论编码术语时，我可能会犯一些错误(可能是因为，在缺席1年后我从那本书重新学习了C，所以我可能将它们混在一起) 预先感谢.

My problem is that it doesn't create a root of binary search tree. When I try to add a new element to heap, it seems, it creates a new node. When I traced my code, it seems every instance of this functions returns NULL. I am trying to say every time when I call tree_insert, it goes first if statement(Thinks root is NULL)... Sorry for my bad English. And I may made some mistake when talking about coding terminology(it may because, I returned to study C from that book after absence of 1 year.So I may mixed them) Thanks in advance.

推荐答案

在add_to_t中，您更新了oldTreep，但是由于它是一个局部变量，所以新值在离开函数后就立即丢失.

In add_to_t, you update oldTreep, but since it is a local variable, the new value gets lost as soon as you leave the function.

例如，您可以将oldTreep的新值返回给调用者，调用者将使用返回值更新 his oldTreep

You could, e.g., return the new value of oldTreep to the caller, which updates his oldTreep with the return value

tree_node_t
add_to_t(tree_node_t *oldTreep, // input/output - binary search tree 
        tree_element_t ele)       // input - element to add 
{ 
    return tree_insert(oldTreep, ele); 
} 

...

myRootOfTheTree = add_to_t (myRootOfTheTree, element);

另一种解决方案是在树中始终有一个虚拟元素.

Another solution is to always have one dummy element in the tree.

这篇关于二进制搜索树插入不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！