带队列的二叉树级序遍历实现

Question

我正在尝试实现一个levelOrder函数，它接受树的指针并逐级打印树的数据。这是《C如何编程》一书中的一个问题，完整问题如下：

（级序二叉树遍历）Fig的程序。12.19说明了遍历二叉树的三种递归方法——顺序遍历、前序遍历和后序遍历。此练习演示了二叉树的级别顺序遍历，其中节点值从根节点级别开始逐级打印。每个级别上的节点从左到右打印。级序遍历不是递归算法。它使用队列数据结构来控制节点的输出。算法如下：

>

在队列中插入根节点

虽然队列中还有节点，

获取队列中的下一个节点

打印节点的值

如果指向节点左子节点的指针不为NULL，请在队列中插入左子节点

如果指向节点的右子节点的指针不为NULL，请在队列中插入右子节点。

写入函数levelOrder以执行二叉树的级别顺序遍历。该函数应将指向二叉树根节点的指针作为参数。修改图12.19的程序以使用此功能。将此函数的输出与其他遍历算法的输出进行比较，以确定其工作是否正确。[注：您还需要在本程序中修改和合并图12.13中的队列处理功能。]

我的尝试如下：

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

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

struct queueNode{
    struct treeNode* tree;
    struct queueNode* next;
};


/* prototype */
void insert(struct treeNode**, int); // tree creator
void levelOrder(struct treeNode**);
void inOrder(struct treeNode*);
void enqueue(struct queueNode**, struct queueNode**, struct treeNode*);
struct treeNode* dequeue(struct queueNode**, struct queueNode**);

int main(){
    struct treeNode* root = NULL;
    levelOrder(&root);
}

void insert(struct treeNode** root, int val){
    if(!(*root)){ // when root is empty
        *root = (struct treeNode*)malloc(sizeof(struct treeNode));
        if(*root){ // if allocation is achieved
            (*root) -> data = val;
            (*root) -> right = NULL;
            (*root) -> left = NULL;
        } else { // if allocation is not succesfull
            printf("%s\n", "[ERROR] Not enough memory space for allocation!");
        }
    } else { // if root is not empty
        if(val > (*root) -> data)
            insert(&(*root) -> right, val);
        else if(val < (*root) -> data)
            insert(&(*root) -> left, val);
    }
}

void enqueue(struct queueNode** head, struct queueNode** tail, struct treeNode* tree){
    struct queueNode* newNode = (struct queueNode*)malloc(sizeof(struct queueNode));
    if( newNode ){
        newNode -> tree = tree;
        newNode -> next = NULL;
        if(!(*head)){
            *head = newNode;
            //printf("head->tree->data:%d --> ", (*head)->tree->data);
            printf("%d --> ", (*head)->tree->data);
        }
        else{
            (*tail) -> next = newNode;
            //printf("tail->tree->data:%d --> ", (*tail)->tree->data);
            printf("%d --> ", (*tail)->tree->data);
        }
        (*tail) = newNode;
    } else {
        printf("%s\n", "[ERROR] Not enough memory space for allocation!");
    }
}

struct treeNode* dequeue(struct queueNode** head, struct queueNode** tail){
    struct treeNode* val = (*head)->tree;
    struct queueNode* temp = *head;
    *head = (*head) -> next;
    if(!(*head))
        *tail = NULL;
    return val;
}

void levelOrder(struct treeNode** root){
    struct treeNode* output = NULL;
    struct queueNode* head = NULL, *tail = NULL;
    size_t i;
    srand(time(NULL));
    for(i = 0; i < 9; ++i){
        insert(root, 1 + rand()%16);
    }
    puts("in order");
    inOrder(*root);
    puts("NULL");
    puts("After in order");
    enqueue(&head, &tail, *root);
    while(head){
        if(head->tree->left)
            enqueue(&head, &tail, head->tree->left);
        if(head->tree->right)
            enqueue(&head, &tail, head->tree->right);
        head = head->next;
    }


    /*for(i=0;i<9;++i){
       output = dequeue(&head, &tail);
       printf("%d",output->data);
    }*/
}

void inOrder(struct treeNode* tree){ // used to be sure if my implementation works correct
    if(tree != NULL){
        inOrder(tree->left);
        printf("%-2d-->", tree->data);
        inOrder(tree->right);
    }
}

当我使用退出函数时，它不能正常工作。我不能得到队列中的所有树与队列函数。但是，如果我打印队列中的值，它会打印所有添加的值，除了一个（我不打印哪个），但会打印第一个值两次。（你能运行代码吗？我想把输出放在这里，但stackoverflow认为它是一个代码块，我不能编辑它，所以它不让我添加它。（

Answer 1

一些问题：

>

在enqueue中的else块中，在移动tail之前打印该值：这可能会误导输出的读取器，因为该值不是附加到队列中的值。我假设这是为了调试，但最后不应该在这里打印。

在主循环中，您不应该像那样移动head引用。取而代之的是在循环开始时使用de队列，并捕获您已经声明的输出变量中的节点，并立即打印相应的值。这将保持队列的大小不超过必要的长度。

while(head){
    output = dequeue(&head, &tail); // extract
    printf("%d --> ", output->data); // print here instead of in enqueue
    if(output->left) // use output
        enqueue(&head, &tail, output->left);
    if(output->right)
        enqueue(&head, &tail, output->right);
    // Don't move head here
}
puts("\n");

在dequeue中，您应该在return之前释放从队列中删除的队列节点：

free(temp);

其他一些评论：

>

evelOrder不应该真正负责构建树。在主驱动程序代码中执行此操作，或者--如果您真的想要--在单独的函数中执行此操作。然后将第二个参数设为evelOrder，只需struct treeNode*，而不是struct treeNode**。

对于调试，您的inOrder实现将值打印在单独的行上，并使用对应于递归深度的缩进，对此您可以传递一个额外的int深度参数。这样你就可以看到实际的树结构。