数据结构：基于队列的二叉树深度计算（层次遍历实现）

队列代码实现 + 注释（迭代复制二叉树要用到）

//创建一个空队列 //return 指向新队列的指针 Queue* CreateQueue() { Queue* newQueue = (Queue*)malloc(sizeof(Queue)); if (newQueue == NULL) { printf("队列创建失败\n"); exit(1); } newQueue->front = newQueue->rear = NULL; return newQueue; }

//判断队列是否为空 //return 1：为空 0：不为空 int isQueueEmpty(Queue* q) { return q->front == NULL; }

//将一个树节点入队 void enQueue(Queue* q, TreeNode* TNode) { QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newQueueNode == NULL) { printf("新节点分配内存失败\n"); exit(1); } newQueueNode->treeNode = TNode; newQueueNode->next = NULL;

//队列是否为空，若为空，则将头指针、尾指针修改为新节点的地址
if (isQueueEmpty(q)) {
    q->front = newQueueNode;
    q->rear = newQueueNode;
}
else {
    //队列不为空，将新节点入队，尾指针后移一位
    q->rear->next = newQueueNode;
    q->rear = newQueueNode;
}

}

//将队头的树节点出队 //返回出队的树节点指针 TreeNode* deQueue(Queue* q) { if (isQueueEmpty(q)) { return NULL; }

QueueNode* temp = q->front;
TreeNode* treeNode = temp->treeNode;

q->front = q->front->next;

//如果队列中只有一个元素，将队头、队尾指针置空，防止悬挂指针
if (q->front == NULL) {
    q->rear = NULL;
}

free(temp);
return treeNode;

}

//释放队列占用的内存 void freeQueue(Queue* q) { //先释放所有的队列结点 while (!isQueueEmpty(q)) { deQueue(q); } //再释放队列，将 q 指针赋值为 NULL，使他不指向任何有效的内存，而非已被释放的无效内存的地址 free(q); q = NULL; }

迭代计算二叉树深度代码实现 + 注释

//迭代计算二叉树深度 //当树的深度过大时，可能导致栈溢出 //用队列，无栈溢出风险，因为使用的是堆内存来存储队列 int calculateDepth(TreeNode* root) { if (root == NULL) return 0;

Queue* q = CreateQueue();
enQueue(q, root);

int depth = 0;

while (!isQueueEmpty(q)) {
    //当前层的结点数量
    int  = 
    QueueNode*  = q->front

    while (current != NULL) {
        levelSize++
         = current->next
    }

    for (int  = 
        TreeNode*  = deQueue(q)

        if (node->lchild != NULL) {
            enQueue(q, node->lchild)
        }
        if (node->rchild != NULL) {
            enQueue(q, node->rchild)
        }
    }
    //当前层处理完毕，深度 +1
    depth++
}
freeQueue(q)
return depth