一些元素没有被添加到二叉搜索树中

Question

我正在用 doubly-linked-list 在 C 中实现二叉搜索树。我没有得到预期的输出。 一些元素没有被添加到树中，特别是一些正确的孩子。

我需要帮助来解决这个问题。这是我的代码，

struct node{
    int data;
    struct node *left;
    struct node *right;
};

struct node *root=NULL;
struct node *temp=NULL;

struct node* createnode(int data){
    struct node *newNode= (struct node*)malloc(sizeof(struct node));
    newNode->data= data;
    newNode->left= NULL;
    newNode->right= NULL;

    return newNode;
}

void createBinaryTree(){
    int arr[100],size,i;
    printf("Enter no.of elements:");
    scanf("%d",&size);
    printf("\nEnter elements:");
    for(i=0;i<size;++i){
        scanf("%d",&arr[i]);
    }
    root= createnode(arr[0]);
    for(i=1;i<size;i++){
        temp=root;
        while(arr[i]>(temp->data)){
            if(temp->right==NULL){
                temp->right=createnode(arr[i]);
                continue;
            }
            temp=temp->right;
            
        }
        while(arr[i]<(temp->data)){
            if(temp->left==NULL){
                temp->left=createnode(arr[i]);
                continue;
            }
            temp=temp->left;
            
        }
    }
}

Answer 1

您的代码：

struct node{
    int data;
    struct node *left;
    struct node *right;
};

struct node *root=NULL;
struct node *temp=NULL;

struct node* createnode(int data){
    struct node *newNode= (struct node*)malloc(sizeof(struct node));
    newNode->data= data;
    newNode->left= NULL;
    newNode->right= NULL;

    return newNode;
}

void createBinaryTree(){
    int arr[100],size,i;
    printf("Enter no.of elements:");
    scanf("%d",&size);
    printf("\nEnter elements:");
    for(i=0;i<size;++i){
        scanf("%d",&arr[i]);
    }
    root= createnode(arr[0]);
    for(i=1;i<size;i++){
        temp=root;
        while(arr[i]>(temp->data)){
            if(temp->right==NULL){
                temp->right=createnode(arr[i]);
                continue;
            }
            temp=temp->right;
            
        }
        while(arr[i]<(temp->data)){
            if(temp->left==NULL){
                temp->left=createnode(arr[i]);
                continue;
            }
            temp=temp->left;
            
        }
    }
}

有些元素被跳过的原因是你添加的方式不对。那 2 个 while 循环就是问题所在。

假设你有这棵树：

你想输入数字 6。

您的第一个时间将被跳过。

然后用你的第 2 个 while 去到编号为 5 的节点。

在那之后你将退出那个 while 并且什么都不会发生。

你不会到达那个 NULL。

因此，要毫无问题地添加节点，只需使用一个 while 循环，只要未达到 NULL，该循环就会起作用，并在该循环内使用一个 if 语句来检查您必须在每个节点中遵循哪条路径。

一些元素没有被添加到二叉搜索树中

Some of the elements are not getting added to the Binary Search Tree

c

linked-list

binary-tree

binary-search-tree

doubly-linked-list