0

我一直在研究二叉搜索树及其几个用于学校作业的功能实现。我刚刚编写了广度优先搜索函数，但在我的 queueenter 函数的 else 语句中出现了分段错误。

谁能给我任何关于我需要做什么来完善我的实现的指示？

这是代码：

/*This code will implement a binary search tree based on 20
user-inputed integers. It will then implement a search,
insert, delete, and traverse function. */

#include <stdio.h>
#include <stdlib.h>
#define ARRSIZE 20

/*------ TYPE DEFINITIONS ------*/

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

typedef struct tree
{
    int count;
    struct node* root;
} tree;

typedef struct queue
{
    int count;
    struct node* front;
    struct node* rear;
} queue;

/*------ FUNCTION DECLARTATIONS ------*/

void InitializeTree (tree* ptree);
int insert (int data, tree* ptree);
void place (node* root, node* new_node);
void BreadthFirst (tree* ptree);
node* queuedelete (queue* pq);
void queueenter (queue* pq, node* pn);
int queueisempty(queue* pq);

/*------ MAIN FUNCTION ------*/

int main (void)
{
    int i, arr[ARRSIZE];
    tree BST;

    InitializeTree(&BST);

    printf("Enter 20 integers for a list.\n");

    for(i=0; i<ARRSIZE; i++)
    {
        printf("Integer %d:\n", i+1);
        scanf("%d", &arr[i]);

        if(insert(arr[i], &BST) == 0)
        {
            printf("Error in creating node.\n");
            exit(1);
        }
    }
    BreadthFirst(&BST);

    return 0;
}

/*
* ADDITIONAL FUNCTIONS
*
*/

/*------ CREATION FUNCTIONS ------*/

void InitializeTree (tree* ptree)
{
    ptree->count = 0;
    ptree->root = NULL;
}

int insert (int data, tree* ptree)
{
    node* new_node;

    new_node = (node*) malloc(sizeof(node));

    if(new_node == NULL)
    {
        printf("Couldn't create a node.\n");
        return 0;
    }
    new_node->data = data;

    ptree->count++;

    if(ptree->root == NULL)
    {
        ptree->root = new_node;
    }

    else
    {
        place(ptree->root, new_node);
    }

    return 1;
}

void place (node* root, node* new_node)
{
    if(new_node->data < root->data)
    {
        if(root->left == NULL)
        {
            root->left = new_node;
        }
        else
        {
            place(root->left, new_node);
        }
    }
    else
    {
        if(root->right == NULL)
        {
            root->right = new_node;
        }
        else
        {
            place(root->right, new_node);
        }
    }
}

/*------ TRAVERSAL FUNCTIONS ------*/

void BreadthFirst (tree* ptree)
{
    static int i;
    queue buff;
    node* temp;

    if(ptree->root == NULL)
    {
        return;
    }

    queueenter(&buff, ptree->root);

    while(!queueisempty(&buff))
    {
        temp = queuedelete(&buff);
        printf("Node% - %d\n", i++, temp->data);

        if(temp->left != NULL)
        {
            queueenter(&buff, temp->left);
        }

        if(temp->right != NULL)
        {
            queueenter(&buff, temp->right);
        }
    }

    free(&buff);
}

node* queuedelete (queue* pq)
{
    if(queueisempty(pq))
    {
        return NULL;
    }

    pq->front = pq->front->next;
    pq->count--;
    if(queueisempty(pq))
    {
        pq->rear = NULL;
        return NULL;
    }
    return pq->front;
}

void queueenter (queue* pq, node* pn)
{
    node* temp;

    if(queueisempty(pq))
    {
        pq->front =  pn;
    }

    else
    {
        pq->rear->next = pn;
    }
    pq->rear = pn;
    pq->count++;
}

int queueisempty(queue* pq)
{
    return pq->count == 0;
}

提前感谢您的帮助和耐心！

4

1 回答 1

1

第一次通过该函数时，您设置了 pq->front，但未初始化 pq->rear。第二次，你取消引用 pq->rear，因为它有一个随机值，所以会出现段错误。

于 2013-04-28T23:45:29.257 回答