数据结构-二叉树·堆(顺序结构的实现)

简介: 数据结构-二叉树·堆(顺序结构的实现)



一.树的概念及结构

1.1树的概念

图一  图二

树是一种非线性的数据结构,它是由k个节点(k>=0)组成的具有层次关系的一个集合,如图一所示,把上图倒过来,如图二所示,看起来像一棵树,所以被叫作树;

类似于树的特点,把最上面的那个结点(A)叫作根结点

除了根结点,其余的结点又可以分为若干个类似于树的子树,如下图:

所以树是递归定义的;

相关概念:

 

1.结点的度:及该结点含有子树的个数(有几个孩子),如上图:1的度为3,2的度为1,4的度为2;

2.叶结点(终端结点):度为0的结点,如上图的3,5,6,7;

3.分枝结点(非终端结点):根结点与叶结点以外的结点,如2,4;

4.双亲结点(父结点):一个结点含有子结点,该结点称为子结点的父结点,如1是2,3,4的父结点,4是6,7的父结点;

5.孩子结点(子结点):如5是2的子结点,4是1的子结点;

6.兄弟结点:有相同父结点的结点称为兄弟结点,如6,7的父结点都是4,所以6,7是兄弟结点;

7.树的度一棵树中,最大的结点的度称为树的度,如上面的树的度是3(因为1的度最大,为3);

8.结点的层次:根为第一层,往下一次类推;

9.树的高度(深度)如上图,树的高度为3;

10.森林:有许多互不相交的树组成的集合;

11.度为0的结点个数为N0,度为2的节点个数为N2;则有N0=N2+1;

1.2树的表示

最常见的是孩子兄弟表示法

 

双亲表示法(一般使用结构体数组):只存储双亲的下标或指针;

例如:

上面这个树用双亲表示法表示:

蓝色存储的该结点的父结点的下标或指针;

没有父亲就存储-1(-1不是个有效的下标);

 

二.二叉树的概念及结构

2.1二叉树的概念

二叉树:

1.不存在度大于2的结点的树;最多两个,可以是1个或则0个;

度为0(空树);

2.二叉树的子树 有左右子树之分,次序不能颠倒,所以二叉树是有序的;

2.2两个特殊的二叉树

满二叉树:

一个二叉树,如果每一层的结点数都达到最大值,这个数就是满二叉树;

假设一个满二叉树有h层,则该二叉树的总的结点为2^h-1;

完全二叉树:

是一个深度为k的有n个节点的二叉树,对树中的节点按从上至下、从左到右的顺序进行编号,如果编号为i1≤i≤n的结点与满二叉树中编号为i的结点在二叉树中的位置相同;

 

三.二叉树顺序结构及实现

3.1二叉树顺序结构

根据完全二叉树的特点,可以得出这样的结论:

如果完全二叉树用数组存储,那么可以得到任意一个父结点,可以通过下标找到孩子,通过孩子下标也可以找到父结点的下标;

规律如下:

liftchild = perent*2+1;

rightchild = parent*2+2;

parent = (child-1)/2;

堆在存储的分类:大根堆,小根堆

 

3.2二叉树(堆)顺序结构的实现

这里重点分析向上/向下调整的函数

向上调整:

思想:将插入的数据尾插到数组里面,根据父结点与孩子结点下标的关系向上比较做调整,如果父亲结点的数据大于(小于)孩子结点,就交换:如图:

实现代码:

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//向上调整
void Adjustup(HPDataType* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if (a[parent] > a[child])
    {
      Swap(&a[parent], &a[child]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

向下调整:

思想:如果我们要删除堆顶(根)的结点,如果直接删除,然后向前覆盖,堆的顺序就会改变,不再是大堆(小堆),如图,这里就需要用到向下调整,先将最后一个数据与第一个数据交换,再将最后一个数据删除,这样保证了除了根,下面的结点都是大堆(小堆);

然后再用根和两个孩子中较小的一个交换,一次向下重复以上动作,图解如下:

实现代码:

//向下调整
void Adjustdown(HPDataType* a, int parent,int n)
{
  assert(a);
  int child = parent * 2 + 1;
  while (child<n)
  {
    //假设左孩子小
    if (child+1<n && a[child] > a[child + 1])   //假设错误,修正
    {
      child = child + 1;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[parent], &a[child]);
      parent = child;
      child = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

完整代码:Heap.h    Heap.c    

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include<string.h>
#define HPDataType int
typedef struct Heap
{
  //存储数据的数组
  HPDataType* a;
  int size;
  int capacity;
}Heap;
//初始化函数,两种
//先不开空间,使用的时候再开
void HeapInit(Heap* php);
//已经有一个数组的数据,先开空间,把一个数组的数据放到堆数组里面
void HeapInitArray(Heap* php,int* a,int n);
//摧毁函数,防止内存泄露
void HeapDestory(Heap* php);
//打印函数
void HeapPrintf(Heap* php);
//向上调整函数
void Adjustup(HPDataType* a, int child);
//向下调整函数
void Adjustdown(HPDataType* a, int child,int n);
//向堆里面插入数据的函数
void HeapPush(Heap* php, HPDataType x);
//把堆里面的根结点Pop出去的函数
void HeapPop(Heap* php);
//取出根结点数据的函数
HPDataType HeapTop(Heap* php);
//判断堆是否为空的函数
bool HeapEmpty(Heap* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void HeapInit(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = 0;
  php->size = 0;
}
void HeapInitArray(Heap* php,int* a,int n)
{
  assert(a);
  assert(php);
  php->a = (HPDataType*)malloc( n * sizeof(int));
  if (php->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  memcpy(php->a, a, n * sizeof(int));
  //向上调整建堆
  for (int i = 1; i < n; i++)
  {
    Adjustup(php->a, i);
  }
  php->size = n;
  php->capacity = n;
}
void HeapDestory(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = php->size = 0;
}
void HeapPrintf(Heap* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ",php->a[i]);
  }
  printf("\n");
}
//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//向上调整函数
void Adjustup(HPDataType* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if (a[parent] > a[child])
    {
      Swap(&a[parent], &a[child]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//向下调整函数
void Adjustdown(HPDataType* a, int parent,int n)
{
  assert(a);
  int child = parent * 2 + 1;
  while (child<n)
  {
    //假设左孩子小
    if (child+1<n && a[child] > a[child + 1])
    {
      child = child + 1;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[parent], &a[child]);
      parent = child;
      child = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//插入函数
void HeapPush(Heap* 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");
      exit(-1);
    }
    php->a=tmp;
    php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  Adjustup(php->a,php->size-1);
}
//删除堆顶结点
void HeapPop(Heap* php)
{
  assert(php);
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  Adjustdown(php->a, 0,php->size);
}
//取出堆顶数据的函数
HPDataType HeapTop(Heap* php)
{
  assert(php);
  return php->a[0];
}
//判空函数
bool HeapEmpty(Heap* php)
{
  assert(php);
  return php->size;
}
目录
相关文章
|
20天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
56 1
|
21天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
21天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
21天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
21天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
21天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
17 0
|
21天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
21天前
初步认识栈和队列
初步认识栈和队列
49 10
|
15天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1