树数据结构 (level_order)

Question

我正在学习有关 preorder、postorder、inorder 和 level_order 的树数据结构。这些代码是C写的。当我在dequeue方法中将temp -> item分配给element item时，报错。但我认为 struct 指针可以节省另一个 struct 指针！我该如何解决

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

typedef struct QueueNode {
    int item;
    struct QueueNode *link; 
} QueueNode;
typedef struct {
    QueueNode *front, *rear;
} QueueType;

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

typedef TreeNode * element;


void error(char *message)
{
fprintf(stderr,"%s\n",message);
exit(1);
}


void init(QueueType *q)
{
    q->front = q->rear = 0;
}

int is_empty(QueueType *q)
{
    return (q->front==NULL);
}

int is_full(QueueType *q)
{
    return 0;
}

void enqueue(QueueType *q, element item)
{ 
    QueueNode *temp=(QueueNode *)malloc(sizeof(QueueNode)); 
    if(temp == NULL )
        error("error");
    else {
        temp->item = item;
        temp->link = NULL;
        if( is_empty(q) ){
            q->front = temp;
            q->rear = temp;     
        }
        else {
            q->rear->link = temp;
            q->rear = temp; 
        }   
    }
}

element dequeue(QueueType *q) 
{ 
    QueueNode *temp = q -> front;
    element item; 
    if( is_empty(q) )
        error("error");
    else {
        item = temp->item;
        q->front = q->front->link;
        if( q->front == NULL )
        q->rear = NULL;
        free(temp);
        return item;
    }
} 


void level_order(TreeNode *ptr)
{
    QueueType q;

    init(&q);
    if( !ptr ) return;
    enqueue(&q, ptr);
    while(is_empty(&q)) {
        ptr = dequeue(&q);
        printf(" %d ", ptr->data);
        if( ptr->left )
            enqueue(&q, ptr->left);
        if( ptr->right )
            enqueue(&q, ptr->right);
    }
}

TreeNode n1={1,  NULL, NULL};
TreeNode n2={2,  &n1,  NULL};
TreeNode n3={4, NULL,  NULL};
TreeNode n4={8, NULL, NULL};
TreeNode n5={10, NULL, NULL};
TreeNode n6={6, NULL, NULL};
TreeNode n7={9, &n4,  &n5};
TreeNode n8={7, &n6, &n7};
TreeNode n9={3, &n2,  &n3};
TreeNode n10={5, &n9,  &n8};
TreeNode *root= &n10;



void main()
{
    level_order(root);

}

Answer 1

在你的函数dequeue中，这个赋值-

item = temp->item;

item 是指向结构 TreeNode 的指针，但 temp->item 是整数变量。编译器显然会报错（ 并不知道你试图完成什么）。

Answer 2

这是正确的出队方式：

int dequeue(QueueType *q)
{
    QueueNode *temp = q -> front;
    int item;
    if( is_empty(q) )
        error("error");
    else {
        item = temp->item;
        q->front = q->front->link;
        if( q->front == NULL )
            q->rear = NULL;
        free(temp);
        return item;
    }

    return 0;
}

您应该 return 的数据类型是 int。

Answer 3

您正在尝试将结构 temp->item 的成员分配给 dequeue 中的结构 item 并将结构 item 的成员分配给enqueue 中的结构 temp->item。

出队： 这里是 returning 类型 int，更改 return 类型 element到int（item = temp->item;这个说法是不正确的）。所以这是正确的出队方式。

int  dequeue(QueueType *q) 
{ 
    QueueNode *temp = q -> front;
    element item; 
    if( is_empty(q) )
        error("error");
    else {
        item->data = temp->item;
        q->front = q->front->link;
        if( q->front == NULL )
        q->rear = NULL;
        free(temp);
        return item;
    }
}

入队：使用此函数入队（temp->item = item;此说法不正确）：

void enqueue(QueueType *q, element item)
{ 
    QueueNode *temp=(QueueNode *)malloc(sizeof(QueueNode)); 
    if(temp == NULL )
        error("error");
    else {
        temp->item = item->data;
        temp->link = NULL;
        if( is_empty(q) ){
            q->front = temp;
            q->rear = temp;     
        }
        else {
            q->rear->link = temp;
            q->rear = temp; 
        }   
    }
}

树数据结构 (level_order)

tree data structure (level_order)

c

tree

data-structures