当前位置：网站首页>二叉树的实现-c
二叉树的实现-c
2022-07-23 05:44:00 【潜水少年请求出战】
1.二叉树概况方向：
在这里我先推荐几道关于二叉树的基础OJ题，加快友友们实现。
链接: 基础OJ题
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
2.分析与解刨
1.二叉树的销毁，我建议用一级指针，保持与其它的一致（到外面把根置空。），当然也可以用二级的。
2.判断是应该用bool,但是本质就是0是错，1是对，我们可以打印来观看。
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
在先序遍历的过程中构建每一个节点
代码：
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
//当结点没有孩子或这走到最后都要返回NULL
if (a[*pi]=='#' || (*pi) >= n)
{
++(*pi);
return NULL;
}
//创建一个结点
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
printf("malloc file!");
exit(-1);
}
root->data = a[(*pi)++];
root->left = BinaryTreeCreate(a, n, pi);
root->right= BinaryTreeCreate(a, n, pi);
return root;
}
运行结果：
红框是前序遍历，后面两个是中和后序遍历
推荐一道题：链接: 二叉树遍历
题解解析：
/* 解题思路： 在先序遍历的过程中构建每一个节点 */
#include <stdio.h>
#include <malloc.h>
typedef struct BTNode
{
char _data;
struct BTNode* _left;
struct BTNode* _right;
}BTNode;
//中序遍历
void Inorder(BTNode* root)
{
if(root)
{
Inorder(root->_left);
printf("%c ", root->_data);
Inorder(root->_right);
}
}
BTNode* CreatBTree(char* str, int* pi)
{
if(str[*pi]!= '#')
{
//当前节点非空，则创建当前节点
BTNode*root=(BTNode*)malloc(sizeof(BTNode));
root->_data = str[*pi];
//字符位置向后移动一个位置
++(*pi);
//创建左子树
root->_left=CreatBTree(str,pi);
//字符位置向后移动一个位置
++(*pi);
//创建右子树
root->_right=CreatBTree(str,pi);
return root;
}
else
return NULL; //如果是空节点，则返回NULL
}
int main()
{
char str[101];
int i = 0;
//读入字符串
scanf("%s", str);
//创建二叉树
BTNode* root = CreatBTree(str, &i);
//中序打印二叉树
Inorder(root);
printf("\n");
return 0;
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在
层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历的思路：我们需要借助队列来实现，c语言只能自己来实现一个。链接: 队列
我们有了一个队列后(当然我们队列里存的是结点)，我们可以先存一个树的根，然后取出的时候再放它的孩子，当然它孩子为空不存，只取。例如：存了A，当我们存它的孩子B、C的时候先利用队列的性质把A取出来（打印一下）后存BC。依次类推。
代码：
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
//如果队列不为空，进入。
while (!QueueEmpty(&q))
{
//取出 打印
BTNode* front = QueueFront(&q);
printf("%c ", front->data);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
//销毁队列
QueueDestroy(&q);
}
运行结果：
A B C D E F G H
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
我建议使用一级，不用二级所以就，销毁我采用的是后序的方法来销毁。
代码段：
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
//printf("%p %c\n", root, root->data);
free(root);
}
通过打印看销毁成功
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
层序遍历遇到NULL，不把这个结点放进去，而判断完全二叉树先把NULL存进去，当拿出的那个结点为空；我们跳出来后；此时只有两种情况。（1.如果后面全是空，则是完全二叉树；2.如果后面还有非空，则不是完全二叉树。）
代码段：
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
//遇到NULL，跳出。
break;
}
}
//1.如果后面全是空，则是完全二叉树；
//2.如果后面还有非空，则不是完全二叉树。
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
结果展示：
0为假1为真
1、前序遍历的数组"ABD##E#H##CF##G##"构建二叉树，它不是完全二叉树，而"ABD##E##CF##G##"是完全二叉树。
1.
2
显然第二个是完全二叉树
总的代码：
两个.h文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct
{
QNode* head;
QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//放数据
void QueuePush(Queue* pq, QDataType x);
//删除
void QueuePop(Queue* pq);
//长度
int QueueSize(Queue* pq);
//取头
QDataType QueueFront(Queue* pq);
//取尾
QDataType QueueBack(Queue* pq);
//判断空
bool QueueEmpty(Queue* pq);
3个.c文件
#include"bt.h"
#include"queue.h"
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
//当结点没有孩子或这走到最后都要返回NULL
if (a[*pi]=='#' || (*pi) >= n)
{
++(*pi);
return NULL;
}
//创建一个结点
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
printf("malloc file!");
exit(-1);
}
root->data = a[(*pi)++];
root->left = BinaryTreeCreate(a, n, pi);
root->right= BinaryTreeCreate(a, n, pi);
return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
//printf("%p %c\n", root, root->data);
free(root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
return;
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
return;
BinaryTreePrevOrder(root->left);
printf("%c ", root->data);
BinaryTreePrevOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
return;
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
printf("%c ", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
//如果队列不为空，进入。
while (!QueueEmpty(&q))
{
//取出 打印
BTNode* front = QueueFront(&q);
printf("%c ", front->data);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
//销毁队列
QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
//遇到NULL，跳出。
break;
}
}
//1.如果后面全是空，则是完全二叉树；
//2.如果后面还有非空，则不是完全二叉树。
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
#include"queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//放数据
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//开辟空间
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//添加数据
newnode->data = x;
newnode->next = NULL;
//链接
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//判断空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//取头
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//取尾
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//长度
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
int count = 0;
while (cur)
{
++count;
cur = cur->next;
}
return count;
}
#include"bt.h"
#include"queue.h"
int main()
{
char ch[] = "ABD##E#H##CF##G##";
//gets(ch);
int n = strlen(ch);
int i = 0;
//BinaryTreeCreate
BTNode* root = BinaryTreeCreate(ch, n, &i);
//进行前序遍历，输出遍历结果。
BinaryTreePrevOrder(root);
printf("\n");
//进行中序遍历，输出遍历结果。
BinaryTreeInOrder(root);
printf("\n");
//进行后序遍历，输出遍历结果。
BinaryTreePostOrder(root);
printf("\n");
//结点个数
int ret = BinaryTreeSize(root);
printf("%d\n", ret);
//叶结点的个数
int ret1 = BinaryTreeLeafSize(root);
printf("%d\n", ret1);
//第k个结点
int ret2 = BinaryTreeLevelKSize(root, 2);
printf("%d\n", ret2);
//借用队列实现层序遍历
BinaryTreeLevelOrder(root);
// 判断二叉树是否是完全二叉树
int ret3 = BinaryTreeComplete(root);
printf("%d\n", ret3);
BTNode* c = BinaryTreeFind(root, ch[2]);
printf("%c", c->data);
BinaryTreeDestory(root);
root = NULL;
return 0;
}
看完之后，二叉树的基本友友们已经掌握了，下个文章见.
边栏推荐
- Interpretation of the paper: iterative feature representation method to improve the prediction performance of N7 methylguanosine (m7G) sites
- 3.2daydayup举一反三：三天打鱼两天晒网式学习
- [distinguish the meaning and usage of constant pointer and pointer constants const int * and int * const]
- 使用PyOD来进行异常值检测
- ARM架构与编程5--gcc与Makefile（基于百问网ARM架构与编程教程视频）
- 利用google or-tools 求解逻辑难题：斑马问题
- 【AUTOSAR CanDrive 2.了解通信Hoh、CanId与PduID的Mapping关系】
- 【学习总结】
- Analysis of 100 questions and answers in Higher Algebra
- Interpretation of the paper: develop a prediction model based on multi-layer deep learning to identify DNA N4 methylcytosine modification
猜你喜欢
How can knowledge map, map data platform and map technology help the rapid development of retail industry
ARM架构与编程1--LED闪烁（基于百问网ARM架构与编程教程视频）
Interpretation of the paper: iterative feature representation method to improve the prediction performance of N7 methylguanosine (m7G) sites
Deep convolution generation countermeasure network
![[AUTOSAR candrive 1. learn the function and structure of candrive]](/img/f6/662512bddab70e75367d212029fc23.png)
[AUTOSAR candrive 1. learn the function and structure of candrive]
单片机学习笔记9--常见的通信方式（基于百问网STM32F103系列教程）
把LVGL所有控件整合到一个工程中展示（LVGL6.0版本）
【存储器了解 RAM flash和eeprom存储器的区别和作用】
Using pycaret: low code, automated machine learning framework to solve classification problems
Under the "double carbon" goal of the digital economy, why does the "digital East and digital West" data center rely on liquid cooling technology to save energy and reduce emissions?
随机推荐
C语言中，对柔性数组的理解
[AUTOSAR com 3. signal sending and receiving process tx/rx]
对字符串函数的使用和理解（2）
Eigen multi version library installation
博客搭建二：NexT主题相关设置beta
博客搭建六：绑定自己域名的方法
Under the "double carbon" goal of the digital economy, why does the "digital East and digital West" data center rely on liquid cooling technology to save energy and reduce emissions?
ARM架构与编程1--LED闪烁（基于百问网ARM架构与编程教程视频）
硬件知识1--原理图和接口类型（基于百问网硬件操作大全视频教程）
硬件知識1--原理圖和接口類型（基於百問網硬件操作大全視頻教程）
How to develop the computing power and AI intelligent chips in the data center of "digital computing in the East and digital computing in the west"?
Installation and use of APP automated testing tool appium
Data analysis of time series (I): main components
单片机学习笔记7--SysTick定时器（基于百问网STM32F103系列教程）
高分子合成工艺学复习考题
LVGL8.1版本笔记
高电压技术基础知识
【AUTOSAR CanDrive 1.学习CanDrive的功能和结构】
Question bank of basic principles of steel structure
高分子物理考研概念及要点、考点总结