文章目录
- 前言
- 一、普通二叉树(链式结构)基本结构构建
- 二、前序遍历(先根遍历)
- 三、中序遍历
- 四、后序遍历
- 五、二叉树结点个数
- 六、二叉树叶子结点个数
- 七、二叉树第k层结点个数(k >= 1)
- 八、求二叉树高度
- 九、二叉树查找值为x的结点
- 十、二叉树销毁
- 十一、二叉树层序遍历(需要借助队列)
- 借助的队列代码_Queue.c:
- 借助的队列代码_Queue.h:
- 层序遍历代码:
- 十二、判断二叉树是否为完全二叉树(需要借助队列)
- 十三、测试代码:
- 总结
前言
本文总结学习普通二叉树(链式结构)接口实现-C语言。
一、普通二叉树(链式结构)基本结构构建
#include
#include
#include
// 该头文件的包含相当于将Queue.h的代码全部复制到此处,后续二叉树层序遍历和判断完全二叉树用到
#include "Queue.h"
// 普通二叉树链式结构的实现
// 说明:普通二叉树增删查改没有价值,如果是为了单纯存放数据,不如使用线性表
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 创建结点
BTNode* BuyBTNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
assert(newnode);
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
// 构建一颗二叉树
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyBTNode(1);
BTNode* node2 = BuyBTNode(2);
BTNode* node3 = BuyBTNode(3);
BTNode* node4 = BuyBTNode(4);
BTNode* node5 = BuyBTNode(5);
BTNode* node6 = BuyBTNode(6);
BTNode* test = BuyBTNode(99);
node1->left = node2;
node2->left = node3;
node1->right = node4;
node2->right = test;
node4->left = node5;
node4->right = node6;
return node1;
}
二、前序遍历(先根遍历)
// 前序遍历(先根遍历)
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;
}
借助的队列代码_Queue.h:
#pragma once
#include
#include
#include
#include
// 当队列的数值不为int类型时,方便修改,当层序遍历二叉树时,作用就体现出来了
// 前置声明(类似函数声明),在此处用到该结构体指针,且在链式二叉树源文件中,此处需要向上找struct BinaryTreeNode的定义
// 所以需要前置声明,告诉编译器定义在后面找
struct BinaryTreeNode;// 声明类型,而不是全局变量(用到extern)
typedef struct BinaryTreeNode* QDataType;// 在链式二叉树源文件中,此处需要向上找struct BinaryTreeNode的定义
// 单链表结构(表示队列,定义结点)
typedef struct QListNode
{
struct QListNode* next;
QDataType val;
}QNode;
// 队列的结构(定义头尾指针,方便出入队列)
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType val);
// 队头出队列
void QueuePop(Queue* pq);
// 检测队列是否为空
bool QueueEmpty(Queue* pq);
// 获取队列中有效元素个数
size_t QueueSize(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列尾部元素
QDataType QueueBack(Queue* pq);
层序遍历代码:
// 二叉树的层序遍历(需要借助队列)
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条)