前言
在前面的顺序表、链表、都是线性表。今天的所介绍的二叉树是一种非线性数据结构。
树的概念以及介绍
定义
树是一种非线性的数据结构,它由n(n>0)个有限结点组成一个具有层次关系的集合。
树的相关概念(类比人类血缘关系)
结点的度:一个结点含有的子树的个数称为该结点的度。
叶结点或终端结点:度为0的结点称为叶结点。
非终端结点或分支结点:度不为0的结点。
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点。
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点。
兄弟结点:具有相同父结点的结点互称为兄弟结点。
树的度:一棵树中,最大的结点的度称为树的度。
结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推。
树的高度或深度:树中结点的最大层次。
堂兄弟结点:双亲在同一层的结点互为堂兄弟。
结点的祖先:从根到该结点所经分支上的所有结点。
子孙:以某结点为根的子树中任一结点都称为该结点的子孙。
森林:由m(m>0)棵互不相交的树的集合称为森林
二叉树的概念
二叉树是树的一种特殊形式,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。
满二叉树
满二叉树的定义
1.满二叉树是一种特殊的二叉树,它的特点是每一层的节点数都达到最大值,即每一层的节点数都恰好为2的幂次(除了最后一层以外)。
2.如果满二叉树的深度为k,那么它的节点总数为2^k - 1。在满二叉树中,除了最后一层的节点之外,其余每一层的节点都是完全填满的,而且最后一层的节点也是从左到右连续排列的
满二叉树性质
- 满二叉树的深度为k,节点总数为2^k - 1。
- 满二叉树的每一层的节点数都达到最大值,即每一层的节点数为2^(i-1),其中i是层数。
- 满二叉树的叶子节点全部位于最后一层。
- 满二叉树的节点要么是叶子节点(度为0),要么是度为2的节点,不存在度为1的节点
如下图:
完全二叉树
完全二叉树的定义
- 除了最后一层外,其他每一层的节点数都达到最大数量,即该层的节点数等于2的幂减去1。
- 最后一层的节点都集中在最左边,并且右边的节点可以少,但不能有空位。
完全二叉树的性质
1.完全二叉树的节点编号从1开始,对于编号为i的节点,其左子节点的编号为2i,右子节点的编号为2i+1。
2.如果一棵完全二叉树有n个节点,那么它的深度大约为log2(n)+1。
3.完全二叉树的特点是叶子节点只能出现在最下层和次下层,且最下层的叶子节点集中在树的左部。
二叉树的顺序实现
堆
堆的定义
堆是一种特殊的完全二叉树,它可以被视为一种特殊的顺序表。
堆的分类
堆的特点是父节点的值总是大于或小于其子节点的值,根据这个特点,堆可以分为大根堆和小根堆。在大根堆中,根节点的值是最大的,而在小根堆中,根节点的值是最小的。
二叉树的实现(本质:顺序表,形式:大根堆)
二叉树的功能
//初始化
void HeapInit(Heap* hp);
//扩容
void CheckCapacity(Heap* hp);
//插入数据
void HeapPush(Heap* hp, HPDataType x);
//删除数据
void HeapPop(Heap* hp);
//顶数据
HPDataType HeapTop(Heap* hp);
//大小
int HeapSize(Heap* hp);
//堆是否为空
bool HeapEmpty(Heap* hp);
//销毁
void HeapDestory(Heap* hp);
二叉树的定义以及初始化
定义
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
初始化
本质就是顺序表,没有太大的变化,开辟初始空间。
//初始化
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
if (hp->a == NULL)
{
perror("malloc fail");
return NULL;
}
hp->capacity = 4;
hp->size = 0;
}
二叉树空间扩容
//扩容
void CheckCapacity(Heap* hp)
{
assert(hp);
if (hp->size == hp->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
if(tmp == NULL)
{
perror("malloc fail");
return NULL;
}
hp->a = tmp;
hp->capacity *= 2;
}
}
二叉树的插入数据
数据从尾部插入,但是要保证大堆结构,我们调用函数 AdjustUp(向上调整)。
插入
//插入数据
void HeapPush(Heap* hp,HPDataType x)
{
assert(hp);
CheckCapacity(hp);
hp->a[hp->size++] = x;
AdjustUp(hp,hp->size-1);
}
AdjustUp(向上调整)
在这里,由于孩子结点和父亲结点的关系是:父亲 = (孩子-1)/ 2. (顺序表本质就是数组,首元素下标就是0)
如图:结点为4 父亲节点为 (4-1)/ 2 = 1。
如果发现,孩子节点大于父亲节点,进行交换。
//向上调整
void AdjustUp(Heap* hp, int child)
{
assert(hp);
int parent = (child - 1) / 2;
while (child >= 0)
{
if (hp->a[child] > hp->a[parent])
{
Swap(&(hp->a[child]), &(hp->a[parent]));
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
Swap(交换)
//交换
void Swap(HPDataType* child, HPDataType* parent)
{
HPDataType tmp = *child;
*child = *parent;
*parent = tmp;
}
二叉树数据的删除
在这展示的是首节点的删除,尾节点删除的意义不大
删除
删除操作是首节点,和尾节点进行互换,删除尾节点。
- 保证了删除效率
- 保证了堆的原始关系
由于尾结点互换到了头结点,需要进行AdjustDown(向下调整)
//删除数据
void HeapPop(Heap* hp)
{
assert(hp);
hp->a[0] = hp->a[hp->size - 1];
hp->size--;
AdjustDown(hp,hp->size);
}
AdjustDown(向下调整)
在这里,由于孩子结点和父亲结点的关系是:孩子 = 父亲*2 + 1.
如图:1. 孩子结点 5 = 2 * 2 +1
2. 孩子结点 6 = 2 * 2 + 1 +1
//向下调整
void AdjustDown(Heap* hp,int size)
{
assert(hp);
int parent = 0;
int child = parent * 2 + 1;
while (child < size)
{
if (hp->a[parent] < hp->a[child])
{
Swap(&hp->a[parent], &hp->a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
二叉树顶数据
//顶数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
return hp->a[0];
}
二叉树大小
//大小
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
二叉树是否为空
//堆是否为空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
二叉树销毁
//销毁
void HeapDestory(Heap* hp)
{
free(hp->a);
hp->a == NULL;
}
源码
Heap.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
//扩容
void CheckCapacity(Heap* hp);
//插入数据
void HeapPush(Heap* hp, HPDataType x);
//删除数据
void HeapPop(Heap* hp);
//顶数据
HPDataType HeapTop(Heap* hp);
//大小
int HeapSize(Heap* hp);
//堆是否为空
bool HeapEmpty(Heap* hp);
//销毁
void HeapDestory(Heap* hp);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"
//初始化
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
if (hp->a == NULL)
{
perror("malloc fail");
return NULL;
}
hp->capacity = 4;
hp->size = 0;
}
//扩容
void CheckCapacity(Heap* hp)
{
assert(hp);
if (hp->size == hp->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
if(tmp == NULL)
{
perror("malloc fail");
return NULL;
}
hp->a = tmp;
hp->capacity *= 2;
}
}
//交换
void Swap(HPDataType* child, HPDataType* parent)
{
HPDataType tmp = *child;
*child = *parent;
*parent = tmp;
}
//向上调整
void AdjustUp(Heap* hp, int child)
{
assert(hp);
int parent = (child - 1) / 2;
while (child >= 0)
{
if (hp->a[child] > hp->a[parent])
{
Swap(&(hp->a[child]), &(hp->a[parent]));
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//插入数据
void HeapPush(Heap* hp,HPDataType x)
{
assert(hp);
CheckCapacity(hp);
hp->a[hp->size++] = x;
AdjustUp(hp,hp->size-1);
}
//向下调整
void AdjustDown(Heap* hp,int size)
{
assert(hp);
int parent = 0;
int child = parent * 2 + 1;
while (child < size)
{
if (hp->a[parent] < hp->a[child])
{
Swap(&hp->a[parent], &hp->a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//删除数据
void HeapPop(Heap* hp)
{
assert(hp);
hp->a[0] = hp->a[hp->size - 1];
hp->size--;
AdjustDown(hp,hp->size);
}
//顶数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
return hp->a[0];
}
//大小
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
//堆是否为空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
//销毁
void HeapDestory(Heap* hp)
{
free(hp->a);
hp->a == NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"
void Heaptest()
{
Heap HP;
HeapInit(&HP);
HeapPush(&HP, 3);
HeapPush(&HP, 5);
HeapPush(&HP, 40);
HeapPush(&HP, 70);
HeapPush(&HP, 18);
HeapPush(&HP, 25);
while (!HeapEmpty(&HP))
{
printf("%d ", HeapTop(&HP));
HeapPop(&HP);
}
HeapDestory(&HP);
}
int main()
{
Heaptest();
return 0;
}