数据结构：从队列到二叉树基础解析

这章讲解了队列的知识，树形结构的基本概念，以及二叉树的基础部分以及相关的概念，例如根据前序和中序，计算后序等

从队列到二叉树 数据结构入门核心脉络解析

今天我们从两个经典数据结构入手 队列和二叉树 串联讲解它们的核心概念与应用 尤其会深入剖析二叉树中前序中序求后序的经典问题 让你彻底搞懂递归与树的逻辑

一 队列 先进先出的线性表

1 什么是队列

队列是一种线性数据结构 特点是先进先出FIFO 像生活中排队买票 先来的人先买到票离开 后来的人排在队尾 队列有两个关键端 队头出队 队尾入队

2 基本操作

入队enqueue 在队尾添加元素 出队dequeue 在队头移除元素 判空isEmpty 判断队列是否有元素 判满isFull 判断队列是否已满

3 实现 循环数组队列

用数组实现队列时 为避免假溢出 常用循环数组 即数组首尾相连 用两个指针front队头 rear队尾标记位置

#include <stdio.h>
#define MAX_SIZE 5 // 队列最大容量

// 队列结构体
typedef struct {
int data[MAX_SIZE]; // 存储元素的数组
int front; // 队头指针 指向队头元素
int rear; // 队尾指针 指向队尾下一个位置
} Queue;

// 初始化队列
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}

// 判空 队头队尾重合且未存元素时为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}

// 判满 队尾下一个位置是队头时满 (循环)
int isFull(Queue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队
int enqueue(Queue *q, int val) {
if (isFull(q)) {
printf("队列已满 无法入队\\n");
return 0; // 失败
}
q->data[q->rear] = val;
q->rear = (q->rear + 1) % MAX_SIZE; // 队尾循环后移
return 1; // 成功
}

// 出队
int dequeue(Queue *q, int *val) {
if (isEmpty(q)) {
printf("队列为空 无法出队\\n");
return 0; // 失败
}
*val = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE; // 队头循环后移
return 1; // 成功
}

// 示例 模拟排队
void queueExample() {
Queue q;
initQueue(&q);
enqueue(&q, 10); // 队尾入队10
enqueue(&q, 20); // 入队20
enqueue(&q, 30); // 入队30
int val;
dequeue(&q, &val); // 队头出队10
printf("出队元素 %d\\n", val); // 输出10
enqueue(&q, 40);
enqueue(&q, 50);
enqueue(&q, 60); // 此时队列满 无法入队
}

二 树形结构基本概念

1 什么是树

树是非线性数据结构 像倒过来的树 有根节点 每个节点有零个或多个子节点 子节点下还有子树 最上面是根 最下面是叶子

2 核心术语

节点 树的基本单位 度 节点拥有的子节点数 叶子节点 度为0的节点 双亲 父节点 孩子 子节点 兄弟 同一双亲的子节点 层次 根是第一层 往下递增 深度 树的最大层次 森林 多棵互不相交的树

3 例子

家族树 根是祖先 孩子是后代 公司架构 根是CEO 子树是各部门

三 二叉树基础

1 定义

二叉树是每个节点最多有两棵子树的树 分别叫左子树和右子树 子树有顺序 不能颠倒

2 特殊二叉树

满二叉树 每层节点都满 深度k有2^k 1个节点 完全二叉树 除最后一层 其余层满 最后一层节点靠左排列

3 性质

第i层最多有2^i 1个节点 深度为k的二叉树最多有2^k 1个节点 对任意二叉树 叶子数 度为2的节点数 1

4 遍历方式

前序遍历 根左右 先访问根 再左子树 再右子树 中序遍历 左根右 先左子树 再根 再右子树 后序遍历 左右根 先左子树 再右子树 再根 层序遍历 按层次从左到右访问

// 二叉树节点结构体
typedef struct TreeNode {
int val; // 节点值
struct TreeNode *left; // 左子树
struct TreeNode *right; // 右子树
} TreeNode;

// 前序遍历 根左右
void preorder(TreeNode *root) {
if (root == NULL) return;
printf("%d ", root->val); // 访问根
preorder(root->left); // 左子树
preorder(root->right); // 右子树
}

// 中序遍历 左根右
void inorder(TreeNode *root) {
if (root == NULL) return;
inorder(root->left); // 左子树
printf("%d ", root->val); // 访问根
inorder(root->right); // 右子树
}

// 后序遍历 左右根
void postorder(TreeNode *root) {
if (root == NULL) return;
postorder(root->left); // 左子树
postorder(root->right); // 右子树
printf("%d ", root->val); // 访问根
}

四 前序中序求后序 递归的艺术

 问题引入

已知二叉树前序序列和中序序列 求后序序列 例 前序ABDECF 中序DBEAFC 求后序

核心思路

前序定根 中序分左右 递归求解

步骤

1 前序第一个元素是根节点

2 在中序中找到根 左边是左子树中序 右边是右子树中序

3 根据左子树节点数 在前序中划分左子树前序右子树前序

4 递归处理左子树 得左后序 递归处理右子树 得右后序

5 后序 左后序 + 右后序 + 根

代码实现

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

// 根据前序pre和中序in 求后序 返回后序字符串
char* preInToPost(char *pre, char *in, int len) {
if (len <= 0) { // 空树
char *post = (char*)malloc(1);
post[0] = '\\0';
return post;
}

char root = pre[0]; // 前序首元素为根
// 在中序中找根位置
int i;
for (i = 0; i < len; i++) {
if (in[i] == root) break;
} // i是根在中序的位置

int leftLen = i; // 左子树节点数
int rightLen = len – i – 1; // 右子树节点数

// 递归左子树 前序[1~leftLen] 中序[0~i-1]
char *leftPost = preInToPost(pre + 1, in, leftLen);
// 递归右子树 前序[1+leftLen~end] 中序[i+1~end]
char *rightPost = preInToPost(pre + 1 + leftLen, in + i + 1, rightLen);

// 拼接后序 左后序+右后序+根
char *post = (char*)malloc(len + 1);
strcpy(post, leftPost);
strcat(post, rightPost);
post[len – 1] = root; // 根放最后
post[len] = '\\0';

free(leftPost); // 释放临时内存
free(rightPost);
return post;
}

// 示例
void example() {
char pre[] = "ABDECF"; // 前序
char in[] = "DBEAFC"; // 中序
int len = strlen(pre);
char *post = preInToPost(pre, in, len);
printf("后序序列 %s\\n", post); // 输出DEBFCA
free(post);
}

变体思考

中序后序求前序 思路类似 后序末元素为根 中序分左右 递归求左右前序 拼接根+左前序+右前序

总结

队列教会我们线性结构的顺序管理 二叉树则打开非线性思维大门 前序中序求后序的核心是递归拆分 抓住根与左右子树的关系 多画图多练手 就能掌握树的逻辑 动手实现这些代码 你会发现数据结构并不难