news 2026/9/14 17:56:57

【C 数据结构】 树 二叉树 堆 (链式二叉树模拟实现篇)

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
【C 数据结构】 树 二叉树 堆 (链式二叉树模拟实现篇)

目录

链式二叉树的模拟实现

二叉树的数据结构

基本功能实现

树初始化和销毁

遍历方式

遍历方式的概念解释：

遍历方式的代码模拟实现：

层序遍历

计算树的节点个数

二叉树叶子结点个数

二叉树k层结点个数

二叉数的最大深度

查找元素

判断是否为完全二叉树

链式二叉树的模拟实现

二叉树的数据结构

typedef int TreeDateType; typedef struct TreeNODE { TreeDateType data; struct TreeNODE* left; struct TreeNODE* right; }TreeNODE; typedef struct Tree { TreeNODE* phead; int size; }Tree;

基本功能实现

树初始化和销毁

void TreeInit(Tree* head)//初始化 { head->size = 0; head->phead = NULL; return; } void Treedestory(TreeNODE* ptr)//销毁一 { if (ptr == NULL) { return; } Treedestory(ptr->left);//后序遍历 Treedestory(ptr->right); free(ptr); ptr = NULL; return; } void TreeDestory(Tree* head)//销毁二 { Treedestory(head->phead); head->size = 0; return; }

遍历方式

遍历方式的概念解释：

树是一个非线性的数据结构我们就不能以普通的顺序遍历方式来遍历，二叉树的遍历方式多了三种：前序遍历、中序遍历和后序遍历。

如何理解这三种遍历方式呢？我们知道二叉树是由一个根节点和两个向下分支出来的两个节点构成，三种遍历方式就是以三个围绕张开的遍历方式。为了方便理解我们把三个节点分为：根、左、右，来理解。

  • 前序遍历：根->左->右
  • 中序遍历：左->根->右
  • 后序遍历：左->右->根

记住一定是无论根在哪个位置，都是左优先在右。

以上图的二叉树为例：

  • 前序遍历的输出打印方式就是：1 2 4 5 3 6 7

以为以1 2 3 为一个节点来说那么就是优先打印1，然后走到2；而 2 4 5又是一个节点那么就优先打印 2 然后在走到 4 ；4也是一个节点但是没有其他两节点了，所以只 打印出 4 就返回到 2 4 5的节点中，再走到 5 同理就打印出 5 ，2 4 5 这整个节点打印结束就回到 1 2 3 的节点中，同样的方式打印出剩下的节点，所以打印出来的是1 2 4 5 3 6 7。

  • 中序遍历打印方式：4 2 5 1 6 3 7.（功能介绍与前序遍历方法类似）
  • 后序遍历打印方式：4 5 2 6 7 3 1 （功能介绍与前序遍历方法类似）
遍历方式的代码模拟实现：

我们其实在观察概念的时候其实也不难看出，二叉树的章节的代码实现其实已经很明显的看出，都要以函数递归来实现代码的，的确无论实现前中后序遍历都是需要到函数递归来实现。

void preorder(TreeNODE* ptr)//前序打印 { if (ptr == NULL) { return; } printf("%d ", ptr->data); preorder(ptr->left); preorder(ptr->right); return; } void inorder(TreeNODE* ptr)//中序打印 { if (ptr == NULL) { return; } inorder(ptr->left); printf("%d ", ptr->data); inorder(ptr->right); return; } void postorder(TreeNODE* ptr)//后序打印 { if (ptr == NULL) { return; } postorder(ptr->left); postorder(ptr->right); printf("%d ", ptr->data); return; } void Tree_print (Tree* head,void* Print(TreeNODE*))//输出打印 { Print(head->phead); printf("\n"); return; }

我的这套代码是通过函数回调函数来实现函数的打印输出，通过Tree_print 函数 传参结构体和相关的遍历打印输出函数来实现。

void Treetest() { Tree head; TreeInit(&head); Treepush(&head, 1); Treepush(&head, 2); Treepush(&head, 3); Treepush(&head, 4); Treepush(&head, 5); Treepush(&head, 6); Treepush(&head, 7); Tree_print(&head, preorder); Tree_print(&head, inorder); Tree_print(&head, postorder); TreeDestory(&head); return; } int main() { Treetest(); return 0; }

输出结果

层序遍历

除了三种遍历方式之外还有一种的就是层序遍历，功能描述就是以按顺序的每一层的数值依次打印出来

以图上的二叉树为例打印出来就是1 2 3 4 5 6 7。

那么我们要实现改代码就要用到之前的数据结构的知识：队

必要操作：

沿用以前的写过的队的数据结构或者先写也可以，基本功能的保证，初始化，销毁，入队和出队的功能（输出可不用），将原本typedef int QUEDatatype 的 int 类型或者其他改成TreeNODE* 的树节点结构体类型。

queue.c 和queue.h 的文件拷贝一份到对应的现在写的Tree.c 文件当前位置并且Tree.c 文件内要有

#include "queue.h"的库的调用。

queue.h

#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef struct TreeNODE* QUEDatatype; typedef struct queuenode { QUEDatatype data; struct queuenode* next; }QN; typedef struct queue { QN* phead;//头 QN* ptail;//尾 int size; }Q; //队头>>>>>>>队尾 void queue_init(Q* queue);//初始化 void queue_destory(Q* queue);//销毁队 void queue_push(Q* queue, QUEDatatype a);//入队 void queue_pop(Q* queue);//出队函数 void queue_print(Q* queue);//输出

queue.c

#include "queue.h" void queue_init(Q* queue)//初始化 { queue->phead = queue->ptail = NULL; queue->size = 0; return; } void queue_destory(Q* queue)//销毁队 { QN* dest; while (queue->phead) { dest = queue->phead; queue->phead = queue->phead->next; free(dest); queue->size--; } queue->ptail = NULL; return; } void queue_push(Q* queue, QUEDatatype a)//入队 { QN* node = (QN*)malloc(sizeof(QN)); if (node == NULL) { perror("malloc"); exit(1); } node->data = a; node->next = NULL; if (queue->phead == NULL) { queue->phead = node; queue->ptail = node; queue->size++; } else { queue->ptail->next = node; queue->ptail = node; queue->size++; } return; } void queue_pop(Q* queue)//出队函数 { if (queue->size) { QN* pop = queue->phead; queue->phead = queue->phead->next; free(pop); queue->size--; if (queue->phead == NULL) queue->ptail = NULL; } return; } void queue_print(Q* queue)//输出 { QN* p = queue->phead; while (p != NULL) { printf("%p ->", (void*)p->data); p = p->next; } printf("\n"); return; }

Tree.c

#include "Tree.h" #include "queue.h"

实现思路：

要实现该代码的原理也不困难，肯定必不可少的就是循环的利用，或者递归，当然如果在一开始的时候我们没办法想象到如何运用递归的知识还是保险起见还是先用循环来实现。

我们要实现循环可先分为三个部分，头、过程和尾的部分

头的功能就是延续循环的根本、过程就是功能的实现，尾就是能使循环逐渐停止的功能。

头：queue_push 入队 判断队的节点的树左右节点是否有内容，需不需要入队

过程：printf("%d ", queue.phead->data->data); 打印输出队尾

尾：queue_pop(&queue); 出队头。

代码展示：

void level_order(TreeNODE* ptr)//顺序打印 { Q queue; queue_init(&queue); queue_push(&queue, ptr); while (queue.phead) { if (queue.phead->data->left) { queue_push(&queue, queue.phead->data->left); } if (queue.phead->data->right) { queue_push(&queue, queue.phead->data->right); } printf("%d ", queue.phead->data->data); queue_pop(&queue); } queue_destory(&queue); return; } void Tree_print (Tree* head,void* Print(TreeNODE*))//输出打印 { Print(head->phead); printf("\n"); return; }
void Treetest() { Tree head; Tree_init(&head); Tree_push(&head, 1); Tree_push(&head, 2); Tree_push(&head, 3); Tree_push(&head, 4); Tree_push(&head, 5); Tree_push(&head, 6); Tree_push(&head, 7); Tree_print(&head, level_order); Tree_destory(&head); return; }

类似的就是层序的写入功能也是一样的。

TreeNODE* Tree_malloc(TreeDateType a) { TreeNODE* node = (TreeNODE*)malloc(sizeof(TreeNODE)); if (node == NULL) { perror("malloc"); return NULL; } node->data = a; node->left = NULL; node->right = NULL; return node; } void Tree_push(Tree* head,TreeDateType a)//层序写入 { if (head->phead == NULL) { head->phead = Tree_malloc(a); return; } Q queue; queue_init(&queue); queue_push(&queue, head->phead); while (1) { if (queue.phead->data->left == NULL) { queue.phead->data->left = Tree_malloc(a); break; } if (queue.phead->data->right == NULL) { queue.phead->data->right = Tree_malloc(a); break; } queue_push(&queue, queue.phead->data->left); queue_push(&queue, queue.phead->data->right); queue_pop(&queue); } head->size++; queue_destory(&queue); return; }

通过层序直到遇到对应位NULL的位置就通过malloc 创建空间退出循环销毁 queue。实现树的层序遍历的创建。

计算树的节点个数

//计算树的节点个数 1 int Tree_size_1(Tree* ptr) { return ptr->size; } //计算树的节点个树 2 int Tree_size_2(TreeNODE* ptr) { if (ptr == NULL) { return 0; } return 1 + Tree_size_2(ptr->left) + Tree_size_2(ptr->right); }

两种方式就是在的设置树的节点的时候已经有预留一个空间来存取size 的大小，另一种就是没有预留空间来存取，那么就直接计算，无论是什么遍历方式都可以，我这里用的就是前序遍历的方式来实现数值的递归放回的进行计算。

二叉树叶子结点个数

要求：计算末端节点的个数

int Tree_leaf_size(TreeNODE* ptr) { if (ptr == NULL) { return 0; } if (ptr->left == NULL && ptr->right == NULL) { return 1; } return Tree_leaf_size(ptr->left) + Tree_leaf_size(ptr->right); }

二叉树k层结点个数

要求：计算出k 层的节点个数

int Tree_levelK_size(TreeNODE* ptr, int k) { if (k == 1 && ptr != NULL)//是否符合条件 { return 1; } else if (ptr == NULL)//判断为空指针 { return 0; } return Tree_levelK_size(ptr->left, k - 1) + Tree_levelK_size(ptr->right, k - 1);//递归 }

二叉数的最大深度

要求：计算出的二叉树的最大深度

int Tree_depth(TreeNODE* ptr) { if (ptr == NULL)//判断为空指针 { return 0; } if (Tree_depth(ptr->left) >= Tree_depth(ptr->right))//比较长短 { return 1 + Tree_depth(ptr->left); } else { return 1 + Tree_depth(ptr->right); } }

查找元素

要求：查找 a 元素所在位置，并且返回地址，如果没有就直接访问 NULL（空指针）

TreeNODE* Tree_find(TreeNODE* ptr,TreeDateType a) { if (ptr == NULL)//判断为空 { return NULL; } if (ptr->data == a)//识别是否为所需元素 { return ptr; } TreeNODE* find = Tree_find(ptr->right, a);//递归 if (find != NULL) { return find; } return Tree_find(ptr->left, a);//递归 } /* 因为指针和return 的条件，不能直接使用两个return */

判断是否为完全二叉树

bool Tree_complete(Tree* ptr) { Q queue; int input = 0;//0 就是未遇到NULL 1 遇到NULL进行 queue_init(&queue); queue_push(&queue, ptr->phead); while (queue.phead && !input) { if (queue.phead->data->left == NULL && !input) { input = 1; } else { queue_push(&queue, queue.phead->data->left); } if (queue.phead->data->right == NULL && !input) { input = 1; } else { queue_push(&queue, queue.phead->data->right); } if(!input) queue_pop(&queue); } while (input) { if (queue.phead->data != NULL) { if (queue.phead->data->left != NULL && input) { input = 0; } if (queue.phead->data->right != NULL && input) { input = 0; } queue_pop(&queue); } else { break; } } queue_destory(&queue); return input; }
void Treetest() { Tree head; Tree_init(&head); Tree_push(&head, 1); Tree_push(&head, 2); Tree_push(&head, 3); Tree_push(&head, 4); Tree_push(&head, 5); Tree_push(&head, 6); Tree_push(&head, 7); Tree_push(&head, 8); Tree_push(&head, 9); head.phead->right->right->right=Tree_malloc(10); //Tree_print(&head, pre_order); //Tree_print(&head, in_order); //Tree_print(&head, post_order); Tree_print(&head, level_order); printf("%d\n", Tree_size_2(head.phead)); printf("%d\n", Tree_leaf_size(head.phead)); printf("%d\n", Tree_levelK_size(head.phead,3)); printf("%d\n", Tree_depth(head.phead)); printf("%p\n", Tree_find(head.phead, 10)); printf("%d\n", Tree_complete(&head)); Tree_destory(&head); return; }

感谢观看！！！

悠仁さん

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/9/14 17:54:19

yq Pipe 管道操作符：把一个表达式接进下一个表达式

yq Pipe 管道操作符&#xff1a;把一个表达式接进下一个表达式 【免费下载链接】yq yq is a portable command-line YAML, JSON, XML, CSV, TOML, HCL and properties processor 项目地址: https://gitcode.com/GitHub_Trending/yq/yq yq 是一款可移植的 YAML、JSON、XM…

作者头像 李华
网站建设 2026/9/14 17:52:49

闲鱼90元戴尔准系统改造NAS：1800元配置单与实战

上个月我蹲闲鱼的时候又刷到一台戴尔OptiPlex 7010 USFF&#xff0c;卖家标价90块&#xff0c;裸机&#xff0c;不带电源适配器&#xff0c;侧面还缺一颗螺丝。我犹豫了大概十秒钟&#xff0c;拍了。这种老准系统改NAS的玩法&#xff0c;是我这两年折腾下来觉得最划算的方案。整…

作者头像 李华
网站建设 2026/9/14 17:52:39

CentOS 7.9停服后如何换阿里源？yum仓库配置与排错全指南

1. 不换源真不行&#xff1a;CentOS 7.9官方仓库停服后的连锁反应接手一台CentOS 7.9服务器&#xff0c;我建议你第一件事先看yum源。很多人新装完系统&#xff0c;习惯性敲一句yum install -y vim&#xff0c;等了好几分钟才发现要么卡在"Loading mirror speeds from cac…

作者头像 李华
网站建设 2026/9/14 17:51:23

Flutter与OpenHarmony开发视力保护App的反馈系统实现

1. 项目背景与核心需求视力保护提醒App在数字时代显得尤为重要。随着人们每天面对电子屏幕的时间越来越长&#xff0c;眼睛疲劳、干涩等问题日益普遍。这款基于Flutter和OpenHarmony开发的App&#xff0c;核心功能是通过定时提醒帮助用户养成科学用眼的习惯。意见反馈系统作为A…

作者头像 李华
网站建设 2026/9/14 17:51:01

DAB变换器控制策略：PI与MPC对比分析

1. 双有源全桥DAB变换器控制策略概述双有源全桥&#xff08;Dual Active Bridge, DAB&#xff09;变换器作为现代电力电子系统中的关键部件&#xff0c;在中大功率DC/DC转换领域占据重要地位。这种拓扑结构因其独特的双向能量传输能力和高频电气隔离特性&#xff0c;被广泛应用…

作者头像 李华