createBinaryTree 给出无限循环，createBinarySearchTree 给出分段错误

Question

createBinaryTree 给出无限循环，createBinarySearchTree 给出分段错误。有人可以指导我吗，因为我对数据结构还很陌生。

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

typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} * NODE;

NODE createBinaryTree(NODE root)
{
    NODE temp = (NODE)malloc(sizeof(struct node));
    printf("Enter the value of the node. \n Enter -1 for returning. \n");
    scanf(" %d", &temp->data);
    if (temp->data == -1)
        return NULL;
    else
    {
        printf("For left Node of %d \n", temp->data);
        temp->lchild = createBinaryTree(temp->lchild);
        printf("For right Node of %d \n", temp->data);
        temp->rchild = createBinaryTree(temp->rchild);
    }
    return temp;
}
NODE createBinarySearchTree(NODE root, int ele)
{
    NODE new_node;
    new_node = (NODE)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->lchild = new_node = NULL;

    if (root == NULL)
        return new_node;

    NODE parent = NULL;
    NODE curr = root;

    while (curr != NULL)
    {
        parent = curr;
        if (curr->data < ele)
            curr = curr->rchild;
        else
            curr = curr->lchild;
    }

    if (ele < parent->data)
        parent->lchild = new_node;
    else
        parent->rchild = new_node;

    return root;
}

void inorder(NODE ptr)
{
    if (ptr != NULL)
    {
        inorder(ptr->lchild);
        printf("%5d", ptr->data);
        inorder(ptr->rchild);
    }
}

void postorder(NODE ptr)
{
    if (ptr != NULL)
    {
        postorder(ptr->lchild);
        postorder(ptr->rchild);
        printf("%5d", ptr->data);
    }
}

void preorder(NODE ptr)
{
    if (ptr != NULL)
    {
        printf("%5d", ptr->data);
        preorder(ptr->lchild);
        preorder(ptr->rchild);
    }
}

void main()
{
    NODE root = NULL;

    printf("Enter 0.createBinaryTree \n");
    printf("Enter 1.createBinarySearchTree \n");
    printf("Enter 2.displayTree \n");
    printf("Enter 3.searchTree \n");

    int choice;
    printf("Enter your choice\n");
    scanf(" %d", &choice);

    int tempvalue;

    while (1)
    {
        switch (choice)
        {
        case 0:
            root = createBinaryTree(root);
            break;

        case 1:
            printf("Enter Root Node\n");
            scanf(" %d", &tempvalue);
            while (tempvalue != -1)
            {
                root = createBinarySearchTree(root, tempvalue);
                break;
                printf("Enter Next Node.\n Enter -1 to exit\n");
                scanf(" %d", &tempvalue);
            }
            break;

        case 2:
            printf("\n Inorder Traversals \n");
            inorder(root);
            printf("\n Postorder Traversals \n");
            postorder(root);
            printf("\n Preorder Traversals \n");
            preorder(root);
            printf("\n ********* \n");
            break;
        case 4:
            exit(0);
        }
    }
}

Answer 1

对于您的 createBinaryTree 函数

问题出在行 scanf(" %d", &temp->data);当您到达树的根部时，然后在根部上方的节点上再次调用创建二叉树，然后覆盖您之前的条目。要解决此问题，您应该在将其分配给 temp->data 之前检查 scanf 的值。此外，您需要 return root，而不是 -1 上的 return NULL，以防在上一次迭代中设置 root。类似于以下内容。

编辑

typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} * NODE;

NODE createBinaryTree(NODE root)
{
    printf("Enter the value of the node. \n Enter -1 for returning. \n");
    int input = 0; 
    scanf(" %d", &input);
    printf("%d\n",input );
    if(input == -1 && root == NULL){
        return NULL;
    }
    if(input == -1 && root != NULL){
        return root;
    }
    NODE temp = (NODE)malloc(sizeof(struct node));
    temp->data = input;
    if (temp->data == -1)
        return NULL;
    else
    {
        printf("For left Node of %d \n", temp->data);
        temp->lchild = createBinaryTree(temp->lchild);
        printf("For right Node of %d \n", temp->data);
        temp->rchild = createBinaryTree(temp->rchild);
    }
    return temp;
}
NODE createBinarySearchTree(NODE root, int ele)
{
    NODE new_node;
    new_node = (NODE)malloc(sizeof(struct node));
    new_node->data = ele;

    new_node->lchild = new_node;

    if (root == NULL)
        return new_node;

    NODE parent = NULL;
    NODE curr = root;

    while (curr != NULL)
    {
        parent = curr;
        if (curr->data < ele)
            curr = curr->rchild;
        else
            curr = curr->lchild;
    }

    if (ele < parent->data)
        parent->lchild = new_node;
    else
        parent->rchild = new_node;

    return root;
}

void inorder(NODE ptr)
{
    if (ptr != NULL)
    {
        inorder(ptr->lchild);
        printf("%5d", ptr->data);
        inorder(ptr->rchild);
    }
}

void postorder(NODE ptr)
{
    if (ptr != NULL)
    {
        postorder(ptr->lchild);
        postorder(ptr->rchild);
        printf("%5d", ptr->data);
    }
}

void preorder(NODE ptr)
{
    if (ptr != NULL)
    {
        printf("%5d", ptr->data);
        preorder(ptr->lchild);
        preorder(ptr->rchild);
    }
}

int main()
{
    NODE root = NULL;

    printf("Enter 0.createBinaryTree \n");
    printf("Enter 1.createBinarySearchTree \n");
    printf("Enter 2.displayTree \n");
    printf("Enter 3.searchTree \n");

    int choice;
    printf("Enter your choice\n");
    scanf(" %d", &choice);

    int tempvalue;

    while (1)
    {
        switch (choice)
        {
        case 0:
            root = createBinaryTree(root);
            printf("Done\n");
            return 0;

        case 1:
            printf("Enter Root Node\n");
            scanf(" %d", &tempvalue);
            while (tempvalue != -1)
            {
                root = createBinarySearchTree(root, tempvalue);
                break;
                printf("Enter Next Node.\n Enter -1 to exit\n");
                scanf(" %d", &tempvalue);
            }
            return 0;

        case 2:
            printf("\n Inorder Traversals \n");
            inorder(root);
            printf("\n Postorder Traversals \n");
            postorder(root);
            printf("\n Preorder Traversals \n");
            preorder(root);
            printf("\n ********* \n");
            return 0;
        case 4:
            exit(0);
        }
    }
    return 0;
}

Answer 2

对于 BinarySearchTree。在第一次迭代中，您在每次迭代中都将新节点设置为 NULL。最好先检查节点的值，然后再决定遍历树的方向。当您点击根节点时，添加节点。像下面这样的东西。

将root单独输入，以便下一个输入进行比较。

        case 1:
        printf("Enter Root Node\n");
        scanf(" %d", &tempvalue);
        NODE root;
        root = (NODE)malloc(sizeof(struct node));
        root->data = tempvalue;
        while (tempvalue != -1)
        {   
            printf("Enter Node Value\n");
            scanf(" %d", &value);
            if(value == -1){
                break;
            }
            root = createBinarySearchTree(root, value);
        }
        return 0;

然后在函数内部，遍历树，直到找到节点应该去的地方。

NODE createBinarySearchTree(NODE root, int ele)
{
    NODE new_node;
    new_node = (NODE)malloc(sizeof(struct node));
    new_node->data = ele;

    if (root == NULL)
        return new_node;

    NODE curr = root;

    while (curr != NULL)
    {
        printf("%d\n",curr->data);
        if(ele < curr->data )
        {
            if(curr->lchild == NULL){
                printf("inserted %d as left child of %d\n",ele,curr->data );
                curr->lchild = new_node;
                return root;
            }
            curr=curr->lchild;
        }
        else if(ele > curr->data)
        {
            if(curr->rchild == NULL){
                printf("inserted %d as right child child of %d\n",ele,curr->data );
                curr->rchild = new_node;
                return root;
            }
             curr=curr->rchild;
        }
    }
    return root;
}

createBinaryTree 给出无限循环，createBinarySearchTree 给出分段错误

createBinaryTree is giving an infinite Loop and createBinarySearchTree is giving segmentation Fault

tree

binary-tree

tree-traversal

binary-search-tree

data-structures