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

Question

我正在尝试实现一个 levelOrder 函数，它获取树的指针并逐层打印树的数据。这是 C How to Program 一书中的问题，完整问题如下：

(Level Order Binary Tree Traversal) The program of Fig. 12.19 illustrated three recursive methods of traversing a binary tree—inorder traversal, preorder traversal, and postorder traversal. This exercise presents the level order traversal of a binary tree in which the node values are printed level-by-level starting at the root node level. The nodes on each level are printed from left to right. The level order traversal is not a recursive algorithm. It uses the queue data structure to control the output of the nodes. The algorithm is as follows:

Insert the root node in the queue

While there are nodes left in the queue,

Get the next node in the queue

Print the node’s value

If the pointer to the left child of the node is not NULL Insert the left child node in the queue

If the pointer to the right child of the node is not NULL
Insert the right child node in the queue.

Write function levelOrder to perform a level order traversal of a binary tree. The function should take as an argument a pointer to the root node of the binary tree. Modify the program of Fig. 12.19 to use this function. Compare the output from this function to the outputs of the other traversal algorithms to see that it worked correctly. [Note: You’ll also need to modify and incor- porate the queue-processing functions of Fig. 12.13 in this program.]

我的尝试如下：

#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);
    }
}

当我使用出队功能时，它无法正常工作。我无法使用出队功能获取队列中的所有树。但是，如果我打印 enqueue 中的值，它会打印除一个之外的所有添加值（我不打印哪个），但会打印第一个值两次。（你能运行代码吗？我想把输出放在这里，但Whosebug认为它是一个代码块，我不能编辑它所以它不让我添加它。）

Answer 1

一些问题：

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

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

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);
```

一些其他备注：

levelOrder 不应该真正负责构建树。在您的主要驱动程序代码中执行此操作，或者——如果您真的想要——在一个单独的函数中执行此操作。然后将 levelOrder 的第二个参数设为 struct treeNode * 而不是 struct treeNode **.
为了调试，您的 inOrder 实现将值打印在单独的行上，并带有与递归深度相对应的缩进，为此您可以传递一个额外的 int depth 参数。这样您就可以对实际的树结构有一些直观的了解。

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

Level Order Binary Tree Traversal Implementation with Queue

c

queue

binary-search-tree

data-structures