树形结构——二叉树专题总结——满二叉树，完全二叉树（堆），普通二叉树以及相应的数据管理方式（上）

前言：

我们都见过树，由根部出发，向上延申的同时向下延申，如图：

从主干开始，依次分支，然后每一个分支再一次分支…以此类推，这样就形成了一棵枝叶茂密，长势良好的参天大树。那么树这样的结构对于我们管理数据又有什么联系呢？试想一下：倘若从根开始，我们就可以入同树一样一直分支一直分支寻找数据，这要比遍历更快，因为操作一次可能就可以访问更多的数据，这便是我们初步要学树形数据结构的意义所在。

1.树的概念：

和我们见过的树不同，数据结构中树的概念如下：

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

如图：

1.树运用的重要思想：

1.注意，最后的强调，树是递归定义的，我们前面学过递归的知识，递归的本质思想是大事化小，小事化了，也就是把一个大的事件拆分成无数个有相同规律和逻辑的小事件，这便是二叉树这块重要的一个思想，之后的很多问题用到，希望在这里大家先记住。

2.注意：树形结构中，子树之间不能有交集，否则就不是树形结构

如图：

这三种就都不是树，因为他们的子节点有交集了，这种被称为图但不是树。

2.树结构中的一些概念：

如图：

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：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而不是0，这是由于0是留给树为空树的时候准备的，倘若第一层叫0，那么空树就只能是-1，有负数就不好表示了，所以我们这里把树的高度的第一层默认为1，空树则为0，然后向下依次加一得到树的高度

3.树的表示方式：

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间

的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法

等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

如图：

这种方式类似一层一层去遍历，同时每一个节点存储两个指针，第一个是指向自己右侧的下一个兄弟节点，另一个负责接收自己的下一层孩子节点，就如上图所示，这样即表达了根与子节点的关系，比如B的三个子节点，它只要存储好第一个孩子，就有第一个孩子依次向右访问它的其他孩子，直到指向空为止。

结构体的构造为：

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

我个人认为这种方式是非常优秀且合理的，很方便去访问，跟双亲表示法相比，更加容易想而且不容易出错，对于树的访问是很优秀的

4.树的实际应用：

说到这里，可能大家会有疑问，树能用来干什么呢？我学过的链表和顺序表已经可以存储大量的数据并且管理他们了，学习树形结构怎样运用呢？那不妨打开你电脑的文件夹，想一想电脑的文件系统是怎样去存储数据的呢？

在一个文件夹下面，有着多个文件夹或者文件，这种存储方式让人可以清楚的知道文件的位置，而且得益于树的特点，树中数据的位置是唯一的，故访问的路径唯一且很有秩序，这是链表或者顺序表很难做到的，所以，我们的Windows或者LINUX系统的文件存储就是以树形的结构进行的，这便是树的一个非常典型的运用实例。

2.树中的典型–二叉树：

既然我们已经熟悉了树形结构，下面就来介绍我们树形结构中最常见的一种树：二叉树

如图：

1.二叉树的概念：

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成，也就是说：
   1… 二叉树不存在度大于2的结点
   2 . 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
   如图：
   
   二叉树可能会出现下面的情况：
   
   所以，我们处理二叉树的数据的时候，坚持的原则就是按照次序，同时也要滴水不漏，不能放过任何一个点机械化的挨个审查一遍，这便是我说为什么二叉树需要使用递归的思想，因为递归本质就是一种机械式审查方式。

2.二叉树的一些性质（最好记下来）：

注意最后一条的2 3点，这个在后面在进行向下调整交换时会用到。！！！！！！而且再次强调，这些都是二叉树方面的性质，不是任意一棵树的，千万别记错了！！！！！！！

3.二叉树的类型：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
   说，如果一个二叉树的层数为K，且结点总数是2^K-1 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
   的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
   应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
   3.普通二叉树：即不满足上面两种的，存在左节点右节点不全的二叉树。
   ！！注意，满二叉树本质上就是特殊的完全二叉树，所以更笼统的分，二叉树就两种：普通二叉树和完全二叉树。！！
   如图：
   
   
   这便依次是：满二叉树，完全二叉树，普通二叉树。

4.二叉树的存储方式：

俗话说，兵来将挡水来土掩，二叉树也是如此，根据不同的类型我们选择不同的存储方式。

我们常见的存储二叉树的方式有两种：

1.顺序存储：即使用顺序表存储二叉树的数据，由于顺序表存在一定的死板的机械性和泛用的规律，故用来存储满二叉树和完全二叉树非常适合，但也不是不能存储普通二叉树，不过需要浪费很多的空间。

2.链式存储：即使用带有指针的链接方式存储二叉树的数据，由于指针指向的灵活性，故用来存储情况复杂的普通二叉树非常适合。

下面，就让我们详解一下这两种二叉树的存储方式！！！

3.二叉树顺序存储结构

1.物理结构和逻辑结构：

首先在我们正式开始讲顺序结构时，我们要先强调一下物理结构和逻辑结构的关系，防止大家记混。

物理结构是实际存在的，在二叉树这里，我们就是用顺序表实现二叉树，也就是数组，而逻辑结构是在我们脑袋里的想象出来的，并不是实际存在的，也就是：

在我们想象里的结构是这样的：

但实际上它是这样的：

那我们如何串联起他们两个呢？

这个时候让我们回想一下二叉树的性质：第最后一条的1 2 3点：

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否则无右孩子

也就是说

1.父亲节点 * 2+1=左子节点
2.父亲节点 * 2+2=右子节点
3.（任意子节点-1）/2=父亲节点

注意，我这里强调的节点是指相应的对应的数组的下标，所以有了这个公式，我们的数组一下子便清晰成了一张二叉树的模样了，有了这样的概念，让我们正式进入二叉树顺序结构的实现吧：

代码如下：

头文件：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>//文件函数头文件
#include<time.h>//伪随机函数头文件
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void Swap(HPDataType* child, HPDataType* parent);//交换数据
void HeapPrint(HP* php);//打印二叉树堆
void HeapInit(HP* php);//初始化二叉树（注意，此时还不是堆，只是初始化一个数组）
void HeapInitArray(HP*php,int*a,int n);//初始化堆的标准方法，注意，这种初始化是直接将现有的数据建成为堆
void HeapDestroy(HP* php);//销毁二叉树堆
void HeapPush(HP* php,HPDataType x);//尾插
void HeapPop(HP* php);//删除数据（删除根）
void Adjustdown(HPDataType* a, int n, int parent);//向下调整
void Adjustup(HPDataType* a, int child);//向上调整
HPDataType HeapTop(HP* php);//找根元素
bool HeapEmpty(HP* php);//判断为空

函数文件

#include"Heap.h"
void HeapInit(HP* php)//初始化二叉树堆
{
  assert(php);
  php->a = NULL;
  php->size =php->capacity= 0;
}
void HeapDestroy(HP* php)//销毁二叉树堆
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)//交换数据
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
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 = (parent - 1) / 2;
    }
    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* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("realloc failed");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  php->size++;
  Adjustup(php->a, php->size - 1);
}
void HeapPrint(HP* php)//打印
{
  assert(php);
  int i = 0;
  for (i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
void Adjustdown(HPDataType*a,int n,int parent)//向下调整
{
  int child = parent * 2 + 1;//这里的做法类似于求最大值的假设法。
  while(child<n)
  {
    //找出小孩子
    if (child+1<n&&a[child + 1] < a[child])//注意，加上这个child+1<n的目的是防止越界，因为假设child<n进入循环，而child恰好是最后一个元素，则child+1则越界了，所以我们不仅要保证child不越界，child+1也要不越界，这样就可以处理只有一个子节点的情况了
    {
      child++;//首先找到两个子节点中更大或者更小的那个节点，作为接下来向下调整的子节点
    }
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    } 
  }
}
//总结：向下调整传父亲节点，向上调整传孩子节点
void HeapPop(HP* php)//删除根数据，根子节点交换然后删除，之后向下调整，向下调整的前提：左右子树是大堆或者小堆
{
  assert(php);
  assert(php->size > 0);
  Swap(&(php->a[0]),&(php->a[php->size - 1]));
  php->size--;
  Adjustdown(php->a, php->size,0);//注意，别忘了传的是下标，而不是元素内容
}
HPDataType HeapTop(HP* php)//找根元素
{
  assert(php);
  assert(php->size > 0);
  return php->a[0];
}
bool HeapEmpty(HP* php)//判断为空
{
  assert(php);
  return php->size == 0;
}
void HeapInitArray(HP* php, int* a, int n)//将现有的数据初始化为堆的函数，注意，是现有的数据。
{
  assert(php);
  assert(a);
  php->a = (HPDataType*)malloc(sizeof(int) * n);
  if (php->a == NULL)
  {
    perror("malloc failed");
    exit(-1);
  }
  php->size = n;
  php->capacity = n;
  memcpy(php->a, a, sizeof(HPDataType)* n);
}

由于我们是依托顺序表来构建的，故顺序表的初始化，销毁，判断为空，打印，找根元素（也就是下标为0的最开始的元素），数据交换，就不过多赘述了，这里我们重点谈谈插入和删除函数的思路：