网站飘窗 两学一做,网站做程序,lamp网站开发制作,装修装饰网站建设上一章我们介绍了二叉树入门的一些内容#xff0c;本章我们就要正式开始学习二叉树的实现方法#xff0c;先三连后看是好习惯#xff01;#xff01;#xff01; 目录
一、二叉树的顺序结构及实现
1. 二叉树的顺序结构
2. 堆的概念及结构
3. 堆的实现
3.1 堆的创建
… 上一章我们介绍了二叉树入门的一些内容本章我们就要正式开始学习二叉树的实现方法先三连后看是好习惯 目录
一、二叉树的顺序结构及实现
1. 二叉树的顺序结构
2. 堆的概念及结构
3. 堆的实现
3.1 堆的创建
3.2 堆的插入
3.3 向下调整算法
3.4 堆的删除
3.5 总体代码实现
4. 堆操作的时间复杂度
二、堆的应用
1. 堆排序
2. TOP-K问题
三、二叉树链式结构的实现
1. 前置说明
2. 二叉树的遍历
2.1 前/中/后序遍历
2.2 层序遍历
2.3 节点个数以及深度等
3. 二叉树的销毁 一、二叉树的顺序结构及实现
1. 二叉树的顺序结构 普通的二叉树不适合用数组来存储因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。 2. 堆的概念及结构 如果有一个关键码的集合 {, ,…,}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 且 则称为小堆(或大堆)。 大堆(大根堆)根节点最大所有父亲都≥孩子 小堆(小根堆)根节点最小所有父亲都≤孩子 堆的性质
堆中某个节点的值总是≥(或≤)其父节点的值成为大堆(或小堆)堆总是一棵完全二叉树 注意堆在数组里不是有序的小(大)堆可以帮我们找到最小(大)值即找到根节点。
3. 堆的实现
3.1 堆的创建 我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 3.2 堆的插入 先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 3.3 向下调整算法 我们给出一个数组逻辑上看做一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 3.4 堆的删除 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 3.5 总体代码实现 先在头文件中对相关功能接口进行声明
typedef int HPDataType;
//数组实现
typedef struct Heap
{HPDataType* a;//底层就是一个数组int size;int capacity;
}HP;
//堆的初始化和销毁
void HeapInit(HP* php);
void HeapInitArray(HP* php, HPDataType* a, int n);
void HeapDestroy(HP* php);
//向上调整算法
void AdjustUp(HPDataType* a, int child);
//往堆中插入数据
void HeapPush(HP* php, HPDataType x);
//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent);
//删除堆顶根节点
void HeapPop(HP* php);
//输出根节点
HPDataType HeapTop(HP* php);
//计算堆的大小
size_t HeapSize(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//堆排序
void HeapSort(int* a, int n);
//TOP-K问题
void PrintTopK(int* a, int n, int k); 下面是接口的具体实现
//堆的初始化和销毁
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}//将交换功能封装成Swap函数以便复用
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//以小堆为例
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//确保不会移动根节点因为根节点的索引为0没有父节点while (child 0){//孩子 父亲就要交换if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;//把父亲的位置给孩子parent (child - 1) / 2;//再算新的父亲}else{break;}}
}//往堆中插入数据
void HeapPush(HP* php, HPDataType x)
{assert(php);//空间不够需要扩容if (php-size php-capacity){//初始化时capacity0所以要先给他4个空间int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc);return;}//把原来的数组和容量更新成扩容之后的php-a tmp;php-capacity newCapacity;}php-a[php-size] x;//在尾部插入数据php-size;//插入一个数据后size要1//插入之后可能就不是堆了通过向上调整算法把它变成堆AdjustUp(php-a, php-size - 1);
}//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){//默认左孩子小假设错误就更新一下if (child 1 size a[child 1] a[child])//右孩子存在右孩子小于左孩子{child;//child是左孩子1就是右孩子}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//删除堆顶根节点
void HeapPop(HP* php)
{assert(php);assert(php-size 0);//至少要有一个节点//把堆顶的数据跟数组的尾元素交换位置//此时删除堆顶就变成了删除数组的尾元素Swap(php-a[0], php-a[php-size - 1]);php-size--;//删除操作就是控制size来完成的//其实我们并不是把这个数据删除而是把他反复在最后就不用管它了//size-1后想要访问这个数据就变成了数组越界访问AdjustDown(php-a, php-size, 0);
}//输出根节点
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}//计算堆的大小
size_t HeapSize(HP* php)
{assert(php);return php-size;
}//判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}
4. 堆操作的时间复杂度 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来就是近似值多几个节点不影响最终结果) 插入数据时间消耗主要在向上调整部分最好情况就是不进行调整最差情况就是调整树的高度次因此插入数据的时间复杂度为 。 删除数据时间消耗主要在向下调整部分最好情况就是不进行调整最差情况就是调整树的高度次因此删除数据的时间复杂度为 。
//按照数组来初始化
void HeapInitArray(HP* php, HPDataType* a, int n)
{assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (php-a NULL){perror(realloc);return;}memcpy(php-a, a, sizeof(HPDataType) * n);//把数据放到堆上php-size n;php-capacity n;//建堆//模拟向上调整理解为数据插入时间复杂度O(N*logN)//for (int i 1; i php-size; i)//{// AdjustUp(php-a, i);//}//第二层最多向上调整1次第三层最多向上调整2次……,最后一层最多向上调整h-1次//假设累计向上调整F(h)次,F(h)2^1*12^2*2…2^(h-1)*(h-1)2^h*(h-2)2//把F(h)转换成F(N),hlog(N1),因此F(N)(N1)*(log(N1)-2)2≈N*logN//模拟向下调整时间复杂度O(N)//从倒数的第一个非叶子结点开始调整(最后一个节点的父亲)倒着往上调//最后一个节点的下标是php-size - 1i求他的父亲然后开始倒着调整for (int i (php-size - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, php-size, i);}//假设累计向下调整F(h)次,F(h)2^(h-2)*12^(h-3)*2…2^0*(h-1)//F(N)N-log(N1)≈N
} 对于向上调整满二叉树最后一层结点数占整个树的一半结点数量多的层调整次数也多。而向下调整正好相反结点数量多的调整次数少。因此两种方法时间复杂度相差较大我们优先选择向下调整建堆。
二、堆的应用
1. 堆排序
void HeapSort(int* a, int n)
{HP hp;HeapInitArray(hp, a, n);int i 0;while (!HeapEmpty(hp)){a[i] HeapTop(hp);//将堆顶赋给a[0]HeapPop(hp);//删除堆顶元素这样堆中第二大/小的元素就会被移动到堆顶}HeapDestroy(hp);
} 上面这种写法有两大缺陷首先就是进行堆排序之前需要先创建堆的各种相关算法其次就是空间复杂度为 。 堆排序即利用堆的思想来进行排序总共分为两个步骤 [1] 建堆 升序建大堆 降序建小堆 [2] 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此通过向下调整就可以完成堆排序。 //大堆的向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){//默认左孩子大假设错误就更新一下 if (child 1 size a[child] a[child 1]) //右孩子存在且右孩子大于左孩子 {child; // child原本是左孩子1变成右孩子 }//如果子节点大于父节点则交换 if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//升序建大堆降序建小堆
//建小堆如果想要升序堆顶元素在对应位置剩余元素重新建小堆时间复杂度大大增加
void HeapSort(int* a, int n)
{//对数组直接建堆for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);//上面建的大堆根节点最大把大的数据往后放AdjustDown(a, end, 0);//新的根节点可能会破坏大堆性质需要向下调整end--;}
} 注意我们需要根据升序或降序的要求对向下调整算法进行修改。
2. TOP-K问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素。 对于Top-K问题最容易想到的方法就是排序但是如果数据量非常大排序就不可取了(可能数据不能一口气全部加载到内存中)。 最佳的方式就是用堆来解决基本思路如下 [1] 用数据集合中前K个元素来建堆 求前k个最大的元素则建小堆 求前k个最小的元素则建大堆 [2] 用剩余的N-K个元素依次与堆顶比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比较之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 这种方法的时间复杂度是 。
//以求前K个最大的数据为例则需要建小堆
void PrintTopK(int* a, int n, int k)
{HP php;HeapInit(php);//数组中前k个元素来建堆for (int i 0; i k; i) {HeapPush(php, a[i]);}//用剩余的n-k个元素依次与堆顶比较for (int i k; i n; i) {if (a[i] HeapTop(php)) //当前元素堆顶就要让他进堆{ HeapPop(php); //移除当前堆顶HeapPush(php, a[i]); //将新的元素插入堆中}}for (int i 0; i k; i) {printf(%d , php.a[i]);}printf(\n);HeapDestroy(php);
}
三、二叉树链式结构的实现
1. 前置说明 在学习二叉树的基本操作前需先创建一棵二叉树然后才能学习其相关操作。由于现在对二叉树结构掌握还不够深入因此在此处手动快速创建一棵简单的二叉树快速学习二叉树操作等后面再来研究二叉树真正的创建方式。 回顾下二叉树的概念二叉树是
空树非空根节点根节点的左子树、根节点的右子树组成的 从概念中可以看出二叉树是递归定义的因此后序基本操作中基本都是按照该概念实现的。
2. 二叉树的遍历
2.1 前/中/后序遍历 学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(先序遍历)根 左子树 右子树。中序遍历左子树 根 右子树。后序遍历左子树 右子树 根。
typedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;//前序遍历
void PreOrder(BTNode* root)
{//树为空if (root NULL){printf(N );return;}//树不为空按照 根 左子树 右子树 的顺序递归打印printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}//中序遍历
void InOrder(BTNode* root)
{//树为空if (root NULL){printf(N );return;}//树不为空按照 左子树 根 右子树 的顺序递归打印InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}//后序遍历
void PostOrder(BTNode* root)
{//树为空if (root NULL){printf(N );return;}//树不为空按照 左子树 右子树 根 的顺序递归打印PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
} 前序遍历递归图解 2.2 层序遍历 自上而下自左至右逐层访问树的结点的过程就是层序遍历。 层序遍历的实现需要借助队列先进先出实现思想是上一层带下一层。 void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);//先入根节点if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-val);//带入下一层if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);QueueDestroy(q);
}
2.3 节点个数以及深度等
//求树的结点个数
static int size 0;//定义成全局变量每次调用前初始化为0
int TreeSize(BTNode* root)
{if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
} 但是这种写法会出现线程安全的风险可以改成给函数传size的指针或者依靠分治递归思想左子树返回的结点个数右子树返回的结点个数1通过后序遍历。
//求树的结点个数
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
//求树的深度
int TreeDepth(BTNode* root)
{if (root NULL)return 0;//左子树和右子树分别计算深度取最大的深度1(根节点)int leftDepth TreeDepth(root-left);int rightDepth TreeDepth(root-right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}
int TreeDepth(BTNode* root)
{if (root NULL)return 0;return TreeDepth(root-left) TreeDepth(root-right) ? TreeDepth(root-left) 1 : TreeDepth(root-right) 1;//这种写法看似与上面的写法相差不大但实际上这个写法的时间复杂度大打折扣//通过leftDepth和rightDepth会记录左右子树的深度return时不需要再次计算时间复杂度为O(N)//而这种写法每次使用TreeDepth(root-left)或TreeDepth(root-right)都需要重新计算一次//时间复杂度是一个等比数列和根节点的找次其实是第二层节点找2次是第三层找4次……//最后算到时间复杂度为O(2^N)
}
//求第k层的节点个数
//当前树的第k层节点个数左子树的第k-1层节点个数右子树的第k-1层节点个数
int TreeKLevel(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;//只有根节点if (k 1)return 1;//k1说明第k层在子树里return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}
//查找x所在的节点找到1个就返回
BTNode* TreeFind(BTNode* root, int x)
{if (root NULL)return NULL;if (root-val x)return root;//先在左子树找没找到再去右子树找//如果要找两次推荐用变量来接收BTNode* ret1 TreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 TreeFind(root-right, x);if (ret2)return ret2;return NULL;
}
3. 二叉树的销毁
void TreeDestroy(BTNode* root)
{if (root NULL)return;TreeDestroy(root-left);TreeDestroy(root-right);free(root);//root NULL;//这里置空对形参修改实参不改变//但是想要修改root就需要二级指针非常麻烦//因此可以调用完TreeDestroy函数后手动将root置为NULL
} 以上就是本文的全部内容这个地方非常难理解大家要注意看每段代码的注释部分后面需要勤加练习熟练掌握这些算法
