树是一种非线性的数据结构,它是由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是兄弟节点 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
这个表示法是每次都找左边的第一个孩子,让孩子的兄弟指针去找其他的兄弟节点。
一棵二叉树是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出:
注意:对于任意的二叉树都是由以下几种情况复合而成的:
(1). 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点. (2). 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子. (3). 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子.
如果有一个关键码的集合K = { k0,k1 ,k2 ,…,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki <= K 2i+1且 Ki <= K 2i+2 (Ki >= K 2i+1 且 Ki >= K 2i+2 ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
例如小堆,在以10为父节点的子树中,它的孩子15和56都比它大;在以15为父节点的子树中,它的孩子25和30都比它大;另外,我们可以将堆的物理结构看作一个数组,实现堆的时候我们用数组模拟实现,但控制的其实是堆;
在用数组实现堆之前,我们应该知道两个性质:
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//向上调整---调大堆
void AdjustUP(HPDataType* a, int child);
//向下调整---调大堆
void AdjustDown(HPDataType* a, int len, int parent);
//向上/向下调整中交换
void Swap(HPDataType* p1, HPDataType* p2);
//初始化
void HeapInit(HP* php);
//入堆
void HeapPush(HP* php, HPDataType x);
//删除堆顶的数据
void HeapPop(HP* php);
//获取堆顶元素
HPDataType HeapTop(HP* php);
//获取数组模拟实现的堆的长度
int HeapSize(HP* php);
//判断空堆
bool HeapEmpty(HP* php);
//释放内存
void HeapDestory(HP* php);
堆向下调整算法:现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
堆向上调整算法:从一个节点开始往上开始调整,这个节点一般是叶子,如果调的是大堆,那么就是如果这个节点的父亲比它小,那么就将这两个节点交换;堆向上调整算法的前提是:开始调整的节点上面必须是一个大/小堆;
下面看代码的具体实现:
//初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
//判断空堆
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//向上/向下调整中交换
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
向上调整算法,它的最坏情况是向上调整高度次,一颗完全二叉树的高度是 logN ,所以它的时间复杂度是 O(logN);
//向上调整---调大堆
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;
}
}
}
向下调整算法,它的最坏情况也是向下调整高度次,一颗完全二叉树的高度是 logN ,所以它的时间复杂度也是 O(logN);
//向下调整---调大堆
void AdjustDown(HPDataType* a, int len, int parent)
{
//先定义孩子的节点是父节点的左边第一个
int child = parent * 2 + 1;
while (child < len)
{
//找出孩子节点中较大的那个
if (child + 1 < len && 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 HeapPush(HP* php, HPDataType x)
{
assert(php);
//扩容
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* newphp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
assert(newphp);
php->a = newphp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
//向上调整
AdjustUP(php->a, php->size - 1);
}
//删除堆顶的数据
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
//获取堆顶元素
HPDataType HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}
//获取数组模拟实现的堆的长度
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
//释放内存
void HeapDestory(HP* php)
{
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
void TestHeap()
{
HP hp;
HeapInit(&hp);
int a[] = { 65,100,70,32,50,60 };
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
HeapPush(&hp, a[i]);
}
while (!HeapEmpty(&hp))
{
int top = HeapTop(&hp);
printf("%d\n", top);
HeapPop(&hp);
}
HeapDestory(&hp);
}
测试结果如下:
堆排序的思路是,首先要建立一个堆,如果是排升序,就建大堆,因为大堆中,大的在前面,每次让堆顶的数据与堆尾的数据的值进行交换,交换完长度减一,相当于最大的放到后面就不动了,然后再从堆顶开始向下调整,次大的调到堆顶,然后和倒数第二的数据的值进行交换…直到长度减到0.
这里建堆推荐使用向下建堆,因为向下建堆的时间复杂度为 O(N) ,而向上建堆的时间复杂度为 O(N * logN) ;
//堆排
void HeapSort(int* a, int len)
{
//向上建堆---大堆(时间复杂度:O(N * logN))
/*for (int i = 1; i < len; i++)
{
AdjustUP(a, i);
}*/
//向下建堆---大堆(时间复杂度:O(N))
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, len, i);
}
//每次交换第一个与最后一个的数据,交换完数据长度 -1 ,从下标 0 开始向下调整
while (len)
{
Swap(&a[0], &a[len - 1]);
len--;
AdjustDown(a, len, 0);
}
}
其中实现的结果如下:
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
先生成数据,这里只生成 100000 以内的数据,方便后面进行检验;
void CreateNDate()
{
// 造数据,1000个
int n = 1000;
srand(time(0));
//创建文档
const char* file = "data.txt";
//以write的方式打开文档
FILE* fin = fopen(file, "w");
assert(fin);
//生成 100000 以内的随机数写入文档中
for (size_t i = 0; i < n; ++i)
{
int x = rand() % 100000;
fprintf(fin, "%d\n", x);
}
//关闭文档
fclose(fin);
}
寻找前 k 个最大的数据;
void PrintTopK(int k)
{
//创建文档,已存在就忽略
const char* file = "data.txt";
//以只读的方式打开
FILE* fout = fopen(file, "r");
assert(fout);
//开辟 k 个空间,即前 k 个数据的空间
int* kminheap = (int*)malloc(sizeof(int) * k);
assert(kminheap);
//从文档中读取前 k 个数据,放入kminheap数组中
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &kminheap[i]);
}
// 建小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(kminheap, k, i);
}
// 继续读取文档中 N - K 个数据
//如果读取到比堆顶大的数据,就直接覆盖堆顶的数据,然后向下调整
//直到读取文档中的数据失败,即读取完全部数据
int val = 0;
while (!feof(fout))
{
fscanf(fout, "%d", &val);
if (val > kminheap[0])
{
kminheap[0] = val;
AdjustDown(kminheap, k, 0);
}
}
//打印前 k 个
for (int i = 0; i < k; i++)
{
printf("%d ", kminheap[i]);
}
printf("\n");
}
这里上面只生成了 100000 以内的数据,所以我们手动改变文档中的值,随机将 5 个值的后面加上四个 4 ,即变成了最大的五个数,如下图,证明了我们的代码是正确的;