做网站 赚广告费,建站之星怎么收费,北京好的网页设计,昆山网站建设价格目录
引言
一、树的概念与结构
1.1 树的概念
1.2 树的相关概念
1.3 树的表示
1.4 树在实际中的运用
二、二叉树的概念与结构
2.1 二叉树的概念
2.2 特殊二叉树 满二叉树 完全二叉树
2.3 现实中的二叉树
2.4 二叉树的性质
2.5 二叉树的存储结构
顺序存储
链式…目录
引言
一、树的概念与结构
1.1 树的概念
1.2 树的相关概念
1.3 树的表示
1.4 树在实际中的运用
二、二叉树的概念与结构
2.1 二叉树的概念
2.2 特殊二叉树 满二叉树 完全二叉树
2.3 现实中的二叉树
2.4 二叉树的性质
2.5 二叉树的存储结构
顺序存储
链式存储
三、二叉树的顺序结构及实现
3.1 堆的概念与结构
3.2 堆的实现
3.2.1 定义
3.2.2 初始化
3.2.3 销毁
3.2.4 判断堆是否为空
3.2.5 获取堆顶元素
3.2.6 获取堆的元素个数
3.2.7 入堆
3.2.8 出堆删除堆顶元素
3.3 堆排序
3.4 堆排序的应用Top-K问题
四、二叉树的链式结构及实现
4.1 前序、中序、后序遍历
4.1.1 前序遍历
4.1.2 中序遍历
4.1.3 后序遍历
4.2 节点个数及高度
4.2.1 二叉树节点个数
4.2.2 二叉树叶节点个数
4.2.3 二叉树的高度
4.2.4 二叉树第k层节点个数
4.2.5 二叉树查找值为x的节点
4.3 层序遍历
4.4 二叉树的创建及销毁
4.4.1 二叉树的销毁
4.4.2 二叉树的创建 4.4.3 判断是否为完全二叉树
五、二叉树oj题 个人专栏《数据结构世界》 引言
数据结构世界暂时告别了线性大陆来到了树形的天堂首先迎来最经典的树——二叉树Binary Tree
数据结构世界中本只开辟了线性大陆在其中不断迭代进化线性的力量其余区域均为重重迷雾。但是这一天迷雾散开一角露出深不见底的树形深渊盘根杂枝树影迷蒙。首先二叉树入侵世界它们拥有着与线性截然不同的力量天生可以一心多用同时还有一种强大的神通——空间递归。一时间数据结构世界迎来了树形的恐惧人人谈“树”色变 一、树的概念与结构
1.1 树的概念 树是一种 非线性 的数据结构它是由 n n0 个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来 像一棵倒挂的树 也就是说它是根朝上而叶朝下的 。 有一个特殊的结点称为根结点根节点没有前驱结点 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 因此树是递归定义的。 注意树形结构中子树之间不能有交集否则就不是树形结构 有交集就变成图了更加复杂的数据结构后面会讲 每一个树都是由双亲节点和N个子树构成的所以可以递归定义 1.2 树的相关概念
概念树人类亲缘关系描述 这里高度有两种表示方法一种是直接看成1另一种是把第一层看成0这里推荐前者。 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I...等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G...等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 并查集中会用到森林 学好这些概念后续才能进一步学习其他更复杂的树。比如 AVL树 红黑树 B树系列B树B树B*树 1.3 树的表示 树结构 相对线性表就比较复杂了要存储表示起来就比较麻烦了 既然保存值域也要保存结点和结点之间的关系 实际中树有很 多种表示方式 如 如果明确了树的度那么可以直接定义顺序表存储孩子双亲表示法 当我们定义树节点的结构体时如果知道树的度可以直接定义指针的个数但如果不知道呢 有一种方法那就是用顺序表来存储孩子节点的地址也就是指针数组 也可以用顺序表来存储孩子节点的下标如下图 除此之外还有人想出来一些奇特的定义方法。比如双亲表示法树节点中只存储双亲结点的地址因为每个节点只有一个双亲结点所以也可以从下往上找。还有一种方法树节点中既存储双亲结点也存储孩子节点…… 当然最后我们还是详细了解一种最常用的王者表示法——左孩子右兄弟表示法 相当于一个负责宽度同层找兄弟一个负责深度同分支找孩子 这样我们就可以表示整个树的结构 1.4 树在实际中的运用
其实我们常用的Windows文件系统就是一个森林。同级目录下的文件互为兄弟上下级目录则为父子。还有后面准备学的Linux文件系统就是一棵目录树。 二、二叉树的概念与结构 那么对树有了基本的概念以后我们来看一下一种特殊的树——二叉树
2.1 二叉树的概念 一棵二叉树 是结点的一个有限集合该集合 : 或者为空 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出 二叉树不存在度大于2的结点 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 注意对于任意的二叉树都是由以下几种情况复合而成的 2.2 特殊二叉树 满二叉树
每一层都是满的节点个数为2^h - 1利用等比数列求和公式 完全二叉树
前h-1层都是满的最后一层可以不满但从左到右是连续的节点范围是 [ 2^(h-1) , 2^h - 1 ]前h-1层个数再加一就为2^(h-1) 要注意的是满二叉树是一种特殊的完全二叉树。
2.3 现实中的二叉树
程序员看到肯定要去膜拜一下多么标准的满二叉树啊 2.4 二叉树的性质
tips这里的性质不用强行记忆随着后面刷题和对二叉树认知加深慢慢就融会贯通了。
1. 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.
2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h - 1
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 m, 度为2的分支结点个数为 n,则有 mn1
4. 若规定根节点的层数为1具有n个结点的满二叉树的深度hlog(n1)以2为底
5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 1. 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 2. 若2i1n左孩子序号2i12i1n否则无左孩子 3. 若2i2n右孩子序号2i22i2n否则无右孩子 . 2.5 二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 父子间下标关系
1.父亲找孩子leftchild parent * 2 1 rightchild parent * 2 2
2.孩子找父亲parent (child - 1) / 2 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。
链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面课程学到高阶数据结构如红黑树等会用到三叉链。 三、二叉树的顺序结构及实现
3.1 堆的概念与结构 现实中我们通常把 堆(一种二叉树) 使用 顺序结构的数组来存储 注意 这里的堆和 操作系统虚拟进程地址空间中的堆 是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段 堆的性质
完全二叉树堆中某个节点的值总是不大于或者不小于其父节点的值 好好理解这句话堆的逻辑结构是二叉树物理结构是数组 3.2 堆的实现
3.2.1 定义 3.2.2 初始化 3.2.3 销毁
这里注意不要对整个堆进行空间释放因为堆这个结构体不是动态开辟的只能对堆里的数组进行空间释放。 3.2.4 判断堆是否为空 3.2.5 获取堆顶元素 3.2.6 获取堆的元素个数 3.2.7 入堆
前面几个都非常简单所以不多做介绍了详情请看往期--线性时代。现在来到了关键点——入堆。首先和往常一样先判断是否需要扩容再将入堆元素插入数组末尾。 做完这一切我们才真正来到入堆的精华。将数组想象成一棵二叉树那么刚刚插入的元素就在树的最底层。因为要保持任意一个元素都大于父节点假设这里是小堆所以我们就要根据父子间的下标关系进行调整这种算法称为向上调整算法。
具体做法
判断该节点孩子与其父节点的大小如果孩子小于父亲则交换。再让原本的孩子如今变成了父亲继续向上比较直到孩子大于等于父亲则跳出循环循环的条件是孩子节点的下标大于0注意这里不能写成父节点下标大于等于0因为父亲下标永远大于0。孩子为0后父亲也为0还是会进循环然后break所以逻辑不合理 AdjustUp(php-a, php-size-1);
所以push最后加上向上调整将数组和尾部元素下标传过去调整完保持还是一个堆。 3.2.8 出堆删除堆顶元素 入堆讲完了我们再来将另一个重点——出堆。大家觉得出堆应该从哪出队尾不那没有任何意义。出堆应该从堆顶出也就是二叉树的根节点。
但是如果直接向前挪动覆盖那父子关系就全乱了堆也就不存在了需要重新建堆代价太大了。所以如果我们要保持原有的堆的结构那要怎么删除呢
有一种做法可以达到目的那就是先把首尾元素交换再size--。这时就保持除了根节点其余两棵子树都是堆这时我们只要利用父子间下标关系进行调整即可这种算法称为向下调整算法 具体做法 先假设我们要比较的孩子是左孩子再进行判断比较左孩子和右孩子的大小如果右孩子更小则child下标再改为右孩子如果左孩子小则保持不变然后再用当前的节点父节点与更小的孩子进行比较如果孩子比父亲更小则父子交换再让原本的父亲如今的孩子继续向下进行比较调整直到孩子大于等于父亲则跳出循环注意循环的条件是孩子下标小于数组长度同时因为左孩子存在时右孩子不一定存在所以1中的条件判断还要补上child1n保证右孩子在数组时才进行比较 堆的测试及运行结果 这样我们先将数组元素入堆再不断获取堆顶元素再删除就可以实现升序打印小堆实现
源代码
heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#includetime.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HPInit(HP* php);
//销毁
void HPDestroy(HP* php);
//入堆
void HPPush(HP* php, HPDataType x);
//删除堆顶元素
void HPPop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
//获取堆顶元素
HPDataType HPTop(HP* php);
//获取堆的元素个数
int HPSize(HP* php);void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeheap.hvoid HPInit(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent])//小堆{Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);if (php-capacity php-size){int newCapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;AdjustUp(php-a, php-size-1);
}void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}HPDataType HPTop(HP* php)
{assert(php);return php-a[0];
}int HPSize(HP* php)
{assert(php);return php-size;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeheap.hvoid TestHeap1()
{HP hp;HPInit(hp);int arr[] { 4,3,2,50,65,44,12,78,95,35 };int sz sizeof(arr) / sizeof(arr[0]);int i 0;for (i 0; i sz; i){HPPush(hp, arr[i]);}while (!HPEmpty(hp)){printf(%d\n, HPTop(hp));HPPop(hp);}HPDestroy(hp);
}int main()
{TestHeap2();return 0;
} 3.3 堆排序
沿用刚刚的思路那堆排序是不是就是这样呢请看下面代码 先将待排序数组元素全部入堆再不断取堆顶元素放入数组中。好像很有道理对吧
但是这样排序有很多缺点
需要先实现一个堆想想我们为了实现一个堆写了多少代码 空间复杂度高来回拷贝数据
所以有没有一种更简单的方法实现堆排序呢 有
具体做法
既然我们不想要实现一个堆那么我们可以直接操作原数组将其变成堆即可。将数组调整成堆我们用向上调整算法这里建小堆建好小堆后利用堆删除思路再首尾元素交换选出最小的放在末尾再将前n-1个元素进行向下调整算法选出次小的不断循环重复以上步骤则最后将所有的元素排序完毕 堆排序的大体思路是这样的但是其实堆的创建除了向上调整算法也可以用向下调整算法而且速度更快可以达到优化的效果。
但是这里用向下调整算法和堆删除时不同因为用向下调整算法的前提是左右子树都为堆。这里一般肯定都不符合因为要排序的数组肯定是杂乱无章的所以怎么办呢
实现思路
我们可以从下往上因为可以把叶节点看作是堆所以从倒数第二层最后一个节点的父亲开始用向下调整算法因此逐渐从下往上把一个个小子树排成堆最后直到根节点这样就可以一直满足左右子树都为堆 时间复杂度分析与对比
向上调整算法
简单的运用错位相减法化简即可 向下调整算法 所以我们就通过精确的计算来得到向下调整算法比向上调整算法更快时间复杂度更优——O(N)。因此以后我们在写堆排序时就只用写向下调整算法三个愿望一次满足
其实我们还可以发现创建好堆后第二部分排序用向下调整算法时时间复杂度与创建堆时向上调整算法相同为O(N*logN)
所以堆排序整体时间复杂度为O(NN*logN)忽略小量来说就是O(N*logN)
这样我们就实现了真正简单实用的堆排序。运行结果如下 值得注意的是
小堆排序——排序结果为降序 相反大堆排序——升序
代码如下
void HeapSort(int* a, int n)
{//降序--建小堆//for (int i 1; i n; i)//{// AdjustUp(a, i);//向上调整--建小堆//}for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);//向下调整--建小堆}int end n - 1;//尾部元素下标while (end 0){Swap(a[0], a[end]);//首尾交换,选出最小的AdjustDown(a, end, 0);//隔绝尾部元素向下调整选出次小的end--;}}void HeapSort(int* arr, int sz)
{HP hp;HPInit(hp);int i 0;for (i 0; i sz; i){HPPush(hp, arr[i]);}i 0;while (!HPEmpty(hp)){arr[i] HPTop(hp);HPPop(hp);}HPDestroy(hp);
}void TestHeap2()
{int arr[] { 4,3,2,50,65,44,12,78,95,35 };int sz sizeof(arr) / sizeof(arr[0]);HeapSort(arr, sz);
} 3.4 堆排序的应用Top-K问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于 Top-K 问题能想到的最简单直接的方式就是排序正常思路 把N个数据建成堆再pop K次 但是如果数据量非常大排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决改进思路如下 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
那让我们来实战一下先造出N个数据
配合使用srand和rand函数创造100w以内的随机数 使用文件操作的形式将数据写入到文件中 创造好数据后再来实现topk的筛选
首先打开文件并读取k个数据创建小堆 其次循环读取剩下的N-K个数据与堆顶元素进行比较如果大于它则覆盖入堆再进行向下调整算法最后打印堆中数据最大的前K个顺便释放动态开辟的堆空间 那这些数都是随机的怎么检验自己的程序对不对呢很简单只要手动更改让数值大于100w即可。 运行结果 代码如下
void CreateNData()
{int n 10000;srand((unsigned int)time(NULL));FILE* fin fopen(data.txt, w);if (fin NULL){perror(fopen fail);return;}int x 0;for (int i 0; i n; i){x rand() % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}void PrintTopk(int k)
{FILE* fout fopen(data.txt, r);if (fout NULL){perror(fopen fail);return;}int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}for (int i (k-1-1)/2; i 0; i--){AdjustDown(minheap, k, i);}int val 0;while (fscanf(fout, %d, val) ! EOF){if (val minheap[0]){minheap[0] val;AdjustDown(minheap, k, 0);}}for (int j 0; j k; j){printf(%d\n, minheap[j]);}free(minheap);
}int main()
{CreateNData();PrintTopk(5);return 0;
} 四、二叉树的链式结构及实现
终于来到链式二叉树的部分也是真正有难度的精华部分。关于链式二叉树的学习我们不会像往期的数据结构一样讲解它的增删查改因为对于普通的链式二叉树并没有什么意义。只有到了后期的搜索二叉树以及更高阶的AVL树红黑树等等对它们增删查改才有意义。
所以现在学习的链式二叉树有两个目的
掌握前序中序后序和层序遍历为后期搜索二叉树的学习打基础与单链表相同大部分oj题也是以链式二叉树为考察对象的为后期刷题做准备 4.1 前序、中序、后序遍历 学习二叉树结构最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则依次对二 树中的节点进行相应的操作并且每个节点只操作一次 。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 从现在开始我们将任何一部分都看作根左子树右子树 前序先根遍历根 左子树 右子树 中序中根遍历左子树 根 右子树 后序后根遍历左子树 右子树 根 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 4.1.1 前序遍历 遍历时我们用递归实现
如果为空树则直接返回返回条件如果不为空时则先访问根节点再依次访问左子树和右子树子问题 运行结果 4.1.2 中序遍历
同理中序遍历只需把访问的顺序调换一下即可 这里我们可以手动算一算结果是多少有助于加深我们对遍历方式的认知。
运行结果 4.1.3 后序遍历
同理后序遍历只需把访问的顺序调换一下即可 运行结果 三条遍历的实现过程非常相似只有细微的差别但是背后的遍历方式与函数递归时栈帧的创建却需要我们多去画图思考与理解。 4.2 节点个数及高度
4.2.1 二叉树节点个数
方法一遍历计数
根据刚刚遍历的思想计算节点个数每次递归经过一个节点时size
但是思考一个问题如果我们要在函数内定义size那每次递归都会创建新的size变量不能满足想要的效果。有同学可能会说加上static修饰变成局部静态变量如下图。 看起来好像没问题再看看运行结果。 我们发现因为每次计算完节点个数size没有置为0导致后续计算错误。而且因为size是局部静态变量我们没有办法通过外部去修改所以这种方法不可行。
那应该怎么办呢其实很简单把size设置为全局变量即可。 这样我们就能外部将size置为0实现目的。 方法二分治
上述方法是不是显得有些繁琐每次都要将size置为0所以我们有第二种更简便的方法——分治。什么是分治呢简单来说就是运用管理思维分而治之。
假设一个场景校长要统计全校的人数那是不是就安排院长去统计而院长又安排辅导员去统计……依此类推最终全校人数经过一层层统计和汇总交付到校长手中。而不是校长挨个去统计全校师生的人数。这样的效率是不是就很高了 同理想象一下自下而上让每个节点统计自身下面的节点个数这样最后汇总到根节点时就完成了对节点个数的统计。 如果为空树返回0如果为非空节点返回左子树节点个数右子树节点个数1本身节点 这里熟练以后还可以用三木操作符化简一下。 运行结果 4.2.2 二叉树叶节点个数
那么如果我们要求叶节点的个数按照刚刚分治的思路只要稍微改动一下即可。
如果为空树返回0如果为叶节点返回1如果为分支节点返回左子树叶节点个数右子树叶节点个数 运行结果 4.2.3 二叉树的高度
求二叉树的高度同样运用分治的思维
如果为空树返回0如果为非空节点则计算出左右子树的高度再进行比较。返回更大的高度1 注意要定义变量存储当前递归计算的左右子树高度千万不要写成以下形式。看似没什么区别实际上递归的次数呈几何倍增加时间复杂度高效率极其低下。 运行结果 4.2.4 二叉树第k层节点个数
求二叉树第k层节点个数分析递归问题时我们都要弄清楚子问题和返回条件
子问题转化为求左子树和右子树的第k-1层节点个数之和返回条件1.如果为空树则返回0 2.如果不为空且k1则返回1 运行结果 4.2.5 二叉树查找值为x的节点
这里查找值为x的节点要返回的是节点的地址这样就可以进行修改。
同样我们先确定一下返回条件
如果为空树则返回NULL如果为要查找的值则返回root节点地址 但是这题分解子问题时有点复杂可能有人会写成这种形式 这样是不对的因为后续子问题没有返回值。所以应该怎么做呢
具体思路如下
先查找左子树如果左子树返回值不为空则返回其返回值再查找右子树如果右子树返回值不为空则返回其返回值这样如果左子树先找到了就不用查找右子树了注意由之前的题的警示我们在每次递归调用时都存储一下当前的值防止反复递归效率太低最后如果左右子树返回值都为空则返回NULL 4.3 层序遍历 层序遍历 除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1 层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第 2 层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 那层序遍历要怎么实现呢其实这里用队列实现非常方便。
利用队列先进先出的性质每一层的每个结点要出队列时则将左右孩子带进队列这样就达到层序遍历的效果。
具体做法
因为C语言没有对应的库所以我们将之前写好的队列源代码代码拷贝过来使用创建队列并初始化将根节点push入队当队列不为空时循环每次获取队头数据再pop出队打印树节点的数据从左到右的顺序如果孩子不为空则将孩子节点依次push入队最后销毁队列 注意这里队列嵌套了三层每个节点存储的数据是树的根节点的地址指针
结构体定义 函数定义 运行结果 4.4 二叉树的创建及销毁
4.4.1 二叉树的销毁
经过前面的磨练相信二叉树的销毁对于各位只是小意思了~
比较方便的方式是采用后序遍历先销毁左子树再销毁右子树最后销毁根节点。
如果采用其余遍历先销毁了根节点那还要保存其地址这样才能继续往下找。
返回条件如果已经走到空树那就不用销毁直接return即可 使用时要注意实现半自动在外部手动置空和free函数的逻辑一样 4.4.2 二叉树的创建
经过前面对递归的认识不断加深我们现在来研究正在创建二叉树的方法。
二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
我们通过一道题目来理解二叉树的创建。
描述
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。
输入描述
输入包括1行字符串长度不超过100。
输出描述
可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行 大体思路
先写出树节点的结构体定义和产生新节点的函数再用数组来存储输入的字符串将数组和下标i注意要传址传入创建二叉树的函数最后写出中序遍历的函数
这里重点讲讲创建二叉树的函数实现
以前序遍历的形式创建二叉树也是最常见的创建形式返回条件如果当前数组对应下标i的元素为#表示空则pi解引用再返回NULL如果不为#则创建新节点将数组对应元素放入同时pi解引用子问题创建完根节点后继续以先左后右的方式不断递归创建新节点最后返回root
代码如下图其实大家会发现好像也没有想象中那么难就是前序遍历的小小改版。因为大家对递归的掌握更加深刻了 完整代码如下
#include stdio.h
#include stdlib.htypedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-left NULL;newnode-right NULL;return newnode;
}BTNode* BTreeCreat(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root BuyNode(a[(*pi)]);root-left BTreeCreat(a, pi);root-right BTreeCreat(a, pi);return root;
}void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%c ,root-data);InOrder(root-right);
}int main()
{char a[100];scanf(%s,a);int i 0;BTNode* root BTreeCreat(a, i);InOrder(root);return 0;
} 4.4.3 判断是否为完全二叉树
判断一棵二叉树是否为完全二叉树先回忆一下完全二叉树的定义前n-1层都为满最后一层可以不满但从左到右必须连续。
思路根据这个特性我们可以采取层序遍历如果遇到空以后还有非空则不为完全二叉树如果遇到空后后面全是空则为连续为完全二叉树 具体方法
采用层序遍历则创建队列并初始化将根节点push入队队列非空则循环不断取队头元素并pop出队。判断取出的元素是否为空如果为空则break跳出循环如果不为空则继续把根节点的左右孩子push入队再进入另一层循环同样取队头元素。不过判断条件改为如果元素不为空则销毁队列return false 如果等到全部元素取完还没有return false则证明后面全为空为完全二叉树则销毁队列return true 运行结果 关于二叉树其实还没有完全讲完只是暂时告一段落。剩下的部分后续会在C中讲解因为用C做会方便不少。 源代码
queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;typedef BTNode* QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//检测队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#includequeue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;if (pq-ptail NULL){assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);return pq-phead-data;
}QDataType QueueBack(Queue* pq)
{assert(pq);return pq-ptail-data;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includequeue.hBTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-left NULL;newnode-right NULL;return newnode;
}BTNode* CreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}void PreOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}int size1 0;void BTreeSize1(BTNode* root)
{if (root NULL){return;}size1;BTreeSize1(root-left);BTreeSize1(root-right);
}//int BTreeSize(BTNode* root)
//{
// static int size 0;
// if (root NULL)
// {
// return size;
// }
// size;
//
// BTreeSize(root-left);
// BTreeSize(root-right);
// return size;
//}int BTreeSize(BTNode* root)
{return root NULL ? 0 : BTreeSize(root-left) BTreeSize(root-right) 1;//if (root NULL)//{// return 0;//}//return BTreeSize(root-left)// BTreeSize(root-right) 1;
}int BTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
}int BTreeHeight(BTNode* root)
{if (root NULL){return 0;}int leftHeight BTreeHeight(root-left);int rightHeight BTreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}int BTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL){return 0;}if (k 1){return 1;}return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
}BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftRoot BTreeFind(root-left, x);if (leftRoot){return leftRoot;}BTNode* rightRoot BTreeFind(root-right, x);if (rightRoot){return rightRoot;}return NULL;
}void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}QueueDestroy(q);
}void BTreeDestroy(BTNode* root)
{if (root NULL){return;}BTreeDestroy(root-left);BTreeDestroy(root-right);free(root);
}bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(q);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* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}int main()
{BTNode* root CreatBinaryTree();PreOrder(root);InOrder(root);PostOrder(root);printf(%d\n, BTreeSize(root));printf(%d\n, BTreeSize(root));printf(%d\n, BTreeSize(root));BTreeSize(root);printf(%d\n, size1);size1 0;BTreeSize(root);printf(%d\n, size1);size1 0;BTreeSize(root);printf(%d\n, size1);printf(%d\n, BTreeLeafSize(root));printf(%d\n, BTreeLeafSize(root));printf(%d\n, BTreeLeafSize(root));printf(%d\n, BTreeHeight(root));printf(%d\n, BTreeHeight(root));printf(%d\n, BTreeHeight(root));printf(%d\n, BTreeLevelKSize(root, 1));printf(%d\n, BTreeLevelKSize(root, 2));printf(%d\n, BTreeLevelKSize(root, 3));BTNode* pos BTreeFind(root, 3);LevelOrder(root);printf(%d\n, BTreeComplete(root));BTreeDestroy(root);root NULL;return 0;
}
五、二叉树oj题 仅仅了解二叉树的知识是不够的让我们来刷刷题吧
二叉树oj题集LeetCode-CSDN博客 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注 ❤️ 拜托拜托这个真的很重要你们的点赞就是博主更新最大的动力有问题可以评论或者私信呢秒回哦。
