数据结构：构建完全二叉树

一、完全二叉树

`概念`

完全二叉树是一种特殊的二叉树，其结构特点为：从根节点开始，除最后一层外，每一层的节点都被完全填满；最后一层的节点则从左到右连续排列，没有间隙（即该层左侧节点全存在，右侧可空缺）。

alt

`本文采用思路`

二叉树构建通常遵循 “层次优先” 原则：新节点按层次遍历顺序插入，优先填充当前层左侧未填满的节点（先左子节点，后右子节点），正是通过层次遍历找到第一个左或右子节点为空的节点，将新节点插入其中，从而保证树的完全性。

要使用“层次”原则，就要使用queue(队列)，通过队列对每层节点进行入队/出队操作，可以实现每层元素的检查以及遍历，也可以实现按完全二叉树的顺序插入节点。

二、详细代码实现

1.队列相关代码

queue.h

/*===============================================
*   文件名称：queue.h
*   创 建 者：青木莲华     
*   创建日期：2025年07月31日
*   描    述：链式队列
================================================*/
#ifndef __QUEUE_H__
#define __QUEUE_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"



typedef struct Node data_q;
typedef struct Node_q
{
    data_q *data;
    struct Node_q *next;
}node_t;

typedef struct
{
    struct Node_q *front,*rear;
}queue_t;

//create
queue_t *queue_create();
//empty
int is_empty(queue_t *q);
//length
int queue_length(queue_t *q);
//show
void queue_show(queue_t *q);
//en
int queue_en(queue_t *q,data_q *data);
//de
data_q *queue_de(queue_t *q);
#endif

queue.c

/*===============================================
*   文件名称：queue.c
*   创 建 者：青木莲华    
*   创建日期：2025年07月31日
*   描    述：链式队列
================================================*/
#include "queue.h"

//create
queue_t *queue_create()
{
    queue_t *q = (queue_t *)malloc(sizeof(queue_t));
    if(q == NULL)
        return NULL;
    node_t *head = (node_t *)malloc(sizeof(node_t));
    if(head == NULL)
    {
        free(q);
        return NULL;
    }
    head->next = NULL;
    q->front = head;
    q->rear = head;
    return q;
}
//empty
int is_empty(queue_t *q)
{
    return q->front->next == NULL;
}
//length
int queue_length(queue_t *q)
{
    int count = 0;
    node_t *p = q->front->next;
    while(p != NULL)
    {
        count++;
        p = p->next;
    }
    return count;
}
//show
void queue_show(queue_t *q)
{
    if(is_empty(q))
    {
        printf("队已空!\n");
        return;
    }
    node_t *p = q->front->next;
    while(p != NULL)
    {
        //printf("%4d ",p->data);
        p = p->next;
    }
    printf("\n");
}
//en
int queue_en(queue_t *q,data_q *data)
{
    node_t *new = (node_t *)malloc(sizeof(node_t));
    if(new == NULL)
        return 0;
    new->next = NULL;
    new->data = data;
    q->rear->next = new;
    q->rear = new;
    return 1;
}
//de
data_q *queue_de(queue_t *q)
{
    if(is_empty(q))
    {
        printf("队已空!\n");
        return 0;
    }
    node_t *p = q->front;
    q->front = q->front->next;
    free(p);
    return q->front->data;
}

2.树的相关代码

tree.h

/*===============================================
*   文件名称：tree.h
*   创 建 者：青木莲华     
*   创建日期：2025年08月01日
*   描    述：自动插入完全二叉树
================================================*/

#ifndef __TREE_H__
#define __TREE_H__

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

typedef char data_t;

typedef struct Node
{
    data_t data;
    struct Node *lchild, *rchild;
}tree_t;

//create
tree_t *tree_create();
//自动插入到合适位置（构成完全二叉树）
int tree_insert(tree_t *root , data_t x);
//层次遍历
void level_order(tree_t *root);

#endif

tree.c

/*===============================================
*   文件名称：tree.c
*   创 建 者：青木莲华     
*   创建日期：2025年08月01日
*   描    述：自动构建完全二叉树
================================================*/
#include "tree.h"


//创建根节点
tree_t *tree_create()
{
    data_t data = 'A';
    tree_t *root = (tree_t *)malloc(sizeof(tree_t));
    if(root == NULL)
        return NULL;
    root->data = data;
    printf("%c ---->  root\n",root->data);
    return root;
}


//插入按照层次遍历的方法  每一层都判断是否所有节点都有左右子节点，没有则插入到该位置
int tree_insert(tree_t *root , data_t x)
{
    if(root == NULL)
        return 0;
    queue_t *q = queue_create();
    if(q == NULL)
        return 0;
    queue_en(q,root); 
    tree_t *temp = NULL;
    while(!is_empty(q))
    {
        temp = queue_de(q);             //进行出队操作
        if(temp->lchild != NULL)        //左子结点不为空 入队
            queue_en(q,temp->lchild);
		else							//左子节点为空，插入到该位置
		{
        	temp->lchild = (tree_t *)malloc(sizeof(tree_t));
        	temp->lchild->data = x;
            temp->lchild->lchild = NULL;
            temp->lchild->rchild = NULL;
            printf("%c ---->  tree\n",temp->lchild->data);
            return 1;
        }
        if(temp->rchild != NULL)        //右子结点不为空 入队
            queue_en(q,temp->rchild);
		else							//右字节点为空，插入到该位置
		{
    	    temp->rchild = (tree_t *)malloc(sizeof(tree_t));
	        temp->rchild->data = x;
            temp->rchild->lchild = NULL;
            temp->rchild->rchild = NULL;
            printf("%c ---->  tree\n",temp->rchild->data);
	        return 1;
        }
    }
    free(q);
}

//层序遍历  利用队列实现
void level_order(tree_t *root)
{
    if(root == NULL)
        return;
    queue_t *q = queue_create();
    if(q == NULL)
        return;
    //先将根节点入队
    queue_en(q,root);
    tree_t *temp = NULL;
    printf("层次遍历:\n");
    //用循环进行入队出队操作    队为空表示所有结点遍历完毕
    while(!is_empty(q))
    {
        temp = queue_de(q);             //进行出队操作
        if(temp->lchild != NULL)        //左子结点不为空 入队
            queue_en(q,temp->lchild);
        if(temp->rchild != NULL)        //右子结点不为空 入队
            queue_en(q,temp->rchild);
        printf("%c ",temp->data);       //打印当前结点的值
    }
    printf("\n");
    free(q);
}

3.主函数以及运行结果

main.c

/*===============================================
*   文件名称：main.c
*   创 建 者：青木莲华     
*   创建日期：2025年08月01日
*   描    述：自动实现完全二叉树
================================================*/
#include "tree.h"



void main()
{
	tree_t *root = tree_create();
    char c = 'B';
    for(int i = 0 ; i < 20 ; i++)
        tree_insert(root,c + i);
    //遍历
    level_order(root);
	
}

运行结果

alt

数据结构：构建完全二叉树(含代码及思路)