目录

树概念及结构

树的相关概念

树的表示 

二叉树的概念及结构  

堆

堆的实现 

 结构体建立

初始化 

 添加元素

 打印堆

 删除堆首元素

 返回首元素

 判断是否为空

空间销毁 

刷题找工作的好网站——牛客网

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

​​​​​​​

 

树概念及结构

 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根节点没有前驱结点
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有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的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

树的表示 

1.指针数组表示

数组内存的时子节点的地址

 2.二级指针表示

 3.最常用的表示方法——孩子兄弟表示法

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};

 树在实际中的应用

二叉树的概念及结构  

 一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

 1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树每层的节点数是2^(k-1)，满二叉树节点总个数2^k-1,完全二叉树节点个数范围：[2^k-1,2^k-1],完全二叉树最后一层的个数由1到满

注意：对于任意的二叉树都是由以下几种情况复合而成的：

 特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

堆

 动态开辟的空间在堆上，这个堆是进程地址空间内存区域划分

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；

• 堆总是一棵完全二叉树。

• 若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

  

• 不管奇数偶数parent都可以这样计算

   TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

• 比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
  对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
  数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
  1. 用数据集合中前K个元素来建堆
  前k个最大的元素，则建小堆
  前k个最小的元素，则建大堆
  2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元

堆的实现 

 结构体建立

typedef int HPDataTypedef;
typedef struct Heap
{
	HPDataTypedef* a;
	int size;//最后元素的下一个位置
	int capacity;//统计容量
}HP;

初始化 

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

 添加元素

void Swap(HPDataTypedef* a, HPDataTypedef* b)
{
	HPDataTypedef tmp = *a;
	*a = *b;
	*b = tmp;
}

//根据大根堆或小根堆进行调整，这里以小根堆为例
void AdjusuUp(HPDataTypedef* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0) //如果子节点=0，此时已经调整完成了，因此条件是>0
	{
		if (a[child]< a[parent])
		{
			Swap(&a[child], &a[parent]); //如果父节点capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataTypedef* tmp = (HPDataTypedef*)realloc(php->a,sizeof(HPDataTypedef) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail:");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjusuUp(php->a, php->size - 1);
}

 打印堆

void HeapPrint(HP* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i size; i++)
	{
		printf("%d ", php->a[i]);
	}
}

 删除堆首元素

向下调整的前提：左子树和右子树必须同时是大堆或小堆 

void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent)
{
	HPDataTypedef minChild = parent * 2 + 1;
	while (minChild<n)
	{
		if (minChild+1<n&&a[minChild+1]  a[parent])
		{
			Swap(&a[parent], &a[minChild]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapPop(HP* php)
{
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
//删除之后要让堆保持大根堆或小根堆存储的形式，这里以小根堆为例 
	AdjusuDown(php->a,php->size, 0);
}

HPDataTypedef Pop(HP* php)
{
	assert(php);
	assert(!HeapEmpt(php));
	return php->a[0];
}

bool HeapEmpt(HP* php)
{
	assert(php);
	
	return php->size == 0;
} //如果size==0就是空

void Destory(HP* php)
{
	free(php->a); //释放掉开辟的空间
	php->capacity = php->size = 0; //让容量和个数都为0
	php->a = NULL;
}