文章目录
- 前言
- 一、普通二叉树（链式结构）基本结构构建
- 二、前序遍历（先根遍历）
- 三、中序遍历
- 四、后序遍历
- 五、二叉树结点个数
- 六、二叉树叶子结点个数
- 七、二叉树第k层结点个数（k >= 1）
- 八、求二叉树高度
- 九、二叉树查找值为x的结点
- 十、二叉树销毁
- 十一、二叉树层序遍历(需要借助队列)
- 借助的队列代码_Queue.c：
- 借助的队列代码_Queue.h:
- 层序遍历代码：
- 十二、判断二叉树是否为完全二叉树（需要借助队列）
- 十三、测试代码：
- 总结
前言
本文总结学习普通二叉树（链式结构）接口实现-C语言。
一、普通二叉树（链式结构）基本结构构建
#include 二、前序遍历（先根遍历）
// 前序遍历（先根遍历）
void PreOrder(BTNode* root)
{
if (NULL == root)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
三、中序遍历
// 中序遍历
void InOrder(BTNode* root)
{
if (NULL == root)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
四、后序遍历
// 后序遍历
void PostOrder(BTNode* root)
{
if (NULL == root)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
五、二叉树结点个数
// 二叉树结点个数
// 方法1：
// 思路：（子问题）
// 1.空树，最小规模子问题，结点个数为0，返回0
// 2.非空树，左子树结点个数+右子树结点个数+1（自己）
// 分治：把复杂的问题，分成更小规模的子问题，子问题再分成更小规模的子问题。
。
。
直到子问题不可再分割，直接能出结果
// （校长->院长->班长->舍长）
int BTreeSize(BTNode* root)
{
return (NULL == root) ? 0 : \
1 + BTreeSize(root->left) + \
BTreeSize(root->right);
}
// 方法2：（main函数创建一个变量，传它的地址进来）（思路：遍历+计数，最优）
//void BTreeSize(BTNode* root, int* num)
//{
// if (NULL == root)
// {
// return 0;
// }
// else
// {
// (*num)++;// 顺序无所谓，因为只是先加后加的问题
// BTreeSize(root->left, num);
// BTreeSize(root->right, num);
// }
//}
// 方法3：（每次调用函数都需要提前将全局变量num置零）
// 不好！！！线程安全的问题，学linux就知道了，
// 多线程都在调用这个函数，你在调用我在调用，同时去执行，对同一个变量加加会错乱
//int num = 0;
//void BTreeSize(BTNode* root)
//{
// if (NULL == root)
// {
// return;
// }
// else
// {
// num++;// 顺序无所谓，因为只是先加后加的问题
// BTreeSize(root->left);
// BTreeSize(root->right);
// }
//}
// 方法4：（每次调用函数都需要提前将全局变量num置零，但是在main函数无法置零，所以这个方法错误！！！！！）
//int BTreeSize(BTNode* root)
//{
// static int num = 0; //每次调用时,初始化只会执行一次
//
// if (NULL == root)
// {
// return 0;
// }
// else
// {
// num++;// 顺序无所谓，因为只是先加后加的问题
// BTreeSize(root->left);
// BTreeSize(root->right);
// return num;
// }
//}
六、二叉树叶子结点个数
// 二叉树叶子结点个数(思路1：遍历+计数；思路2：分治)
// 分治思想
int BTreeLeafSize(BTNode* root)
{
if (NULL == root)
{
return 0;
}
return (NULL == root->left && NULL == root->right) ? 1 : \
BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
七、二叉树第k层结点个数（k >= 1）
// 二叉树第k层结点个数（k >= 1）
// 分治思想
// 空树：返回0
// 非空且k==1，返回1
// 非空且k>1，返回左子树的k-1层结点数+右子树的k-1层结点数
int BTreeLevelSize(BTNode* root, int k)
{
assert(k >= 1);
if (NULL == root)
{
return 0;
}
return (1 == k) ? 1 : \
BTreeLevelSize(root->left, k - 1) + \
BTreeLevelSize(root->right, k - 1);
}
八、求二叉树高度
// 求二叉树高度
// 分治思想：
// 空树，高度为0
// 非空树，左子树高度和右子树高度大的那个+1
int BTreeDepth(BTNode* root)
{
if (NULL == root)
{
return 0;
}
else
{
int leftDepth = BTreeDepth(root->left);
int rightDepth = BTreeDepth(root->right);
return (leftDepth > rightDepth) ? \
1 + leftDepth : 1 + rightDepth;
}
}
九、二叉树查找值为x的结点
// 二叉树查找值为x的结点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
// 类似于先序查找
if (NULL == root)
{
return NULL;
}
if (x == root->data)
{
return root;
}
BTNode* ret1 = BTreeFind(root->left, x);
if (NULL != ret1)
{
return ret1;
}
// 可简化为：
// return BTreeFind(root->left, x);// 不推荐，不容易看懂，逻辑不清晰
BTNode* ret2 = BTreeFind(root->right, x);
if (NULL != ret2)
{
return ret2;
}
// 可简化为：
// return BTreeFind(root->right, x);// 不推荐，不容易看懂，逻辑不清晰
return NULL; // 别忘记了！！！！
}
十、二叉树销毁
// 二叉树销毁
void BTreeDestory(BTNode** proot)
{
if (NULL == *proot)
{
return;
}
// 类似于后序销毁
BTreeDestory(&((*proot)->left));
BTreeDestory(&((*proot)->right));
free(*proot);
*proot = NULL;
}
// 或者写为：
//void BTreeDestory(BTNode* root)
//{
// if (NULL == root)
// {
// return;
// }
//
// // 类似于后序销毁
// BTreeDestory(root->left);
// BTreeDestory(root->right);
//
// free(root);
// // root = NULL; 在main中调用完处置空
//}
十一、二叉树层序遍历(需要借助队列) 借助的队列代码_Queue.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
// 初始化队列
void QueueInit(Queue* pq) // point queue简写
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
// 遍历链表，将每个结点释放掉，最后将头尾指针也置空
QNode* cur = pq->head;
while (NULL != cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
// free(pq); 为啥不用？？？？？？？？？？？？？？因为初始状态是结构体，而不是结构体指针
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType val)
{
assert(pq);
// 创建一个新结点，因为所有接口函数只有此函数需要，所以无需单独创建函数
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (NULL == newnode) // 或者assert也可以
{
printf("malloc fail\n");
exit(-1);
}
else
{
// 初始化新结点！！！！！！！！别忘记
newnode->next = NULL;
newnode->val = val;
if (NULL == pq->tail)
{
//assert(pq->head == NULL); //没必要，原因见下:
// 当该链表的尾结点指针为NULL，此时头结点也一定为NULL时，将该结点作为头尾结点
pq->head = newnode;
pq->tail = newnode;
}
else
{
// 连接新尾结点
pq->tail->next = newnode;
// 更新尾结点指针
pq->tail = newnode;
}
}
}
// 队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
// 易错！！！！！！不加下面语句的代码会出现：
// 当最后一个结点出队列后，head为NULL，而tail仍为尾结点，且改该尾结点已经被free了，此时tail为野指针
// 补充代码：
if (NULL == pq->head->next)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
// 记录头结点下一个位置
QNode* next = pq->head->next;
free(pq->head);
// 更新头结点指针
pq->head = next;
}
}
// 检测队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
// 注：当仅剩一个结点时，二者相等，但是不为空，所以二者相等不能用来判定空
return NULL == pq->tail;// 当尾结点指针为空时，头结点指针也必定为空；当头结点指针为空时，尾结点指针也必定为空
}
// 获取队列中有效元素个数
size_t QueueSize(Queue* pq)
{
assert(pq);
// 不能使用指针相减来求，因为链表的物理结构不连续!!!!!!
// 方法1，在初始的队列结构中新增一个size变量，每次更新size来获取元素个数
// 方法2，数数
size_t num = 0;
QNode* cur = pq->head;
while (NULL != cur) // 或while(cur)
{
num++;
cur = cur->next;
}
return num;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->val;
}
// 获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->val;
}
#pragma once
#include // 二叉树的层序遍历(需要借助队列)
void LevelOrder(BTNode* root)
{
// 先把根入队列，借助队列先进先出的性质，上一层结点出队列时带自己的两个子结点入队列，直到队列为空
//（所以把结点指针或者结点入队列才能找到对应子结点，但是结点指针占空间小，所以传结点指针）
if (NULL == root)
{
printf("root NULL\n");
return;
}
Queue q = { 0 };
QueueInit(&q);
// 根结点不为空，入根结点
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
// 每轮循环会自动更新至队列的下一个元素
BTNode* front = QueueFront(&q);// 记录该非空结点（QueuePop(&q);之后仍然可以调用它的左右子结点）
printf("%d ", front->data);
// 也可以放在最后
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
QueueDestroy(&q);
}
十二、判断二叉树是否为完全二叉树（需要借助队列）
借助队列同十一章节队列
// 判断二叉树是否为完全二叉树（需要借助队列）
bool BTreeComplete(BTNode* root)
{
// 首先模仿层序遍历（NULL结点也如入队列），直到队头元素为NULL（出到空结点时）时，退出循环
// 从出到的空结点起开始向后出队列现存的所有数据，如果全为空：则说明是完全二叉树；否则一旦遇到非空元素，则说明不是
Queue q = { 0 };
QueueInit(&q);
if (NULL == root) // 空树也为完全二叉树，向下执行，直到最后返回true ！！！！！！！！！！！
{
// 根非空，入队列
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (NULL == front)
{
// 队头数据（出到的数据）为空直接退出循环
// 如果是非完全二叉树：有没有将所有数据入队列完不重要，因为上一层的父节点出队列必然会将左右子结点带入队列，
// 所以即使左子树很小，很快就出到NULL，但是非完全树，它右边的兄弟或表兄弟结点肯定有不为空的结点已经在队列的NULL后面
// 如果是完全二叉树：那么所有（包括空结点）必然全部已经入队列 ！！！！！！！！！
break;
}
else
{
// 无需考虑空或非空，直接入队列
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);// 刚刚判断了队列不为空，所以此处必不为空
QueuePop(&q);
if (front)
{
// 好习惯：先销毁（防止内存泄漏）！！！！！！！！！！
QueueDestroy(&q);
// 队头数据（出到的数据）为非空直接返回false
return false;
}
// 为空，继续执行下一轮循环（会自动更新到下一个结点) ！！！！！！！！！！！
}
// 好习惯：先销毁（防止内存泄漏）
QueueDestroy(&q);
return true;
//while (!QueueEmpty(&q))
//{
// if (front)// front数据不为空
// {
// // 不是完全二叉树，直接返回false
// return false;
// }
// else
// {
// // 更新front（无须继续入队列）
// QueuePop(&q);
// if (!QueueEmpty(&q))// 防止QueueFront(&q);中报错 // 写法不好。
更新见上！！！！！！！！！！！
// {
// front = QueueFront(&q);
// }
// }
//}
}
十三、测试代码：
int main()
{
BTNode* tree = CreatBinaryTree();//或者起名root
// 前序遍历（先根遍历）
PreOrder(tree);
printf("\n");
// 中序遍历
InOrder(tree);
printf("\n");
// 后序遍历
PostOrder(tree);
printf("\n");
// 二叉树结点个数
printf("Size:%d\n", BTreeSize(tree));
// 二叉树叶子结点个数
printf("LeafSize:%d\n", BTreeLeafSize(tree));
// 二叉树第k层结点个数（k >= 1）
printf("LevelSize:%d\n", BTreeLevelSize(tree, 3));
// 求二叉树高度
printf("Depth:%d\n", BTreeDepth(tree));
// 二叉树查找值为x的结点（可结合修改，再次排序来使用）
// 测试查找所有值，包括测试查找不存在的值
for (int i = 1; i <= 7; i++)
{
BTNode* ret = BTreeFind(tree, i);
printf("BTreeFind:%d %p\n", i, ret); // 测试地址，因为如果测试7时，ret为NULL，去访问它的值就会形成非法访问
}
// 二叉树层序遍历
LevelOrder(tree);
printf("\n");
// 判断二叉树是否为完全二叉树（需要借助队列）
if (BTreeComplete(tree))
{
printf("该树是完全二叉树\n");
}
else
{
printf("该树不是完全二叉树\n");
}
// 二叉树销毁
BTreeDestory(&tree);
return 0;
}
总结
这里对文章进行总结：
以上就是今天总结的内容，本文包括了C语言实现普通二叉树（链式结构）各个接口，分享给大家。
真💙欢迎各位给予我更好的建议，欢迎访问！！！小编创作不易，觉得有用可以一键三连哦，感谢大家。
peace
希望大家一起坚持学习，共同进步。
梦想一旦被付诸行动，就会变得神圣。
欢迎各位大佬批评建议，分享更好的方法！！！🙊🙊🙊
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）