数据结构第五课 -----二叉树的代码实现

简介: 数据结构第五课 -----二叉树的代码实现

小知识

完全二叉树的堆的创建时间复杂度

假设我们随意给出一个长度为n的数组,如果我们要建堆,最坏的情况就是全部节点都要向下调整

我们可以当完全二叉树是满二叉树进行计算

我们需要统计全部节点的移动次数,最终全部计算出 2^h -1 - h,因为是每个节点要往下移动一个高度次, 满二叉树是 的节点数 N = 2 ^h - 1 所以 h = log(N +1),代入 2^h -1 - h得出n - log(n+1) 大约就是n次 而每个节点的时间复杂度是大约是O(log(N))(每个节点向下调整高度次).这个就是向下调整的时间复杂度O(N)


向上调整的时间复杂度

二叉树的最后一层占据所有节点的一半

328cdb964cc177041e9be60357d82bbf_3b4382d5439e4f8a927c1489074162ad.png 最终化简就是T(n) = (n+1)*(log(n+1) - 1) +1 -n 大概就是O(N *log(N))


堆的实现

20c353507b5c2e6d15b7d681897f66b6_eec0d8dbd8494ade85982827409e5b4e.png

可以发现我们的要想实现二叉树就得借助顺序表来进行操作,因为二叉树是逻辑结构,我们要想实现就得利用物理结构,也就是堆 ,堆有大小堆的区分,下面我以小堆来实现


结构体

27639c184523729273f8a5e79ffee909_68e210114a6e4d5888bb375cd68749b9.png 这里是利用顺序表来存储,所以结构和顺序表是一样的,但是本质上还是二叉树

typedef int HDataType;
typedef struct Heap
{
  HDataType* tree;
  int size;
  int capacity;
}Heap;

插入

思路:我们先插入最后一个,然后向上调整,因为我们是小堆,要保证每个父亲<= 孩子

这里我们要注意不能越界,

//向上调整
void adjust(HDataType* tree, int Hsize)
{
  int child = Hsize - 1;
  int parent = (Hsize - 1 - 1) / 2;
  while (child > 0)
  {
    if (tree[child] < tree[parent])
    {
      HDataType b = tree[child];
      tree[child] = tree[parent];
      tree[parent] = b;
      child = parent;
      parent = (child - 1) / 2;
    }
    else
      return;
  }
}
// 插入
void Heappush(Heap* obj, HDataType elemest)
{
  //判断释放满
  if (obj->size == obj->capacity)
  {
    obj->capacity = (obj->capacity == 0 ? 4 : obj->capacity * 2);
    HDataType * tmp = realloc(obj->tree, sizeof(Heap) * obj->capacity);
    if (tmp == NULL)
    {
      perror("realloc");
      return;
    }
    obj->tree = tmp;
  }
  obj->tree[obj->size++] = elemest;
  //开始检查是否大于父节点
  adjust(obj->tree, obj->size);
  
}


我们主要就是考虑 根节点和自己的孩子这里,是有可能越界的

如图,可以利用child == 0来结束,


删除

这里的删除和前面我们学习过的顺序表和链表的删除不太一样,这里的删除是要删除二叉树的根节点,删除后又要构成一样的小堆

思路: 根节点和最后一个叶节点进行交换,然后删除叶节点(新的叶节点),交换后的根节点(新的根节点),然后让左右孩子进行比较大小,比较出最小值,然后再和根节点进行比较,如果根节点大于,就交换,然后依次循环直到符合小堆, 如果小于或者等于则不用调整,但是因为我们是把最后一个叶节点交换,交换的节点可能会大于等于,这种情况可以忽略,但是思路还是可以借鉴,

需要注意的是我们交换是循环进行的要找到结束条件

// 删除 (删除根节点)
void HeapPop(Heap* obj)
{
  assert(obj);
  assert(obj->size > 0);
  //两节点交换
  HDataType elemest = obj->tree[0];
  obj->tree[0] = obj->tree[obj->size - 1];
  obj->tree[obj->size - 1] = elemest;
  obj->size--;
  //向下调整
  int parent = 0;
  int  child = parent * 2 + 1;
  if (parent * 2 + 1 < obj->size && parent * 2 + 2 < obj->size &&  obj->tree[parent * 2 + 1] > obj->tree[parent * 2 + 2] )
  {
    child = parent * 2 + 2;
  }
  while (child < obj->size)
  {
    
    //判断孩子和父亲的大小
    if (obj->tree[parent] > obj->tree[child])
    {
      //两节点交换
      HDataType elemest = obj->tree[parent];
      obj->tree[parent] = obj->tree[child];
      obj->tree[child] = elemest;
      parent = child;
    }
    else
      break;
    child = parent * 2 + 1;
    if (parent * 2 + 1 < obj->size && parent * 2 + 2 < obj->size && obj->tree[parent * 2 + 1] > obj->tree[parent * 2 + 2])
    {
      child = parent * 2 + 2;
    }

  }
  

}

我们可以判断child是否大于等于size,,因为我们的思路就是要找到叶节点,我们只需child大于等于size就停止循环

根节点

// 根
HDataType  HeapTop(Heap* obj)
{
  assert(obj);
  assert(obj->size > 0);
  return obj->tree[0];
}

长度

// 长度
size_t HeapSize(Heap* obj)
{
  assert(obj);
  return obj->size;
}

是否为空

//是否为空
bool HeapEmpty(Heap* obj)
{
  assert(obj);
  return obj->size == 0;
}


TOP-K问题

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

在N个数中找出前K个大的数(N远大于K)


1.思路: 把N个数创建成大堆,然后pop K次

这种算法的时间复杂度是 N *log(N) + K *log(N),每个节点向下调整

最终大约是O(N *log(N))

这种算法还是有差异

如果N是100亿, k = 10, 一个整形4个字节

那么我们就需要400亿字节,也就大约40G内存,我们电脑内存最多就32G,这个方法行不通

2.思路:

1.读取N个数的K个,创建一个K个数的小堆,

2.然后依次把剩下的N-K个数进行和堆顶比较,如果大于堆顶就顶替堆顶,然后向下调整形成小堆,

注意的是我们是要大于堆顶的数顶替原来的堆顶,不是让小的顶替, 我们知识借鉴了小堆的思路,并不是完全是按照小堆的思路走

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void exchange(int *a, int *b)
{
  int e = *a;
  *a = *b;
  *b = e;
}
void PrintTop(int n)
{
  //创建一个n个数的小堆
  FILE* pf = fopen("./test.txt", "r");
  if (pf == NULL)
  {
    perror("fopen");
    return 1;
  }
  int* Heap = (int*)malloc(sizeof(int) * n);
  int i = 0;
  for (i = 0; i < n; i++)
  {
    int elemest;
    fscanf(pf, "%d", &elemest);
    Heap[i] = elemest;
    //向上调整
    int child = i;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
      if (Heap[child] < Heap[parent])
      {
        exchange(&Heap[child], &Heap[parent]);
      }
      else
        break;
      child = parent;
      parent = (child - 1) / 2;

    }

  }
  // 继续读取下面的数据
  int ch = 0;
  while ( fscanf(pf, "%d", &ch) != EOF)
  {
    if (ch <= Heap[0])
    {
      continue;
    }
    Heap[0] = ch;
    //向下调整
    int parent = 0;
    int child = parent * 2 + 1;
    while (child < n)
    {
      if (child + 1 < n && Heap[child] > Heap[child + 1])
        {
          child += 1;
        }
      if (Heap[child] < Heap[parent])
        exchange(&Heap[child], &Heap[parent]);
      else
        break;
      parent = child;
      child = parent * 2 + 1;
    }

  }
  //打印数据
  for (i = 0; i < n; i++)
  {
    printf("%d ", Heap[i]);
  }
  free(Heap);
  fclose(pf);
}
void random(int n)
{
  FILE* pf = fopen("./test.txt", "w");
  if (pf == NULL)
  {
    perror("fopen");
    return 1;
  }
  srand(time(NULL));
  int i = 0;
  for (i = 0; i < 10000; i++)
  {
    fprintf(pf, "%d\n", (rand() + i) % 100000);
  }

  fclose(pf);
}

int main()
{
  int n = 10;

  PrintTop(n);



  return 0;
}

上面的代码中的建堆的代码可以使用插入小堆然后进行向上调整的方法,还有一种方法是假设一棵二叉树的

左右子树都是大堆或者小堆,然后我们只需进行根节点和左右子树点进行调整



我们只需对最后叶节点的父节点开始进行向下调整,然后依次往下,

// 第二种方法
  //从最后一个节点的父亲开始向下调整,我们创建的是小堆 ,
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    //向下调整
    int parent = i;
    int child = parent * 2 + 1;
    while (child < n)
    {
      if (child + 1 < n && Heap[child] > Heap[child + 1])
      {
        child += 1;
      }
      if (Heap[child] < Heap[parent])
        exchange(&Heap[child], &Heap[parent]);
      else
        break;
      parent = child;
      child = parent * 2 + 1;
    }
  }

这种算法的效率更高,第一种方法是我们慢慢学习了堆总结出来的,先插入值进堆,然后向上调整,这样很蛮烦

但是这种方法从一开始就是左右子树就是大堆或者小堆,然后只需进行根节点的向下调整就可以,这个是递归思想的一种体现

堆排序

升序排序建大堆 ,降序排序建小堆

思路: 先 根节点和最后一个叶节点进行交换,这样就可以把最大的数放在数组的末尾,然后长度再减1

依次循环往下直到长度为1,或者下标为0就停止

#include<stdio.h>
typedef int Heapdata;
void exchange(Heapdata *a, Heapdata *b)
{
  Heapdata e = *a;
  *a = *b;
  *b = e;
}
void Heapsort(Heapdata* heap, int size)
{
  //建大堆
  int i = 0; 
  for (i = 1; i < size; i++)
  {
    //向上调整
    int child = i;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
      if (heap[child] > heap[parent])
      {
        //交换
        exchange(&heap[child], &heap[parent]);
        child = parent;
        parent = (child - 1) / 2;
      }
      else
        break;
    }

  }
  //开始升序排序
  while (size > 0)
  {
    // 根节点和最后一个叶节点交换
    exchange(&heap[0], &heap[--size]);
    //向下调整
    int parent = 0;
    int child = parent * 2 + 1;
    while (child < size)
    {
      if (child + 1 < size && heap[child] < heap[child + 1])
      {
        child += 1;
      }
      if (heap[child] > heap[parent])
        exchange(&heap[child], &heap[parent]);
      else
        break;
      parent = child;
      child = parent * 2 + 1;
    }
  }
  


}
int main()
{
  Heapdata a[] = { 2,1,48,5,2,4,7,5,63,8 };
  int size = sizeof(a) / sizeof(a[0]);
  //堆排序
  Heapsort(a, size);


  return 0;
}

总结

这里简单介绍了堆 堆排序和Top K问题,还介绍了向下调整的时间复杂度和向上调整的时间复杂度

目录
打赏
0
0
0
0
12
分享
相关文章
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
51 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
50 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
101 1
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
137 4
|
3月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
225 8
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
50 1
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
46 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
67 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等