使用层次遍历创建二叉树，用C语言实现

╰半橙微兮° 2024-03-27 12:54 77阅读 0赞

层次遍历二叉树是指从上到下，从左到右依次遍历二叉树的每一层节点。

下面是一个使用队列实现层次遍历二叉树的 C 语言代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
    } TreeNode;
    
    typedef struct Queue {
      TreeNode **nodes;
      int head;
      int tail;
      int size;
    } Queue;
    
    Queue* createQueue(int size) {
      Queue *q = (Queue*)malloc(sizeof(Queue));
      q->nodes = (TreeNode**)malloc(sizeof(TreeNode*) * size);
      q->head = 0;
      q->tail = 0;
      q->size = size;
      return q;
    }
    
    int isEmpty(Queue *q) {
      return q->head == q->tail;
    }
    
    int isFull(Queue *q) {
      return q->tail == q->size;
    }
    
    void enqueue(Queue *q, TreeNode *node) {
      if (isFull(q)) {
        q->size *= 2;
        q->nodes = (TreeNode**)realloc(q->nodes, sizeof(TreeNode*) * q->size);
      }
      q->nodes[q->tail++] = node;
    }
    
    TreeNode* dequeue(Queue *q) {
      if (isEmpty(q)) {
        return NULL;
      }
      return q->nodes[q->head++];
    }
    
    void levelOrder(TreeNode *root) {
      if (root == NULL) {
        return;
      }
      Queue *q = createQueue(10);
      enqueue(q, root);
      while (!isEmpty(q)) {
        TreeNode *node = dequeue(q);
        printf("%d ", node->val);
        if (node->left != NULL) {
          enqueue(q, node->left);
        }
        if (node->right != NULL) {
          enqueue(q, node->right);
        }
      }
    }
    
    int main() {
      // 创建二叉树的代码省略
      levelOrder(root);
      return 0;
    }

在这段代码中，我们使用了一个结构体来表示二叉树的节点，另外还使用了一个结构体来表示队列。队列是一