码字不易，对你有帮助 点赞/转发/关注 支持一下作者
微信搜公众号：不会编程的程序圆
看更多干货，获取第一时间更新
【数据结构轻松学】系列 Github ：https://github.com/hairrrrr/Date-Structure
本文的代码已上传至 Github
注意： 实现的代码比较多，就不再本文里写了，想看的去 github 上看吧，记得 star 哦~
一 二叉树
0. 二叉树性质
- 若规定根节点的层数为1，则一棵非空二叉树的**第 i 层 **上最多有 2^( i - 1) 个结点.
- 若规定根节点的层数为1，则 深度为 h的二叉树的最大结点数是 2^h - 1.
- 对任何一棵二叉树, 如果度为 0 其叶结点个数为n0，度为 2 的分支结点个数为 n2，则有 n0＝ n2＋1
1. 存储方式
顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的
浪费
image
parent：
- left_child = 2 * parent + 1
- right_child = 2 * parent + 2
child：
- parent = (child - 1) / 2
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表
中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结
点的存储地址 。
image
二 堆
1. 最大堆和最小堆
image
向下调整思想:小堆
从当前需要调整的位置开始，parent
a.从左右孩子中选一 个最小的child
b.如果最小的 child 仍然小于 parent:
交换 child 和 parent
更新: parent = child, child = 2 * parent + 1
如果 child 没有越界，跳到a, 继续执行
如果 child 越界，结束调整如果最小的child仍然大于parent:结束调整
2. 最小堆的建立和插入
堆的向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整
成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
image
堆的创建
我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆
int a[] = {1,5,3,8,7,6};
image
堆的插入
使用向上调整算法
image
接口：
#include <stdlib.h>
#include <memory.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _array;
int _size;
int _capacity;
}Heap;
void heapCreat(Heap* hp, HPDataType* array, int size);
void insertHeap(Heap* hp, HPDataType data);
void shiftDown(HPDataType* array, int size, int parent);
void shiftUp(HPDataType* array, int child);
void Swap(HPDataType* array, int idx1, int idx2);
void heapPrint(Heap* hp);
3. 堆的实现（完全版）
堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据交换，然后删除数组最后一个数据，再进行向下调
整算法
image
我觉得这个版本大家一定要看一下，程序圆花了 2 个小时重构才完成。
#ifndef _HEAP_H_
#define _HEAP_H_
#include<stdlib.h>
#include <memory.h>
#include<stdio.h>
#define MAX_HEAP 100 // 堆的最大容量
#define MINHEAP 0 // 最小堆的标记
#define MAXHEAP 1 // 最大堆的标记
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _array;
int _size;
int _capacity;
}Heap;
/******************** 接口函数 *******************/
void heapCreat(Heap* hp, HPDataType* array, int size, int flg);
void heapPush(Heap* hp, HPDataType data, int flg);
HPDataType heapPop(Heap* hp, int flg);
void heapPrint(Heap* hp);
#endif
4. 堆排序
image
// 堆排序
void heapSort(int* array, int size)
{
// 建堆
for (int parent = (size - 2) / 2; parent >= 0; parent--)
{
shiftDown(array, parent, size);
}
while (size > 1)
{
// 删除最大项（头删），然后将最后的元素补到根节点
Swap(array, 0, size - 1);
// 将总的大小减小，相当于是将最大的元素留在已排序好的区域
size--;
// 向下调整，将堆再次调整为最大堆
shiftDown(array, 0, size);
}
}
三 二叉树实现
0. 理解二叉树遍历
image
image
1. 接口
typedef char BTDataType;
typedef struct BinTree{
BTDataType Val;
struct BinTree* Left;
struct BinTree* Right;
}BinTree;
BinTree* BinaryTreeCreate(BTDataType* str, int* idx);
// 二叉树销毁
void BinaryTreeDestory(BinTree** root);
// 二叉树节点个数
int BinaryTreeSize(BinTree* root);
void BianryTreeSize2(BinTree* root, int* num);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BinTree* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BinTree* root, int k);
// 二叉树查找值为x的节点
BinTree* BinaryTreeFind(BinTree* root, BTDataType x);
四 二叉树遍历非递归
1.接口
// 二叉树前序非递归遍历
void BinaryTreePrevOrderNoR(BinTree* root);
// 二叉树前序遍历
void BinaryTreePrevOrder(BinTree* root);
// 二叉树中序非递归遍历
void BinaryTreeInOrderNoR(BinTree* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BinTree* root);
// 二叉树后序非递归遍历
void BinaryTreePostOrderNoR(BinTree* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BinTree* root);
// 层序遍历
void BinaryTreeLevelOrder(BinTree* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BinTree* root);
查看【数据结构轻松学】更详细的目录： https://github.com/hairrrrr/Date-Structure
不要忘记 star 呦~
欢迎大家在 评论区/私信 提出问题/指正错误，谢谢观看。
我是程序圆，我们下次再见。
网友评论