沈阳有资质做网站的公司,泉州网站建设网站制作,建筑设计工资一般多少,烟台网站建设专业臻动传媒目录
1.树概念及结构
1.1树的概念
1.2树的相关概念
1.3树的表示
2.二叉树概念及结构
2.1二叉树的概念
2.2特殊的二叉树
2.3二叉树的性质
2.4二叉树的存储结构
3.二叉树顺序结构--特殊的二叉树--堆及其实现
3.1堆的概念及结构
3.2堆的实现
3.2.1堆的结构
3.2.2堆…目录
1.树概念及结构
1.1树的概念
1.2树的相关概念
1.3树的表示
2.二叉树概念及结构
2.1二叉树的概念
2.2特殊的二叉树
2.3二叉树的性质
2.4二叉树的存储结构
3.二叉树顺序结构--特殊的二叉树--堆及其实现
3.1堆的概念及结构
3.2堆的实现
3.2.1堆的结构
3.2.2堆的创建
3.2.2.1向上调整算法
3.2.2.2向下调整算法 3.2.2.2.1向下建堆的时间复杂度 3.2.3堆的插入 3.2.4堆的删除 3.2.5堆实现的参考代码 3.2.6堆的应用
3.2.6.1堆排序
3.2.6.2 TOP-K问题
4.二叉树链式结构及实现
4.1链式二叉树的结构
4.2前置说明
4.3二叉树的遍历
4.3.1前序、中序以及后序遍历
4.3.2层序遍历
4.4二叉树的节点个数以及高度等功能
4. 4.1二叉树节点个数
4.4.2二叉树叶子节点个数
4.4.3二叉树第K层节点个数
4.4.4 二叉树查找值为x的节点
4.4.5 二叉树的高度
4.5二叉树的构建、销毁及判断是否是完全二叉树
4.5.1通过前序遍历数组构建二叉树
4.5.2二叉树的销毁
4.5.3判断二叉树是否为完全二叉树
4.6参考代码 1.树概念及结构
1.1树的概念 树不同于之前的线性表树是一种非线性的数据结构由n(n0)个有限节点组成一个具有层次关系的集合。有一个特殊的节点称为根节点根节点没有前驱节点。除了根节点外其余节点被分成MM0个互不相交的集合其中每个集合又是一颗结构与树类似的子树。没一棵子树的根节点有且只有一个前驱结点但是可以有0个或多个后继节点因此树是递归定义的。 注子树之间不能有交集。
1.2树的相关概念 (1) 结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为6.
(2)叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I、P...等结点为叶结点。 (3)非终端结点或分支结点度不为 0 的结点 如上图 D 、 E 、 F 、 G...等结点为分支结点。 (4)双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点。 (5)孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 (6)兄弟结点 具有相同父结点的结点互称为兄弟结点 如上图 B 、 C 是兄弟结点 (7)树的度一棵树中最大的结点的度称为树的度 如上图树的度为6 (8)结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 (9)树的高度或深度树中结点的最大层次 如上图树的高度为4 (10)堂兄弟结点双亲在同一层的结点互为堂兄弟如上图 H 、 I 互为兄弟结点 (11)结点的祖先从根到该结点所经分支上的所有结点如上图 A 是所有结点的祖先 (12)子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是 A 的子孙 (13)森林由 m m0 棵互不相交的树的集合称为森林 上列概念需要熟记:(1)(2)(4)(5)(7)(8)(9). 1.3树的表示 树的节点结构既要存储值也要保存节点和节点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
}; 2.二叉树概念及结构
2.1二叉树的概念 一棵二叉树是节点的一个有限集合该集合1可能为空2由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 二叉树的特点1二叉树不存在度大于2的节点2二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。 注对于任意的二叉树都是由以下几种情况复合而成的 2.2特殊的二叉树 (1). 满二叉树 一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K 且结点总数是则它就是满二叉树。 (2). 完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为 K的有n 个结点的二叉树当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.3二叉树的性质 (1). 若规定根结点的层数为 1 则一棵非空二叉树的 第 i 层上最多有个节点。 (2). 若规定根结点的层数为 1 则 深度为 h 的二叉树的最大结点数是 个节点。 (3). 对任何一棵二叉树 , 如果度为 0的 叶结点个数为 , 度为 2 的分支结点个数为 ,则有 1. /*
* 假设二叉树有N个结点
* 从总结点数角度考虑N n0 n1 n2 ①
*
* 从边的角度考虑N个结点的任意二叉树总共有N-1条边
* 因为二叉树中每个结点都有双亲根结点没有双亲每个节点向上与其双亲之间存在一条边
* 因此N个结点的二叉树总共有N-1条边
*
* 因为度为0的结点没有孩子故度为0的结点不产生边; 度为1的结点只有一个孩子故每个度为1的结
点* * 产生一条边; 度为2的结点有2个孩子故每个度为2的结点产生两条边所以总边数为
n12*n2
* 故从边的角度考虑N-1 n1 2*n2 ②
* 结合① 和 ②得n0 n1 n2 n1 2*n2 - 1
* 即n0 n2 1
*/ (4)若规定根节点的层数为1具有n个节点的满二叉树的深度为。 (5)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有 (a). 若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号无双亲结点 (b). 若 2i1n 左孩子序号 2i1 2i1n 否则无左孩子 (c).若 2i2n 右孩子序号 2i2 2i2n 否则无右孩子 2.4二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 1.顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2.链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们一般都是二叉链。 typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* parent; // 指向当前结点的父亲节点struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
} 3.二叉树顺序结构--特殊的二叉树--堆及其实现 3.1堆的概念及结构 堆分为小堆和大堆小堆的概念就是把一个集合的所以元素按完全二叉树的顺序存储方式存储在一个一维数组中满足任意一个节点的子节点的值都大于该节点的值。大堆则相反。 堆的性质1堆中某个节点的值总是不大于或者不小于其父亲节点。2堆总是一棵完全二叉树。 3.2堆的实现
3.2.1堆的结构 用数组实现堆
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}HP;
3.2.2堆的创建
3.2.2.1向上调整算法 给出一个数组逻辑上可以看作一棵完全二叉树但是还不是一个堆通过向上调整算法把这个堆调整成一个小堆。 向上调整算法依次插入一个元素在最后然后和它的父节点比较如果小于父节点则交换元素再和父节点的父节点比较。终止条件1大于父节点。2调整到根节点。 int arr[] { 9,2,3,1,8,7,0,4,5,6 };
#include stdio.hvoid Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(int* a, int child) //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 test()
{int arr[] { 9,2,3,1,8,7,0,4,5,6 };int sz sizeof(arr) / sizeof(arr[0]);for (int i 0; i sz; i){AdjustUp(arr, i);}for (int i 0; i sz; i){printf(%d , arr[i]);}
}int main()
{test();return 0;
} 3.2.2.2向下调整算法 给出一个数组逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 根结点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子结点的子树开始调整一直调整到根结点的树就可以调整成堆。
int a[] {1,5,3,8,7,6}; 将上述数组调整为大堆 其中的第三步调整时左右子树都是大堆就和上述讲到的从根节点向下调整一样。
#include stdio.hvoid Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整的前提是左右子树是大堆
void AdjustDown(int* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小则将child指向右孩子反之不交换int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child])//child 1 n表示右孩子存在{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void test()
{//使用向下调整算法对数组进行建堆int a[] { 1,5,3,8,7,6 };//先找到最后一个非叶子节点即为最后一个节点的父亲节点int sz2 sizeof(a) / sizeof(a[0]);for (int i ((sz2 - 1) - 1) / 2; i 0; i--){AdjustDown(a, sz2, i);}for (int i 0; i sz2; i){printf(%d , a[i]);}}int main()
{test();return 0;
} 注向上调整算法和向下调整算法建小堆和建大堆思路上是一样的如果要交换把其中父亲节点和子节点比较的大小于符号交换即可。 3.2.2.2.1向下建堆的时间复杂度 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明( 时间复杂度本来看的就是近似值多几个结点不影响最终结果) 3.2.3堆的插入 堆的插入其实就是通过向上调整算法一个一个插入先插入到最后一个位置然后向上调整。
void HeapPush(HP* hp, HPDataType x)
{assert(hp);//判断是否需要扩容if (hp-_size hp-_capacity){int newcapacity hp-_a 0 ? 4 : hp-_capacity * 2;HPDataType* tmp (HPDataType*)realloc(hp-_a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(malloc fail!\n);exit(1);}hp-_a tmp;hp-_capacity newcapacity;}//先插入到最后一个位置然后在向上调整hp-_a[hp-_size] x;hp-_size;//向上调整AdjustUp(hp-_a, hp-_size - 1);
} 3.2.4堆的删除 删除堆是删除堆顶的数据将堆顶的数据和最后一个数据交换然后删除数组最后一个数据再将堆顶数据进行向下调整。
void HeapPop(HP* hp)
{assert(hp);assert(hp-_size 0);Swap((hp-_a[0]), (hp-_a[hp-_size - 1]));//交换堆顶和最后一个位置的数据hp-_size--;//向下调整AdjustDown(hp-_a, hp-_size, 0);
} 3.2.5堆实现的参考代码
//Heap.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}HP;
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//初始化
void HeapInit(HP* hp);
// 堆的销毁
void HeapDestory(HP* hp);
// 堆的插入
void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* hp, HPDataType x);
// 堆的删除
void AdjustDown(HPDataType* a, int n, int parent);
void HeapPop(HP* hp);
// 取堆顶的数据
HPDataType HeapTop(HP* hp);
// 堆的数据个数
int HeapSize(HP* hp);
// 堆的判空
int HeapEmpty(HP* hp);
//Heap.c#include Heap.hvoid Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//初始化
void HeapInit(HP* hp)
{assert(hp);hp-_a NULL;hp-_size 0;hp-_capacity 0;
}// 堆的销毁
void HeapDestory(HP* hp)
{assert(hp);free(hp-_a);hp-_a NULL;hp-_size hp-_capacity 0;
}// 向上调整算法
void AdjustUp(HPDataType* a, int child) //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 HeapPush(HP* hp, HPDataType x)
{assert(hp);//判断是否需要扩容if (hp-_size hp-_capacity){int newcapacity hp-_a 0 ? 4 : hp-_capacity * 2;HPDataType* tmp (HPDataType*)realloc(hp-_a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(malloc fail!\n);exit(1);}hp-_a tmp;hp-_capacity newcapacity;}//先插入到最后一个位置然后在向上调整hp-_a[hp-_size] x;hp-_size;//向上调整AdjustUp(hp-_a, hp-_size - 1);
}//向下调整的前提是左右子树是堆
void AdjustDown(HPDataType* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小则将child指向右孩子反之不交换int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child])//child 1 n表示右孩子存在{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 堆的删除--删除堆顶元素然后重新排列堆
void HeapPop(HP* hp)
{assert(hp);assert(hp-_size 0);Swap((hp-_a[0]), (hp-_a[hp-_size - 1]));hp-_size--;//向下调整AdjustDown(hp-_a, hp-_size, 0);
}// 取堆顶的数据
HPDataType HeapTop(HP* hp)
{assert(hp);assert(hp-_size 0); //堆不能为空return hp-_a[0];
}// 堆的数据个数
int HeapSize(HP* hp)
{assert(hp);return hp-_size;
}// 堆的判空
int HeapEmpty(HP* hp)
{assert(hp);if (hp-_size 0){return 1; //如果为空返回一个非0的数字}else{return 0;}
}
3.2.6堆的应用
3.2.6.1堆排序 堆排序就是利用堆排序的思想进行排序总共分为两个步骤 1建堆a排升序建大堆b排降序建小堆
2利用堆删除思想来进行排序例如排升序先将数组建成一个大堆然后将堆顶数据和最后一个位置的数据交换删除最后一个位置的数据然后向下调整再次调整为大堆这样被删除的那个元素就是最大的一个元素放在数组的最后一个位子然后再将倒数第二个数据和堆顶数据交换重复上述操作重复到不可交换为止既可以将数组排列为升序。 #include stdio.h//向下调整建大堆
#include stdio.hvoid Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整的前提是左右子树是大堆
void AdjustDown(int* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小则将child指向右孩子反之不交换int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child])//child 1 n表示右孩子存在{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void test()
{//使用向下调整算法对数组进行建成大堆int a[] { 20, 17, 4, 16, 5, 3 };//先找到最后一个非叶子节点即为最后一个节点的父亲节点int sz2 sizeof(a) / sizeof(a[0]);for (int i ((sz2 - 1) - 1) / 2; i 0; i--){AdjustDown(a, sz2, i);}for (int i 0; i sz2; i){printf(%d , a[i]);}printf(\n);//利用堆删除的思想排升序for (int i sz2 - 1; i 0; i--) //每次减少一个元素就相当于删除一个元素{Swap(a[0], a[i]);AdjustDown(a, i, 0);}for (int i 0; i sz2; i){printf(%d , a[i]);}printf(\n);
}int main()
{test();return 0;
}
3.2.6.2 TOP-K问题 TOP-K问题即求数据结合中前 K 个最大的元素或者最小的元素一般情况下数据量都比较大。对于TOP-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了可能数据都不能一下子全部加载到内存中。最佳的方式就是用堆来解决基本思路如下 1用数据集中前K个元素来建堆a前K个最大的元素建小堆。2前K个最小的元素建大堆。 2用剩余的N-K个元素依次和堆顶元素进行比较不满足则替换堆顶元素。以找前K个最大的元素为例用前K个元素建小堆然后用剩余的依次比较如果小于堆顶元素则不和堆顶元素交换如果大于堆顶元素则和堆顶元素交换然后再调整为小堆。 #include stdio.h//向下调整建大堆
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整的前提是左右子树是小堆
void AdjustDown(int* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小则将child指向右孩子反之不交换int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child])//child 1 n表示右孩子存在{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void PrintTopK(int* a, int n, int k)
{//1.建小堆--找a中前K大的元素for (int i ((k - 1) - 1) / 2; i 0; i--){AdjustDown(a, k, i);}//2.将剩下n-k个元素依次与堆顶元素进行比较大于堆顶元素则交换然后再次调整为小堆for (int i k; i n; i){if (a[i] a[0]){Swap(a[i], a[0]);AdjustDown(a, k, 0);}}//打印前K个元素for (int i 0; i k; i){printf(%d , a[i]);}
}
void test()
{int arr[] { 2,6,3,1,7,9,23,57,59,23,46,5,47,96,46,39,86,46 };int sz sizeof(arr) / sizeof(arr[0]);PrintTopK(arr, sz, 4);
}int main()
{test();return 0;
} 4.二叉树链式结构及实现
4.1链式二叉树的结构
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
4.2前置说明 此处手动快速创建一棵简单的二叉树快速进入二叉树操作后面再来研究二叉树真正的创建方式。
BTNode* BuyNode(BTDataType x)
{BTNode* ret (BTNode*)malloc(sizeof(BTNode));if (ret NULL){perror(malloc fail!\n);exit(1);}ret-_data x;ret-_left NULL;ret-_right NULL;return ret;
}BTNode* CreateBinaryTree()
{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;
} 创建的二叉树如下 注下列方法的实现都是通过这个例子来说明的 。
4.3二叉树的遍历
4.3.1前序、中序以及后序遍历 所谓二叉树的遍历是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作依次。访问节点所做的操作依赖于具体的应用问题。比如二叉树的销毁就会用到后序遍历。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历这三种遍历方式都属于深度优先遍历后面介绍的层序遍历属于一直广度优先遍历前序/中序/后序的区别是对节点的访问顺序不同
1前序遍历根 左子树 右子树
2中序遍历左子树 根 右子树
3后序遍历左子树 右子树 根 由于被访问的节点必是某子树的根所以N(Node),L(Left subtree),R(Right subtree)又可解释为根根的左子树根的右子树。NLP,LNP,LRN分别称为先根遍历中根遍历和后根遍历。下列是三种遍历方法的代码实现其实区别就是遍历的顺序不同下列的代码在遇到空节点的时候打印N。 注下列功能的实现都在BinaryTree.c文件中声明在BinaryTree.h中测试代码在test.c文件中。
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return ;}BinaryTreeInOrder(root-_left);printf(%d , root-_data);BinaryTreeInOrder(root-_right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return ;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%d , root-_data);
} 测试代码
#include BinaryTree //二叉树功能的实现声明在我自己创建的这个文件中这个文件还包含了功能实现所需 //的头文件
void test()
{//先手搓一个二叉树BTNode* node1 CreateBinaryTree();//进行遍历 BinaryTreePrevOrder(node1);printf(\n);BinaryTreeInOrder(node1);printf(\n);BinaryTreePostOrder(node1);printf(\n);}int main()
{test();return 0;
}
输出结果是 前序遍历结果 1 2 3 4 5 6 中序遍历结果 3 2 1 5 4 6 后序遍历结果 3 2 5 6 4 1 4.3.2层序遍历 设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第二层上的节点接着是第三层的节点以此类推从上至下从左至右逐层访问树的节点的过程就是层序遍历。 层序遍历的实现是通过之前学习的队列这个数据结构来实现的具体队列的实现可以看C语言实现队列 。这里我们直接用实现好的功能即可。 主要的步骤先把根节点放入队列里面访问队头元素此时为根节点之后取出然后把根节点的左子节点和右子节点依次放入队列中然后再访问队头元素此时为根节点的左子节点之后取出把左子节点的左子节点和右子节点依次放入队列中然后再访问队头元素此时为根节点的右子节点之后取出把右子节点的左子节点和右子节点依次放入队列中依次类推直到队列为空结束层序遍历。
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{//用队列来实现层序遍历//从根节点开始存存入根节点时把左右子节点存入Queue q; //创建一个队列QueueInit(q); //对队列进行初始化if (root) //如果不为空树则把根节点放入队列{QueuePush(q, root);}while (!QueueEmpty(q)) //循环进行层序遍历{BTNode* tmp QueueFront(q);QueuePop(q);printf(%d , tmp-_data);if (tmp-_left){QueuePush(q, tmp-_left);}if (tmp-_right){QueuePush(q, tmp-_right);}}QueueDestroy(q);
} 测试代码
#include BinaryTree.hvoid test()
{//先手搓一个二叉树BTNode* node1 CreateBinaryTree();BinaryTreeLevelOrder(node1);
}int main()
{test();return 0;
} 4.4二叉树的节点个数以及高度等功能 接下来的几个功能都是通过递归的方法来实现的学好二叉树和的前提是要学好递归。
4. 4.1二叉树节点个数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root); 通过递归实现的方法最主要的是弄清楚返回值和递归终止条件以二叉树节点个数为例 情况1根节点为空返回0. 情况2左右子树为空返回1 情况3其他情况返回左子树节点个数右子树节点个数1。这个1代表加上这层递归栈帧中的根节点。
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{//情况1根节点为空返回0//情况2左右子树为空返回1//情况3其他情况返回左子树加右子树加1if (root NULL){return 0;}if (root-_left NULL root-_right NULL){return 1;}int leftTreeNode BinaryTreeSize(root-_left);int rightTreeNode BinaryTreeSize(root-_right);return leftTreeNode rightTreeNode 1;
} 测试代码
#include BinaryTree.hvoid test()
{//先手搓一个二叉树BTNode* node1 CreateBinaryTree();//二叉树节点个数int ret BinaryTreeSize(node1);printf(%d\n, ret);
}int main()
{test();return 0;
} 这里通过递归展开图来详细描述该方法的递归过程 上述图的代码就是该函数实现的代码。
4.4.2二叉树叶子节点个数
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) 情况1根节点为空返回0. 情况2叶子节点没有左右子树左子树和右子树为空返回1. 情况3其他情况返回的叶子节点个数 左子树叶子节点的个数 右子树叶子节点的个数。
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{//根节点为空返回0if (root NULL){return 0;}//叶子节点没有左右子树返回1if (root-_left NULL root-_right NULL){return 1;}//叶子节点的个数 左子树叶子节点的个数 右子树叶子节点的个数return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
} 4.4.3二叉树第K层节点个数 根节点可以设为第一层也可以设为第0层这里我们设为第一层求第K层的节点个数就是相对于第二层来说求第K-1层的节点个数相对于第三层来说就是求第K-2层节点个数依次类推到了第K层对于第K层来说就是求第一层的节点个数这是就返回一个这一个代表这个根节点。 情况1根节点为空返回0。 情况2根节点不为空且K1返回1。 情况3根节点不为空且K1返回左子树的第K-1层节点个数右子树的第K-1层节点个数。
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//求第K层的节点个数//第一层的第K层节点个数对于第二层来说就是第二层的k-1层节点个数就是第三层的k-2层节点个数//情况1如果根节点为空返回0//情况2如果根节点不为空且k 1, 返回1//情况3如果根节点不为空且k 1, 返回左子树的第k-1层节点个数右子树的第k-1层节点个数if (root NULL){return 0;}if (root k 1){return 1;}int leftTreeNode BinaryTreeLevelKSize(root-_left, k - 1);int rightTreeNode BinaryTreeLevelKSize(root-_right, k - 1);return leftTreeNode rightTreeNode;
} 测试代码
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include BinaryTree.hvoid test()
{//先手搓一个二叉树BTNode* node1 CreateBinaryTree();int ret BinaryTreeLevelKSize(node1, 2);printf(%d\n, ret);
}int main()
{test();return 0;
} 4.4.4 二叉树查找值为x的节点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) 这个函数与前面的不同是返回的是一个节点 所以每次递归都需要接收返回值通过返回值的判断看是否返回上一层。 情况1根节点为空返回NULL。 情况2根节点不为空但值不等于x返回NULL。 情况3根节点不为空值等于x返回该节点的指针。
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-_data x){return root;}BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1){return ret1;}BTNode* ret2 BinaryTreeFind(root-_right, x);if (ret2){return ret2;}return NULL;
} 测试代码
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include BinaryTree.hvoid test()
{//先手搓一个二叉树BTNode* node1 CreateBinaryTree();BTNode* ret BinaryTreeFind(node1, 3);printf(%d , ret-_data);}int main()
{test();return 0;
} 4.4.5 二叉树的高度
//二叉树的高度
int BinaryTreeHeight(BTNode* root) 情况1根节点为空0返回0. 情况2根节点不为空返回左右子树高度大的那个1.(这个1表示加上该层栈帧根节点的高度)。 如果不用临时遍历存储会有效率问题我写在了代码中。
//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{//情况1如果根节点为空返回0//情况2如果根节点不为空返回左右子树高度大的那个加1if (root NULL){return 0;}//这里不用临时变量存储会有效率问题//return BinaryTreeHeight(root-_left) BinaryTreeHeight(root-_right) ? // BinaryTreeHeight(root-_left) 1 : BinaryTreeHeight(root-_right) 1;//没有用变量存储的话比较调用一次高度高的在返回时又要向下递归重新求一次int LeftTreeHeight BinaryTreeHeight(root-_left);int RightTreeHeght BinaryTreeHeight(root-_right);return LeftTreeHeight RightTreeHeght ? LeftTreeHeight 1 : RightTreeHeght 1;
} 测试代码
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include BinaryTree.hvoid test()
{//先手搓一个二叉树BTNode* node1 CreateBinaryTree();int ret BinaryTreeHeight(node1);printf(%d\n, ret);
}int main()
{test();return 0;
} 4.5二叉树的构建、销毁及判断是否是完全二叉树
4.5.1通过前序遍历数组构建二叉树 这里先给出一个数组ABD##E#H##CF##G##通过遍历该数组构建二叉树用中序遍历打印出来用中序遍历打印时需要先把打印的格式换为输出字符的形式即把%d换为%c不然打印出来的是字符的ASCLL码值。这里先给出这个数组对应的二叉树形状 // 通过前序遍历的数组构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi n) //判断下边是否未超过元素个数未超过进行前序遍历其实可以不写这里是不会越界的{if (a[*pi] #) //如果为#返回NULL{(*pi);return NULL;}//不为#创建一个节点然后连接到二叉树中BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail!\n);exit(1);}root-_data a[(*pi)];root-_left BinaryTreeCreate(a, n, pi);root-_right BinaryTreeCreate(a, n, pi);;return root;}else{perror(越界访问!\n);return NULL;}
} 这里的参数a是待遍历的数组n为数组中元素的个数pi是数组下标的指针。因为在函数中要改变下标i所以这里传指针pi。 测试代码
#include BinaryTree.hint main()
{BTDataType arr[] ABD##E#H##CF##G##;int sz sizeof(arr) / sizeof(arr[0]);int i 0;BTNode* ret BinaryTreeCreate(arr, sz, i);BinaryTreeInOrder(ret);return 0;
} 4.5.2二叉树的销毁 二叉树的销毁使用的是后序遍历因为如果使用前序遍历先销毁了根节点就找不到它的左右子树了所以使用后序遍历先销毁左右子树最后销毁根节点。 情况1根为空不需要销毁直接返回。 情况2根不为空递归左右子树如果都返回则销毁该节点。
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{//三个部分的销毁根 左子树 右子树//用后序左子树 右子树 根if (root NULL){return;}BinaryTreeDestory(root-_left);BinaryTreeDestory(root-_right);free(root);
}
4.5.3判断二叉树是否为完全二叉树 判断二叉树是否为完全二叉树还是用的层序遍历的思想遍历一个节点从队列中取出来把它的子节点放入队列如果子节点为空则把NULL指针放入队列当取出的数据是第一个NULL指针是判断队列中是否还有非空的指针如果有则不为完全二叉树如果没有则为完全二叉树。
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* tmp QueueFront(q);QueuePop(q);if (tmp NULL) //tmp是已经出队列的节点{//判断剩余元素中是否有非空元素//如果有则不为完全二叉树返回false//遍历队列元素QNode* cur q.phead; //此时的队头元素就是tmp的下一个元素while (cur ! q.ptail) {if (q.phead-val ! NULL){return false;}cur cur-next;}return true; //遍历完队列都没有非空指针则为完全二叉树}if (tmp-_left){QueuePush(q, tmp-_left);}else{QueuePush(q, NULL);}if (tmp-_right){QueuePush(q, tmp-_right);}else{QueuePush(q, NULL);}}QueueDestroy(q);
} 测试用例和代码 int main()
{BTNode* node1 CreateBinaryTree();bool ret BinaryTreeComplete(node1);if (ret true){printf(完全二叉树!\n);}else{printf(非完全二叉树!\n);}return 0;
} 这个测试用例的代码也一样只是把创建二叉树函数中节点的连接改一下就行了。 4.6参考代码
//BinaryTree.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;//手动创建二叉树
BTNode* BuyNode(BTDataType x);
BTNode* CreateBinaryTree();// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
int TreeSize(BTNode* root);
BTDataType* preorderTraversal(BTNode* root, BTDataType* returnSize);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//二叉树的高度
int BinaryTreeHeight(BTNode* root);//BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS
#include BinaryTree.h
#include Queue.hBTNode* BuyNode(BTDataType x)
{BTNode* ret (BTNode*)malloc(sizeof(BTNode));if (ret NULL){perror(malloc fail!\n);exit(1);}ret-_data x;ret-_left NULL;ret-_right NULL;return ret;
}BTNode* CreateBinaryTree()
{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;
}
// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi n){if (a[*pi] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail!\n);exit(1);}root-_data a[(*pi)];root-_left BinaryTreeCreate(a, n, pi);root-_right BinaryTreeCreate(a, n, pi);;return root;}else{perror(越界访问!\n);return NULL;}}// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{//三个部分的销毁根 左子树 右子树//用后序左子树 右子树 根if (root NULL){return;}BinaryTreeDestory(root-_left);BinaryTreeDestory(root-_right);free(root);
}// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{//等于左子树节点个数加上右子树节点个数加上1//情况1根节点为空返回0//情况2根节点不为空返回左子树节点个数加上右子树节点个数1//方法1//return root NULL ? 0 :// BinaryTreeSize(root-_left) BinaryTreeSize(root-_right) 1;//方法2//情况1根节点为空返回0//情况2左右子树为空返回1//情况3其他情况返回左子树加右子树加1if (root NULL){return 0;}if (root-_left NULL root-_right NULL){return 1;}int leftTreeNode BinaryTreeSize(root-_left);int rightTreeNode BinaryTreeSize(root-_right);return leftTreeNode rightTreeNode 1;
}// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}//叶子节点没有左右子树if (root-_left NULL root-_right NULL){return 1;}//叶子节点的个数 左子树叶子节点的个数 右子树叶子节点的个数//int leftTreeNode BinaryTreeLeafSize(root-_left);//int rightTreeNode BinaryTreeLeafSize(root-_right);//return leftTreeNode rightTreeNode;return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
}// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//求第K层的节点个数//第一层的第K层节点个数对于第二层来说就是第二层的k-1层节点个数就是第三层的k-2层节点个数//情况1如果根节点为空返回0//情况2如果根节点不为空且k 1, 返回1//情况3如果根节点不为空且k 1, 返回左子树的第k-1层节点个数右子树的第k-1层节点个数if (root NULL){return 0;}if (root k 1){return 1;}int leftTreeNode BinaryTreeLevelKSize(root-_left, k - 1);int rightTreeNode BinaryTreeLevelKSize(root-_right, k - 1);return leftTreeNode rightTreeNode;
}// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-_data x){return root;}BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1){return ret1;}BTNode* ret2 BinaryTreeFind(root-_right, x);if (ret2){return ret2;}return NULL;
}// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}//前序遍历把返回的值存入一个数组中
int TreeSize(BTNode* root) //返回节点的个数
{return root NULL ? 0 : TreeSize(root-_left) TreeSize(root-_right) 1;
}void preOrder(BTNode* root, BTDataType* a, int* pi)
{if (root NULL){return;}a[(*pi)] root-_data;preOrder(root-_left, a, pi);preOrder(root-_right, a, pi);}BTDataType* preorderTraversal(BTNode* root, BTDataType* returnSize)
{//如果返回一个数组必须要告诉返回数组的大小,returnSize表示返回数组的大小*returnSize TreeSize(root);BTDataType* a (BTDataType*)malloc(sizeof(BTDataType) * (*returnSize));int i 0;preOrder(root, a, i);return a;
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return ;}BinaryTreeInOrder(root-_left);printf(%c , root-_data);BinaryTreeInOrder(root-_right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return ;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%d , root-_data);
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{//用队列来实现层序遍历//从根节点开始存存入根节点时把左右子节点存入Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* tmp QueueFront(q);QueuePop(q);printf(%d , tmp-_data);if (tmp-_left){QueuePush(q, tmp-_left);}if (tmp-_right){QueuePush(q, tmp-_right);}}QueueDestroy(q);
}// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* tmp QueueFront(q);QueuePop(q);if (tmp NULL) //tmp是已经出队列的节点{//判断剩余元素中是否有非空元素//如果有则不为完全二叉树返回false//遍历队列元素QNode* cur q.phead;while (cur ! q.ptail) {if (q.phead-val ! NULL){return false;}cur cur-next;}return true;}if (tmp-_left){QueuePush(q, tmp-_left);}else{QueuePush(q, NULL);}if (tmp-_right){QueuePush(q, tmp-_right);}else{QueuePush(q, NULL);}}QueueDestroy(q);
}//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{//情况1如果根节点为空返回0//情况2如果根节点不为空返回左右子树高度大的那个加1if (root NULL){return 0;}//这里不用临时变量存储会有效率问题//return BinaryTreeHeight(root-_left) BinaryTreeHeight(root-_right) ? // BinaryTreeHeight(root-_left) 1 : BinaryTreeHeight(root-_right) 1;//没有用变量存储的话比较调用一次高度高的在返回时又要向下递归重新求一次int LeftTreeHeight BinaryTreeHeight(root-_left);int RightTreeHeght BinaryTreeHeight(root-_right);return LeftTreeHeight RightTreeHeght ? LeftTreeHeight 1 : RightTreeHeght 1;
}
