数据结构初阶：二叉树的链式存储结构
一、二叉树的链式结构
二叉树的链式结构主要分为二叉链和三叉链。本阶段主要讲解二叉链的结构体定义：
C算法
数据结构初阶：二叉树的链式存储结构
本文讲解了二叉树的链式存储结构实现。包含节点定义、手动创建二叉树、前中后序遍历、层序遍历、节点统计及深度计算等核心操作。通过递归和队列辅助完成基本功能，并提供了完整的 C 语言代码示例及测试用例，帮助理解二叉树的数据组织与遍历逻辑。
本文讲解了二叉树的链式存储结构实现。包含节点定义、手动创建二叉树、前中后序遍历、层序遍历、节点统计及深度计算等核心操作。通过递归和队列辅助完成基本功能，并提供了完整的 C 语言代码示例及测试用例，帮助理解二叉树的数据组织与遍历逻辑。
二叉树的链式结构主要分为二叉链和三叉链。本阶段主要讲解二叉链的结构体定义：
// 链式二叉树的节点
typedef struct BinaryTree {
Elemtype data;
struct BinaryTree* leftChild;
struct BinaryTree* rightChild;
} BTNode;
在一个二叉树的节点中，包含数据域和指针域。数据域存储当前节点的值，指针域包含其左子树和右子树的指针（地址），方便直接找到左右子树。
为了便于理解二叉树的基本性质和快速上手，我们手动创建一棵二叉树，暂不涉及复杂的增删查改操作。
二叉树节点的创建与链表节点的创建类似：
// 先创建新节点
BTNode* BuyNode(Elemtype data) {
// 申请空间
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode == NULL) {
perror("create new node fail!\n");
}
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return newNode;
}
通过 BuyNode 创建节点后，将根节点与左右子树进行连接：
BTNode* createNewBT() {
// 创建新节点
BTNode* NodeA = BuyNode('A');
BTNode* NodeB = BuyNode('B');
BTNode* NodeC = BuyNode('C');
BTNode* NodeD = BuyNode('D');
BTNode* NodeE = BuyNode('E');
BTNode* NodeF = BuyNode('F');
BTNode* NodeG = BuyNode('G');
BTNode* NodeH = BuyNode('H');
BTNode* NodeI = BuyNode('I');
BTNode* NodeO = BuyNode('O');
// 直接将节点进行连接
NodeA->leftChild = NodeB;
NodeA->rightChild = NodeC;
NodeB->leftChild = NodeD;
NodeB->rightChild = NodeE;
NodeD->leftChild = NodeH;
NodeC->leftChild = NodeF;
NodeF->leftChild = NodeI;
NodeH->leftChild = NodeO;
return NodeA;
}
该二叉树的结构如下所示：
在链式二叉树中，主要进行以下操作：前序遍历、中序遍历、后序遍历、层序遍历、计算总结点个数、计算叶子节点个数、计算第 k 层节点个数、计算深度、查找元素等。
前序遍历指访问根节点的操作发生在访问左右子树之前（根 -> 左 -> 右）。
// 前序遍历 (根->左->右)
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->leftChild);
PreOrder(root->rightChild);
}
递归终止条件为 root == NULL。遍历过程严格遵循'根->左->右'原则。
中序遍历即访问根节点的操作发生在访问左子树之后，在访问右子树之前（左 -> 根 -> 右）。
// 中序遍历 (左->根->右)
void InOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
InOrder(root->leftChild);
printf("%c ", root->data);
InOrder(root->rightChild);
}
后序遍历即访问根节点的操作发生在访问左子树和右子树之后（左 -> 右 -> 根）。
// 后序遍历 (左->右->根)
void LastOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
LastOrder(root->leftChild);
LastOrder(root->rightChild);
printf("%c ", root->data);
}
采用递归方式，统计左子树和右子树的节点数并相加。
int BinaryTreeSize_of_Node(BTNode* root) {
if (root == NULL) {
return 0;
}
return 1 + BinaryTreeSize_of_Node(root->leftChild) + BinaryTreeSize_of_Node(root->rightChild);
}
当 leftChild 和 rightChild 均为 NULL 时，返回 1。
int BinaryTreesize_of_Leaf(BTNode* root) {
if (root == NULL) return 0;
if (root->leftChild == NULL && root->rightChild == NULL) return 1;
return BinaryTreesize_of_Leaf(root->leftChild) + BinaryTreesize_of_Leaf(root->rightChild);
}
通过递归减少 k 值，当 k=1 时返回 1。
int BinaryTreeSize_of_K(BTNode* root, int k) {
if (root == NULL) return 0;
if (k == 1) return 1;
return BinaryTreeSize_of_K(root->leftChild, k - 1) + BinaryTreeSize_of_K(root->rightChild, k - 1);
}
比较左右子树的深度，取较大值加 1。
int BinaryTreeSize_of_Depth(BTNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = BinaryTreeSize_of_Depth(root->leftChild);
int rightDepth = BinaryTreeSize_of_Depth(root->rightChild);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
遍历整个二叉树，若存在该元素则输出提示。
void BinaryTreeSearch_of_val(BTNode* root, Elemtype val) {
if (root == NULL) return;
if (root->data == val) {
printf("找到了!\n");
return;
}
BinaryTreeSearch_of_val(root->leftChild, val);
BinaryTreeSearch_of_val(root->rightChild, val);
}
借助队列实现，先将根节点入队，循环取出队头元素并打印，将其左右孩子入队。
void LevelOrder(BTNode* root) {
Queue q;
Queue* pQueue = &q;
InitQueue(pQueue);
Push_Queue(pQueue, root);
while (!isEmpty(pQueue)) {
BTNode* top = GetElemFront(pQueue);
printf("%c ", top->data);
Pop_Queue(pQueue);
if (top->leftChild) {
Push_Queue(pQueue, top->leftChild);
}
if (top->rightChild) {
Push_Queue(pQueue, top->rightChild);
}
}
DestroyQueue(pQueue);
}
通过层序遍历，当遇到空节点后，后续所有节点必须为空才算完全二叉树。
bool IsBinaryTree_of_Complete(BTNode* root) {
Queue q;
Queue* pQueue = &q;
InitQueue(pQueue);
Push_Queue(pQueue, root);
while (!isEmpty(pQueue)) {
QElemtype top = GetElemFront(pQueue);
Pop_Queue(pQueue);
if (top == NULL) {
break;
}
Push_Queue(pQueue, top->leftChild);
Push_Queue(pQueue, top->rightChild);
}
while (!isEmpty(pQueue)) {
BTNode* top = GetElemFront(pQueue);
Pop_Queue(pQueue);
if (top != NULL) {
DestroyQueue(pQueue);
return false;
}
}
DestroyQueue(pQueue);
return true;
}
需确保引入了队列的头文件（如 Queue.h），并根据需要调整数据类型（如将队列元素类型定义为 struct BinaryTree*）。
以下是整合后的二叉树核心代码及测试主函数：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Queue.h"
typedef char Elemtype;
typedef struct BinaryTree {
Elemtype data;
struct BinaryTree* leftChild;
struct BinaryTree* rightChild;
} BTNode;
BTNode* BuyNode(Elemtype data) {
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode == NULL) {
perror("create new node fail!\n");
}
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return newNode;
}
BTNode* createNewBT() {
BTNode* NodeA = BuyNode('A');
BTNode* NodeB = BuyNode('B');
BTNode* NodeC = BuyNode('C');
BTNode* NodeD = BuyNode('D');
BTNode* NodeE = BuyNode('E');
BTNode* NodeF = BuyNode('F');
BTNode* NodeG = BuyNode('G');
BTNode* NodeH = BuyNode('H');
BTNode* NodeI = BuyNode('I');
BTNode* NodeO = BuyNode('O');
NodeA->leftChild = NodeB;
NodeA->rightChild = NodeC;
NodeB->leftChild = NodeD;
NodeB->rightChild = NodeE;
NodeD->leftChild = NodeH;
NodeC->leftChild = NodeF;
NodeF->leftChild = NodeI;
NodeH->leftChild = NodeO;
return NodeA;
}
void PreOrder(BTNode* root) {
if (root == NULL) { printf("NULL "); return; }
printf("%c ", root->data);
PreOrder(root->leftChild);
PreOrder(root->rightChild);
}
void InOrder(BTNode* root) {
if (root == NULL) { printf("NULL "); return; }
InOrder(root->leftChild);
printf("%c ", root->data);
InOrder(root->rightChild);
}
void LastOrder(BTNode* root) {
if (root == NULL) { printf("NULL "); return; }
LastOrder(root->leftChild);
LastOrder(root->rightChild);
printf("%c ", root->data);
}
int BinaryTreeSize_of_Node(BTNode* root) {
if (root == NULL) return 0;
return 1 + BinaryTreeSize_of_Node(root->leftChild) + BinaryTreeSize_of_Node(root->rightChild);
}
int BinaryTreesize_of_Leaf(BTNode* root) {
if (root == NULL) return 0;
if (root->leftChild == NULL && root->rightChild == NULL) return 1;
return BinaryTreesize_of_Leaf(root->leftChild) + BinaryTreesize_of_Leaf(root->rightChild);
}
int BinaryTreeSize_of_K(BTNode* root, int k) {
if (root == NULL) return 0;
if (k == 1) return 1;
return BinaryTreeSize_of_K(root->leftChild, k - 1) + BinaryTreeSize_of_K(root->rightChild, k - 1);
}
int BinaryTreeSize_of_Depth(BTNode* root) {
if (root == NULL) return 0;
int leftDepth = BinaryTreeSize_of_Depth(root->leftChild);
int rightDepth = BinaryTreeSize_of_Depth(root->rightChild);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
void BinaryTreeSearch_of_val(BTNode* root, Elemtype val) {
if (root == NULL) return;
if (root->data == val) { printf("找到了!\n"); return; }
BinaryTreeSearch_of_val(root->leftChild, val);
BinaryTreeSearch_of_val(root->rightChild, val);
}
void LevelOrder(BTNode* root) {
Queue q;
Queue* pQueue = &q;
InitQueue(pQueue);
Push_Queue(pQueue, root);
while (!isEmpty(pQueue)) {
BTNode* top = GetElemFront(pQueue);
printf("%c ", top->data);
Pop_Queue(pQueue);
if (top->leftChild) Push_Queue(pQueue, top->leftChild);
if (top->rightChild) Push_Queue(pQueue, top->rightChild);
}
DestroyQueue(pQueue);
}
bool IsBinaryTree_of_Complete(BTNode* root) {
Queue q;
Queue* pQueue = &q;
InitQueue(pQueue);
Push_Queue(pQueue, root);
while (!isEmpty(pQueue)) {
QElemtype top = GetElemFront(pQueue);
Pop_Queue(pQueue);
if (top == NULL) break;
Push_Queue(pQueue, top->leftChild);
Push_Queue(pQueue, top->rightChild);
}
while (!isEmpty(pQueue)) {
BTNode* top = GetElemFront(pQueue);
Pop_Queue(pQueue);
if (top != NULL) { DestroyQueue(pQueue); return false; }
}
DestroyQueue(pQueue);
return true;
}
int main() {
BTNode* NodeA = createNewBT();
printf("前序遍历:"); PreOrder(NodeA); printf("\n");
printf("中序遍历:"); InOrder(NodeA); printf("\n");
printf("后序遍历:"); LastOrder(NodeA); printf("\n");
printf("总结点个数：%d\n", BinaryTreeSize_of_Node(NodeA));
printf("叶子结点个数：%d\n", BinaryTreesize_of_Leaf(NodeA));
printf("第 4 层节点个数：%d\n", BinaryTreeSize_of_K(NodeA, 4));
printf("二叉树深度：%d\n", BinaryTreeSize_of_Depth(NodeA));
BinaryTreeSearch_of_val(NodeA, 'I');
printf("层序遍历："); LevelOrder(NodeA); printf("\n");
if (IsBinaryTree_of_Complete(NodeA)) printf("是完全二叉树\n");
else printf("不是完全二叉树\n");
return 0;
}
以下是队列辅助实现的代码：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct BinaryTree* QElemtype;
typedef struct QueueNode {
QElemtype data;
struct QueueNode* next;
} QueueNode;
typedef struct Queue {
QueueNode* phead;
QueueNode* ptail;
} Queue;
void InitQueue(Queue* pQueue) {
pQueue->phead = pQueue->ptail = NULL;
}
void Push_Queue(Queue* pQueue, QElemtype x) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL) {
perror("Fail reason: ");
exit(0);
}
newNode->data = x;
newNode->next = NULL;
if (pQueue->phead == NULL) {
pQueue->phead = pQueue->ptail = newNode;
} else {
pQueue->ptail->next = newNode;
pQueue->ptail = pQueue->ptail->next;
}
}
bool isEmpty(Queue* pQueue) {
assert(pQueue);
return pQueue->phead == NULL;
}
void Pop_Queue(Queue* pQueue) {
assert(pQueue);
if (pQueue->phead == NULL) {
perror("Fail reason: ");
exit(0);
}
QueueNode* next = pQueue->phead->next;
free(pQueue->phead);
pQueue->phead = next;
}
QElemtype GetElemFront(Queue* pQueue) {
assert(pQueue);
if (isEmpty(pQueue)) exit(1);
return pQueue->phead->data;
}
void DestroyQueue(Queue* pQueue) {
assert(pQueue);
QueueNode* pcur = pQueue->phead;
while (pcur != NULL) {
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pQueue->phead = pQueue->ptail = NULL;
}
运行结果示例：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online