【数据结构】C语言实现二叉树(二叉树链式结构，结点个数，深度等)
上一篇学习了堆的排序，Topk问题等，如果大家需要可以去观看：
【数据结构】C语言实现二叉树超详细入门(堆的实现，堆排序，TopK问题)-ZEEKLOG博客
目录
一.二叉树链式结构的实现
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
typedef char data1; typedef struct BinaryTreeNode { data1 n; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(char x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode*)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->n = x; newnode->left = NULL; newnode->right = NULL; return newnode; } //返回二叉树的根节点,这不是真正意义上创建的二叉树，而是测试用例 BTNode* CreatBinaryTree() { 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'); nodeA->left = nodeB; nodeB->left = nodeD; nodeB->right = nodeE; nodeE->right = nodeH; nodeA->right = nodeC; nodeC->left = nodeF; nodeC->right = nodeG; return nodeA; }注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
1. 空树
2. 非空：根结点，根结点的左子树、根结点的右子树组成的
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
二.结点个数及高度等
1.二叉树结点个数
若二叉树为空树，结点个数为0；若二叉树不为空树，结点个数为：左子树 + 右子树 + 1(根结点)；
代码实现：
//二叉树结点个数 int BinaryTreeSize(BTNode* root) { //判断根是否为空 if (root == NULL) { return 0; } int leftsize = BinaryTreeSize(root->left); int rightsize = BinaryTreeSize(root->right); return leftsize + rightsize + 1; }说明：
这里的 leftsize 存储的是左子树的个数，rightsize 存储的是右子树的个数。
比如：若递归到3这个结点，先走左子树，左子树为空；走右子树，右子树也为空；然后走return 0+0+1；返回到2的左子树这个函数，然后把1存储到 leftsize 中；接着走右子树，右子树为空；然后return 1+0+1 .......以此回溯，直到回溯到根结点1，然后走右子树.......最后return 2+3+1，即该树的结点为6。
代码走读逻辑（清晰易懂）：
说明：
红色箭头为代码运行逻辑，红色数字为结点，蓝色为return 的运算过程，白色则存储的是左子树和右子树上结点的个数
2.二叉树叶子结点的个数
1.若二叉树为空树，则叶子节点的个数为0；
2.若二叉树不为空树，则叶子节点的个数为：左子树 + 右子树
说明：叶子节点是度为0的节点，所以该节点的左子树和右子树都为空时，则说明该节点为叶子节点，否则不为叶子节点。
代码实现：
//二叉树叶子结点的个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } int LeftLeafSize = BinaryTreeLeafSize(root->left); int RightLeafSize = BinaryTreeLeafSize(root->right); return LeftLeafSize + RightLeafSize; }大家可以模仿二叉树结点的个数中的走读逻辑自己动手操作，能够加深印象
3.二叉树的高度
1.若二叉树为空树，则高度为0；
2.若二叉树不为空树，则高度为：max{左子树高度 ，右子树高度} + 1 ；
代码实现：
//二叉树的高度 int BinaryTreeHighSize(BTNode* root) { if (root == NULL) { return 0; } int lefthigh = BinaryTreeHighSize(root->left); int righthigh = BinaryTreeHighSize(root->right); return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1; } 4.二叉树第k层结点的个数
思路：
每次递归让k--，直到k==1的时候，return 1；
代码实现：
//二叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root,int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } else { k--; } int LeftLeveKSize = BinaryTreeLevelKSize(root->left, k); int RightLeveKSize = BinaryTreeLevelKSize(root->right, k); return LeftLeveKSize + RightLeveKSize; }5.二叉树查找值为x的结点
1.若二叉树为空树，则结点为空；
2.若二叉树不为空树，则返回该结点；
说明：若二叉树中有多个结点与x相等，则只返回第一个找到的结点，因为该函数的返回值只能有一个
代码实现：
//二叉树查找值为x的结点 //函数只能返回一个值不能返回多个，所以找到该数直接返回，后面若还有就不管了 BTNode* BinaryTreeFind(BTNode* root, data1 x) { if (root == NULL) { return NULL; } if (x == root->n) { return root; } BTNode* leftnode = BinaryTreeFind(root->left, x); if (leftnode != NULL) { return leftnode; } BTNode* rightnode = BinaryTreeFind(root->right, x); if (rightnode != NULL) { return rightnode; } //如果都没找到返回空 return NULL; } 三.二叉树的创建及销毁
1.二叉树的销毁
//二叉树的销毁 void TreeDestory(BTNode* root) { if (root == NULL) { return; } TreeDestory(root->left); TreeDestory(root->right); free(root); }2.通过前序遍历数组构建二叉树
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include"Queue.h" typedef char data1; typedef struct BinaryTreeNode { data1 n; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(char x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode*)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->n = x; newnode->left = NULL; newnode->right = NULL; return newnode; } //返回二叉树的根节点,这不是真正意义上创建的二叉树，而是测试用例 BTNode* CreatBinaryTree() { 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'); nodeA->left = nodeB; nodeB->left = nodeD; nodeB->right = nodeE; nodeE->right = nodeH; nodeA->right = nodeC; nodeC->left = nodeF; nodeC->right = nodeG; return nodeA; } //通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* TreeCreate(data1* a, int* pi) { if (a[*pi] == '#') { (*pi)++; return NULL; } BTNode* root1 = (BTNode*)malloc(sizeof(BTNode)); if (root1 == NULL) { exit(1); } root1->n = a[(*pi)++]; root1->left = TreeCreate(a, pi); root1->right = TreeCreate(a, pi); return root1; } int main() { //构建二叉树 data1 arr[20] = { 'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#' }; int i = 0; BTNode* root1 = TreeCreate(arr, &i); //销毁二叉树 TreeDestory(root1); root1 = NULL; return 0; }3.判断二叉树是否是完全二叉树
前置声明：
说明：若要判断是否是完全二叉树，则需要用到层序遍历；用到层序遍历，则需要用到队列；所以说这里比较复杂，我将把队列的相关代码粘贴到这里，若要详细理解队列的知识，则可以看我之前写的关于队列的知识点。
思路：逐层遍历，出来一个结点，将它的孩子带入队列，直到出来是空结点，这时跳出循环，遍历队列，若队列中存在非空结点，则说明不是完全二叉树。
代码实现：
Queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //链式结构：表示队列 //相当于前置声明，队列中存放的是二叉树中结点指针的地址 typedef struct BinaryTreeNode* data; typedef struct QListNode { data a; struct QListNode* next; }QNode;//队列中的结点 //由于队列是先进先出，所以插入的时候都需要找尾结点，不如直接定义两个指针，一个指向头结点一个指向尾结点， //但是传递参数需要传递两个指针，不如将两个指针定义在一个结构体中，只用传递结构体即可 //队列的结构 typedef struct Queue { QNode* head; QNode* ptial; int size;//累计队列中有几个结点 }Queue; //初始化队列 void QueueInit(Queue* q);//两个指针都指向头结点 //void QueueInit(QNode* head, QNode* pital);//创建头结点可以传递一级指针，没有头结点要传递二级指针 //队尾入队列 void QueuePush(Queue* q, data x); //对头出队列 void QueuePop(Queue* q); //获取队列头部元素 data QueueFront(Queue* q); //获取队列尾部元素 data QueueBack(Queue* q); //判断队列是否为空 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestory(Queue* q); //队列中的元素个数 int QueueSize(Queue* q);Queue.c
#include"Queue.h" //初始化队列 void QueueInit(Queue* q) { q->head = NULL; q->ptial = NULL; q->size = 0; } //队尾入队列 void QueuePush(Queue* q, data x) { assert(q); //创建新结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("newnode fail"); exit(1); } newnode->next = NULL; newnode->a = x; if (q->ptial == NULL) { q->ptial = newnode; q->head = newnode; } else q->ptial->next = newnode; q->ptial = newnode; q->size++; } //对头出队列 void QueuePop(Queue* q) { //判断队列是否为空 assert(q); assert(q->head != NULL); ////存放第二个结点 //QNode* next = q->head->next->next; //free(q->head->next); //q->head->next = next; //q->size--; //没有将指针ptial置为空，成为野指针了 //一个结点 if (q->head->next == NULL) { free(q->head); q->head = q->ptial = NULL; } else { QNode* next = q->head->next; free(q->head); q->head = next; } q->size--; } //获取队列头部元素 data QueueFront(Queue* q) { assert(q); assert(q->head != NULL); return q->head->a; } //获取队列尾部元素 data QueueBack(Queue* q) { assert(q); assert(q->head != NULL); return q->ptial->a; } //判断队列是否为空 bool QueueEmpty(Queue* q) { assert(q); return q->size == 0; } //销毁队列 void QueueDestory(Queue* q) { assert(q); QNode* cur = q->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->head = q->ptial = NULL; q->size = 0; //QNode* cur = q->head; //while (cur) //{ // QNode* next = cur->next; // free(cur); // cur = next; //} //q->head = q->ptial = NULL; //q->size = 0; } //队列中的元素个数 int QueueSize(Queue* q) { assert(q); return q->size; }Test.c
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include"Queue.h" typedef char data1; typedef struct BinaryTreeNode { data1 n; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(char x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode*)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->n = x; newnode->left = NULL; newnode->right = NULL; return newnode; } //返回二叉树的根节点,这不是真正意义上创建的二叉树，而是测试用例 BTNode* CreatBinaryTree() { 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'); nodeA->left = nodeB; nodeB->left = nodeD; nodeB->right = nodeE; nodeE->right = nodeH; nodeA->right = nodeC; nodeC->left = nodeF; nodeC->right = nodeG; return nodeA; } //判断二叉树是否是完全二叉树 bool TreeComplete(BTNode* root) { //思路：利用层序遍历，将上一层的结点入队列，出来后带入其孩子进队列，直到出第一个空时，判断 //队列中是否还有非空的数，若有非空的数则说明不是完全二叉树 //创建队列 Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* Front = QueueFront(&q); QueuePop(&q); //判断遇到第一个空，队列中是否还有非空元素 if (Front == NULL) { break; } //不管是不是空都入队列 QueuePush(&q, Front->left); QueuePush(&q, Front->right); } while (!QueueEmpty(&q)) { BTNode* node = QueueFront(&q); QueuePop(&q); if (node) { QueueDestory(&q); return false; } } QueueDestory(&q); return true; } int main() { //构建二叉树 data1 arr[20] = { 'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#' }; int i = 0; BTNode* root1 = TreeCreate(arr, &i); //判断是否是完全二叉树 if (TreeComplete(root1)) { printf("该树为完全二叉树\n"); } else printf("该树不为完全二叉树\n"); //销毁二叉树 TreeDestory(root1); root1 = NULL; return 0; }四.总结
本文从二叉树链式结构实现、核心属性计算、树的创建销毁及完全二叉树判断四个维度，系统梳理了二叉树的核心操作与实现思路，为读者构建了清晰的知识框架。递归遍历是统计结点数、叶子数、树高等属性的核心方法，而层序遍历结合队列则是判断完全二叉树的关键，掌握这些逻辑能有效提升对二叉树的理解与应用能力。后续可结合中序、后序等遍历方式，以及线索二叉树、平衡二叉树等进阶结构，进一步深化二叉树相关知识的实践与拓展，为算法学习打下坚实基础。
通过本节课的学习相信你一定有所收获，如果对你有帮助，欢迎 点赞、收藏、关注，后续持续更新数据结构与算法！
下一篇我们讲解二叉树的遍历，超详细！
