数据结构（c语言）——树和二叉树（基础）
树是一种非线性的数据结构，它是由n个（n>=0）个有限节点组成的也该具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下的。
·
1. 树
1.1 树的概念与结构
1.1.1树的概念
树是一种非线性的数据结构，它是由n个（n>=0）个有限节点组成的也该具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下的。
1.1.2 树的结构
- 一棵树由根节点和若干子树构成。
- 除根节点外，其余节点被分成M（M>0）个互不相交的集合T1、T2、……、Tm，其中每个集合Ti（1 <= i <= m）又是一颗结构与树类似的子树。每颗子树的根节点有且只有一个前驱，可以有0个或多个后继，因此树是递归定义的。
树形结构： 非树形结构：
1.1.3 树的相关术语
节点（Node）：树中的每个元素称为节点，节点包含数据及指向子节点的引用。
根节点（Root）：树的顶层节点，没有父节点，是树的起点。
父节点/双亲节点（Parent）：一个节点含有的子树的根节点称为该节点的子节点。
子节点/孩子节点（Child）：一个节点的直接下级节点称为其子节点。
节点的度（Degree）：一个节点有几个孩子节点，它的度就是多少。左图，A的度是3
树的度（Degree）：一棵树中，最大的节点的度称为树的度。左图，树的度是3
叶子节点/终端节点（Leaf）：没有子节点（度为0）的节点。左图，F、H、I、J、K、L
分支节点/非终端节点（Non-leaf）：至少有一个子节点（度不为0）的节点。左图，B、C、D、E、G
内部节点（Internal Node）：至少有一个子节点的非根节点。
祖先节点（Ancestor）：从根节点到某节点路径上的所有节点。
兄弟节点（Sibling）：同一父节点的子节点互为兄弟节点。
后代节点（Descendant）：某节点的子树中的所有节点。
森林（Forest）：m（m>0）棵互不相交的树的集合。
边（Edge）：连接两个节点的线段，表示父子关系。
路径（Path）：从一个节点到另一个节点的边序列，路径长度为边的数量。A 到 I：A-D-I
层级（Level）：根节点为第1层，其子节点为第2层，以此类推。
高度（Height）：该节点到其最远叶子节点的路径长度，叶子节点高度为0，树的高度就是根节点到最远叶子结点的高度=树中节点的最大层次。
深度（Depth）：根节点到该节点的路径长度，根节点深度为0。
1.1.4树的性质
- 树形结构中，子树之间不能有交集，否则就不是树结构。
- 除了根节点外，每个节点有且仅有一个父节点
- 一棵N个节点的树有N-1条边。
1.2 树的表示
孩子兄弟表示法：
1.3 树形结构实际应用场景
文件系统管理
树形结构在计算机文件系统中广泛应用。目录作为节点，文件作为叶子节点，形成层级关系。这种结构便于用户按逻辑分类存储和检索数据。操作系统通过树形结构实现高效的文件遍历和存储空间分配。
2. 二叉树
2.1 二叉树的概念与结构
2.1.1 概念
二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树是递归定义的，一颗二叉树是节点的一个有限集合，该集合由根节点和左、右子树组成或者为空，左右子树也是二叉树。
2.1.2 结构
二叉树的结构特点：
1. 二叉树不存在度大于2的节点。（0、1、2）
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
2.2 特殊的二叉树
2.21 满二叉树
一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。
也就是说，如果一个二叉树的层数为k，且节点总数是
，则她就是满二叉树。
2.2.2 完全二叉树
完全二叉树是效率很高的数据结构，所有层除了最后一层都外节点个数都达到最大，且完全二叉树的节点从左到右依次排列。满二叉树是一种特殊的完全二叉树。
2.2.3 二叉树的性质
由满二叉树的特点可知：1. 若规定根节点的层数为1，则一颗非空二叉树的第 i 层上最多有个节点。
2. 若规定根节点的层数为1，则深度为 h 的二叉树的最大节点数是。
3. 若规定根节点的层数为1，具有n个节点的满二叉树的深度。
2.3 二叉树的存储结构
二叉树一般可以使用两种存储结构：顺序结构、链式结构。
2.3.1 顺序结构
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树。
（不是完全二叉树会有空间的浪费）。
现实中我们通常把堆（一种二叉树）使用给顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆不同，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
2.3.2 链式结构
链式结构就是使用链表来存储，即通过指针或引用来表示节点之间的关系。
通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址。
链式结构又分为二叉链和三叉链。
3. 实现顺序结构二叉树
堆是一种特殊的二叉树，一般使用顺序结构的数组来存储数据具有二叉树的特性的同时，还具备其他的特性。
3.1 堆的概念与结构
如果有一个关键码的集合
，把它的所有元素按完全二叉树的顺序存储方式存储在一个一位数组中，并满足：
，
且
，
，
则称为小堆（或大堆）。
堆是一种完全二叉树。堆中某个节点的值总是不大于或不小于其父节点的值。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
- 最大堆：每个节点的值大于或等于其子节点的值（根节点为最大值）。
- 最小堆：每个节点的值小于或等于其子节点的值（根节点为最小值）。
由二叉树的性质：
对于具有n个节点的完全二叉树，如果按照从上至下，从左至右的数组顺序对所有节点从0开始编号，则对于序号为 i 的节点有：
1. i=0，i 为根节点编号，无父节点；i>0，i 位置节点的父节点序号：
2. 当2i +1<n，2i+2<n时，有左孩子和右孩子，左孩子序号：2i+1，右孩子序号：2i+2。
当2i+1>=0，没有左孩子；当2i+2>=0，没有右孩子；
3.2 堆实现
堆排序
一般情况下：
排升序：建大堆
排降序：建小堆
同样也有向上调整算法建堆（画图累，省之，详见代码），两者时间复杂度如下：
向上调整算法建堆的时间复杂度为：
向下调整算法建堆的时间复杂度为：
堆排序的时间复杂度：
默认为以2为底的对数
Heap.h文件
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
//定义堆结构
typedef int HPDataType;
typedef struct Heap {
HPDataType* arr;
int size;//有效数据个数
int capacity;//空间大小
}HP;
//初始化堆
void HPInit(HP* php);
//销毁堆
void HPDesTroy(HP* php);
//打印
void HPPrint(HP* php);
//堆的插入
void HPPush(HP* php, HPDataType x);
//判断堆是否为空
bool HPEmpty(HP* php);
//出堆顶
void HPPop(HP* php);
//取堆顶操作
HPDataType HPTop(HP* php);
//交换
void Swap(int* x, int* y);
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);
//向上调整算法
void AdjustUp(HPDataType* arr, int child);Heap.c文件
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
//初始化堆
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
//销毁堆
void HPDesTroy(HP* php)
{
assert(php);
if (php->arr)
{
free(php->arr);
}
php->arr = NULL;
php->size = php->capacity = 0;
}
//打印
void HPPrint(HP* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->arr[i]);
}
printf("\n");
}
//交换的算法
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//建大堆：>
//建小堆：<
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//找与parent比较的孩子
//建大堆：找最大的孩子，用 <
//建小堆：找最大的孩子，用 >
if (child + 1 < n && arr[child] < arr[child + 1])//child+1要求<n,否则可能越界
{
child++;
}
//孩子和父亲比较
//建大堆：>
//建小堆：<
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
//堆的插入
void HPPush(HP* php, HPDataType x)
{
assert(php);
//空间不够要增容
if (php->size == php->capacity)
{
//增容
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}
//空间足够
php->arr[php->size] = x;
//向上调整
AdjustUp(php->arr, php->size);
++php->size;
}
//判断堆是否为空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//出堆顶
void HPPop(HP* php)
{
assert(!HPEmpty(php));
Swap(&php->arr[0], &php->arr[php->size - 1]);
--php->size;
//堆盯需要向下调整
AdjustDown(php->arr, 0, php->size);
}
//取堆顶操作
HPDataType HPTop(HP* php)
{
assert(php);
return php->arr[0];
}test.c文件
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
void test01()
{
HP hp;
HPInit(&hp);
HPPush(&hp, 25);
HPPush(&hp, 15);
HPPush(&hp, 10);
HPPush(&hp, 56);
HPPush(&hp, 70);
HPPush(&hp, 30);
HPPrint(&hp);
//HPPop(&hp);
//HPPrint(&hp);
//HPPop(&hp);
//HPPrint(&hp);
//HPPop(&hp);
//HPPrint(&hp);
////循环取堆顶(大堆—降序的队列)(小堆—升序)
//while (!HPEmpty(&hp))
//{
// int top = HPTop(&hp);
// printf("%d ", top);
// HPPop(&hp);
//}
HPDesTroy(&hp);
}
//堆排序（但不是真正的堆排序）
void HeapSort1(int* arr, int n)
{
HP hp;//使用数据结构——堆
HPInit(&hp);
//调用push将数组中的数据放入堆中
for (int i = 0; i < n; i++)
{
HPPush(&hp, arr[i]);
}
printf("\n");
int i = 0;
while (!HPEmpty(&hp))
{
int top = HPTop(&hp);
arr[i++] = top;
HPPop(&hp);
}
}
//堆排序（使用堆结构的思想）
void HeapSort(int* arr, int n)
{
//乱序数组——向下调整算法建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
////乱序数组——向上调整算法建堆
//for (int i = 0; i < n; i++)
//{
// AdjustUp(arr, i);
//}
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
//冒泡排序
void BubbleSort(int* arr, int n)
{
for(int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] < arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
}
}
}
}
int main()
{
//test01();
int arr[6] = { 25,15,10,56,70,30 };
printf("排序之前：\n");
for (int i = 0; i < 6; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
////堆排序(非真正)
//HeapSort1(arr,6);
//堆排序（堆思想）
HeapSort(arr,6);
////冒泡排序
//BubbleSort(arr, 6);
printf("排序之后：\n");
for (int i = 0; i < 6; i++)
{
printf("%d ", arr[i]);
}
return 0;
}4. 实现链式结构二叉树
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通过节点结构体与指针实现，每个节点由三个域组成，数据域和左右指针域。左右指针分别用来给出该节点左孩子和右孩子所在链节点的存储地址。
4.1 二叉树的遍历
前序遍历：先遍历根节点，再遍历左子树，最后遍历右子树。（根左右）
中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树。（左根右）
后序遍历：先遍历左子树，再遍历右子树，最后遍历根节点。（左右根）
层序遍历：按照层次依次遍历。（从上到下，从左到右）
深度优先遍历：前中后序遍历
广度优先遍历：层序遍历
4.2 堆实现
参考代码：
Tree.h文件（结构定义和函数声明）
#pragma once
#include<stdio.h>
#include<stdlib.h>
//定义二叉树节点结构
typedef char BTDataType;
typedef struct BinaryTreeNode{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历——借用数据结构：队列
void Leve1Order(BTNode* root);Tree.c文件（函数实现）
#define _CRT_SECURE_NO_WARNINGS
#include"Tree.h"
//前序遍历
void PreOrder(BTNode* root)//递归
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)//递归
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)//递归
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
//层序遍历——借助数据结构：队列
void Leve1Order(BTNode* root)
{
}
// ⼆叉树结点个数
//节点总数=1+左子树节点个数+右子树节点个数
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 == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)//递归
{
if (root == NULL)
{
return 0;
}
//判断是否为第k层
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
//⼆叉树的深度/⾼度
//二叉树的高度=根节点+max(左子树的高度，右子树的高度)
int BinaryTreeDepth(BTNode* root)//递归
{
if (root == NULL)
{
return 0;
}
int leftDep = BinaryTreeDepth(root->left);
int rightDep = BinaryTreeDepth(root->right);
//根节点+max(左子树的高度，右子树的高度)
return 1 + (leftDep > rightDep ? leftDep : rightDep);
}
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//递归
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftFind = BinaryTreeFind(root->left, x);
if (leftFind)
{
return leftFind;
}
BTNode* rightFind = BinaryTreeFind(root->right, x);
if (rightFind)
{
return rightFind;
}
return NULL;
}
// ⼆叉树销毁——后序遍历
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}test.c文件（测试文件）
#define _CRT_SECURE_NO_WARNINGS
#include"Tree.h"
BTNode* buyNode(char x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
BTNode* createTree()
{
BTNode* nodeA = buyNode('A');
BTNode* nodeB = buyNode('B');
BTNode* nodeC = buyNode('C');
BTNode* nodeD = buyNode('D');
BTNode* nodeE = buyNode('E');
BTNode* nodeF = buyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
void test01()
{
BTNode* root = createTree();
//PreOrder(root);
//InOrder(root);
//PostOrder(root);
printf("size:%d\n", BinaryTreeSize(root));
printf("leaf size:%d\n", BinaryTreeLeafSize(root));
printf("K leve1 size:%d\n", BinaryTreeLevelKSize(root,2));
printf("Tree Depth:%d\n", BinaryTreeDepth(root));
BTNode* find = BinaryTreeFind(root, 'A');
if (find)
{
printf("找到了！\n");
}
else {
printf("未找到！\n");
}
BinaryTreeDestory(&root);
}
int main()
{
test01();
return 0;
}4.3 动手实现
参考代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
//******************************************************二叉树结构定义和函数实现
//定义二叉树节点结构
typedef char BTDataType;
typedef struct BinaryTreeNode {
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//创建二叉树
void CreateBinaryTree(BTNode** b,char* arr)
{
BTNode* St[MaxSize], * newNode = NULL;
int top = -1, k , j = 0;
char ch;
*b = NULL;
ch = arr[j];
while (ch != '\0')
{
switch(ch)
{
case'(':top++; St[top] = newNode; k = 1; break;
case')':top--; break;
case',':k = 2; break;
default:newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode == NULL)
{
perror("malloc failed");
exit(1);
}
newNode->data = ch;
newNode->left = newNode->right = NULL;
if (*b == NULL)
*b = newNode;
else
{
switch (k)
{
case 1:St[top]->left = newNode; break;
case 2:St[top]->right = newNode; break;
}
}
}
j++;
ch = arr[j];
}
}
//输出二叉树
void PrintBinaryTree(BTNode* b)//递归
{
if (b == NULL)
{
return;
}
printf("%c", b->data);
if (b->left!=NULL || b->right != NULL)
{
printf("(");
PrintBinaryTree(b->left);
if (b->right != NULL)
printf(",");
PrintBinaryTree(b->right);
printf(")");
}
}
// ⼆叉树查找x的结点的左右孩子
BTNode* BinaryTreeFind(BTNode* b, BTDataType x)//递归
{
if (b == NULL)
{
return NULL;
}
if (b->data == x)
{
return b;
}
BTNode* leftFind = BinaryTreeFind(b->left, x);
if (leftFind)
{
return leftFind;
}
BTNode* rightFind = BinaryTreeFind(b->right, x);
if (rightFind)
{
return rightFind;
}
return NULL;
}
//⼆叉树的⾼度
//二叉树的高度=根节点+max(左子树的高度，右子树的高度)
int BinaryTreeDepth(BTNode* b)//递归
{
if (b == 0)
{
return 0;
}
int leftDep = BinaryTreeDepth(b->left);
int rightDep = BinaryTreeDepth(b->right);
//根节点+max(左子树的高度，右子树的高度)
return 1 + (leftDep > rightDep ? leftDep : rightDep);
}
// ⼆叉树结点个数
//节点总数=1+左子树节点个数+右子树节点个数
int BinaryTreeSize(BTNode* b)//递归
{
if (b == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(b->left) + BinaryTreeSize(b->right);
}
// ⼆叉树叶⼦结点个数
//叶子节点个数=左子树叶子节点个数+右子树叶子节点个数
int BinaryTreeLeafSize(BTNode* b)//递归
{
if (b == NULL)
{
return 0;
}
//判断是否为叶子节点
if (b->left == NULL && b->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(b->left) + BinaryTreeLeafSize(b->right);
}
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* b, int k)//递归
{
if (b == NULL || k < 1)
{
return 0;
}
//判断是否为第k层
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(b->left, k - 1) + BinaryTreeLevelKSize(b->right, k - 1);
}
// ⼆叉树销毁——后序遍历
void BinaryTreeDestory(BTNode** b)
{
if (*b == NULL)
{
return;
}
BinaryTreeDestory(&((*b)->left));
BinaryTreeDestory(&((*b)->right));
free(*b);
*b = NULL;
}
//******************************************************测试代码
int main()
{
BTNode* b = NULL;
printf("二叉树的基本运算如下：\n");
printf("（1）创建二叉树：\n");
CreateBinaryTree(&b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("（2）输出二叉树：\n");
PrintBinaryTree(b);
printf("\n");
printf("（3）H结点：");
BTNode* p = BinaryTreeFind(b, 'H');
if (p == NULL)
{
printf("未找到H节点\n");
}
else {
if (p->left == NULL)
printf("无左孩子");
else
printf("左孩子为%c", p->left->data);
if (p->right == NULL)
printf("无右孩子");
else
printf("右孩子为%c", p->right->data);
}
printf("\n");
printf("（4）二叉树的高度：%d\n", BinaryTreeDepth(b));
printf("（5）二叉树结点个数：%d\n", BinaryTreeSize(b));
printf("（6）二叉树叶子结点个数：%d\n", BinaryTreeLeafSize(b));
printf("（7）二叉树第2层结点个数：%d\n", BinaryTreeLevelKSize(b, 2));
printf("（8）释放二叉树b\n");
BinaryTreeDestory(&b);
return 0;
}程序流程：
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
8
0- 0
已为社区贡献1条内容
所有评论(0)