前言：到了二叉树这个章节，需要对递归以及函数栈帧有一定的理解，因为树的结构并不是线性的，它的每一个节点都可以看成一个树，比较适合用递归来进行各种操作，另外递归在程序出错进行调试时不会很直观的表现出来，需要自己动手画递归图辅助纠错

树

数据结构中的树

数据结构中的树与日常生活中的树不同，日常生活中的树是根在下，枝叶往上长，而数据结构中的树根在最上面，枝叶往下长

树在计算机上的应用十分广泛，例如我们使用的文件系统，拿windows来说，把C盘看成树根的话，C盘内的文件都算是树枝和树叶，树枝是C盘内的文件夹，而树叶是单独的一个文件，树上的树枝可能还会长树枝和树叶，同样的，文件夹里可能还有其他文件夹和文件

按照我们人类血缘关系来分的话，C盘就是根（父亲），C盘内的文件夹以及文件都是子树（孩子）

树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的度为6

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I，K，L，M，Q节点为叶节点

非终端节点或分支节点：度不为0的节点； 如上图：A，D、E、J节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林

二叉树

二叉树的概念

了解完树的相关概念，接下来我们要开启二叉树之旅，二叉树是度最大为2的树，简单来说，二叉树任意一个节点最多只有两个孩子，可以只有一个孩子，或者没有孩子

满二叉树

了解过二叉树的基本形式，那么来了解一下满二叉树，满二叉树是每一层的节点数都达到最大值的树，它不会存在某个根节点只有一个孩子的情况，满二叉树的节点总数满足公式2^k -1，k是二叉树的层次，满二叉树某一层的节点个数满足公式2^(k - 1)，下图为满二叉树

完全二叉树

完全二叉树和满二叉树的定义是类似的，但完全二叉树不要求最后一层的节点数达到最大值，但最后一层的节点必须依次从1~n插入的，不能跨顺序，用图片展示更清晰点

上图是满足完全二叉树的情况，接下来看看不满足的情况

完全二叉树允许最后一层的节点值不是最大值，要是最大值当然也可以，不过那样不就是满二叉树了嘛，由此可知，满二叉树也是完全二叉树，是特殊的完全二叉树

完全二叉树的用法

为什么要说大半天的完全二叉树呢？这与二叉树的存储形式有关，目前我们掌握了两种存储结构，一种是数组，另一种是链表，那么究竟选择哪种方式存储二叉树呢？接下来分析一下

用数组的方法存储：

1.完全二叉树

2.非完全二叉树

因为数组就是靠下标来定位二叉树的节点的，利用数组来存储，完全二叉树能够较为充分的利用数组空间，而非完全二叉树对空间的浪费比较严重

把二叉树用数组存储 ，这中间又产生了一个问题，我二叉树可不是数组那样的线性结构，二叉树知道父节点，那么就能找到孩子节点，例如上图二叉树中的2，知道了父节点2，那么我就能找到孩子节点1和3，但在数组中1和3并不与2挨着，那该怎么在数组中，知道2就能找到1和3呢，既然数组是用下标来表示二叉树的节点，那就观察父节点和子节点的下标

通过前人的探究，发现了父节点和子节点的下标有以下规律

parent : 表示父节点的下标值

leftchild : 表示左孩子的下标值

rightchild : 表示右孩子的下标值

有规律 ： leftchild = 2 * parent +1

               rightchild = 2 * parent +2

               parent = (child - 1) / 2   child表示左孩子和右孩子都可以

这下一切都活过来了，在数组中也能做到，知道父节点就能找到孩子节点，知道孩子节点就能找到父节点，就能做到数组与二叉树的无缝切换

用链表的方法

先定义二叉树的结构类型

typedef int DataType;
typedef struct BinaryTree
{
  DataType val;               //值
  struct BinaryTree* left;    //左孩子
  struct BinaryTree* right    //右孩子
}BTNode;

利用链表就能实现和二叉树结构图类似的效果，对完全二叉树和非完全二叉树来说，都是蛮不错的，但是链表节点使用和创建的消耗是高于数组的，因此像完全二叉树这样的就用数组来存储，非完全二叉树就适合用链表来存储

堆

堆的定义

如果把一个集合的元素以完全二叉树的结构存放到数组中，且要求，任一个节点的值都不大于或小于其父节点的值，最终形成的结构就是堆

故而堆有两个性质

1.堆是一个完全二叉树

2.堆中每一个节点的值都不大于或小于其父节点的值

根据要求堆可以分为大堆和小堆

大堆就是任一节点的值都不大于其父节点，那么根节点的值是最大的

小堆就是任一节点的值都不小于其父节点，那么根节点的值是最小的

堆的实现

实现堆以及对堆进行相应操作的函数

//堆的初始化

void HeapInit(   )

//销毁堆

void HeapDestory(   )

//查看堆的顶根元素

Datatype HeapTop(   )

//判断堆是否为空

bool HeapEmpty(   )

//堆中节点个数

int HeapSize(   )

//往堆中插入数据

void HeapInsert(   )

//删除顶端元素

void HeapPop(   )  

想要实现一个堆首先是要定义堆的数据类型呀，上面我们提到过，堆是完全二叉树，因此用数组来存储是比较好的，为了方便以后空间的扩充，这里选择了动态存储，定义好类型就可以创建并初始化一个堆，接下来我们就建一个小堆，走一遍建堆的过程

typedef int Datatype;
typedef struct heap
{
  Datatype* pos;  //用来存放数据的数组
  int size;        //标记数组元素个数
  int capacity;    //数据的容量
}heap;
void HeapInit(heap* hp)
{
  assert(hp);
  hp->pos = NULL;
  hp->size = hp->capacity = 0;
}

创建并初始化好，接着就是往堆中插入元素，插入元素首先我们要考虑容量是否已经满了，如果容量满了就要进行扩充，其次往堆中插入元素可不是直接放入数组中那么简单，小堆的结构要保证每一个节点的孩子都比该节点大

如果插入的数值是随机的，那么极大可能导致这个堆被破坏了

我们的目的就是创建一个小堆，你这一随机插入一个元素堆可能就没了，这可不行

向上调整法：如果出现随机插入的数值比它的父节点还小，为了满足堆的定义，我们就要把堆重新调整一下，既然插入的节点比父节点还小，那么就将该节点与它的父节点进行交换，把较小的值换上去，也就是儿子变老子，如果交换之后发现，该节点仍然比它的父节点低，那么就持续交换，直到到了堆顶，或比它的父节点大了才停止

前面提到的根据孩子节点下标值推断出父节点下标值，这不就派上用场了嘛，利用向上调整这个法宝，再插入数值就不怕了，插完调整一下就完了，下面是代码实现

void HeapInsert(heap* hp, int child, Datatype val)
{
  assert(hp);
   //判断容量是否已满
  if (hp->size == hp->capacity)
  {
    int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
    Datatype* tmp = (Datatype*)realloc(hp->pos, sizeof(Datatype) * newcapacity);
    if (tmp == NULL)
    {
      assert(tmp);
    }
    hp->pos = tmp;
    hp->capacity = newcapacity;
  }
  hp->pos[child] = val;
  hp->size++;
 //对新插入的元素进行向上调整，Swap函数自行实现
    while (child > 0)
  {
    int parent = (child - 1) / 2;
    if (hp->pos[child] < hp->pos[parent])
    {
      swap(&hp->pos[child], &hp->pos[parent]);
      child = parent;
    }
    else
    {
      break;
    }
  }
}

搞完了插入，接下来就是删除了，堆的元素删除一般是指将堆顶元素给删掉，可把堆顶元素给删除掉，接下来怎么办，群龙无首了。这样怎么样，在堆顶元素删除之前，选一个它较小的孩子替换它

较小的孩子替换掉父亲，但是替换的这个值走了之后，它的孩子仍然群龙无首了，这个问题就一直延续下去，显然这样并不好，为了展示这个方法的弊端，我将堆顶元素的两个子堆调换了一下

从数组结构中能看出来，如果用刚才的方法，会删除掉错误的元素，导致堆的结构被破坏，怎么办呢，接下介绍另一种调整方法，向下调整法

向下调整法：删掉堆顶元素而不破坏堆，我们不妨将堆顶元素与堆中最后一个元素交换一下，此时size减1，减掉的正好就是我们要删掉的7，然后利用向下调整，将刚才交换到堆顶的那个元素调整到属于它的位置

向下调整的过程就是选取它最小的孩子，然后交换，一直交换到比它的两个孩子都小或到堆末尾为止

//向下调整的代码
void AdjudtDown(Datatype *p ,int n, int parent)
{
  assert(p);
  int minchild = 2*parent +1;
  while (minchild < n)
  {
    if (minchild+1 < n && p[minchild] > p[minchild+1])
    {
      minchild++;
    }
    if (p[parent] > p[minchild])
    {
      swap(&p[parent], &p[minchild]);
      parent = minchild;
      minchild = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}

最麻烦的插入和删除我们已经了解完了，剩下的是些基本操作了，这里就不多唠叨了 ，目前我们已经了解了向下和向上调整堆的思想，可以尝试一下堆排序了

链式二叉树

链式二叉树的定义

前面主要是在介绍完全二叉树，不过二叉树形式更多的是链式二叉树，下面我们继续看看链式二叉树，因为链式二叉树的不规则特性，所以用链表来存储更合适，一个二叉树节点主要包括三个方面的信息，它的左孩子，它的右孩子，它自身的值

typedef int BTDataType;
typedef struct BinaryTree
{
    BTDataType data;
  struct BinaryTree* left;
  struct BinaryTree* right;
}BTNode;

链式二叉树的实现

下面是链式二叉树的一些功能

二叉树单节点创建

BTNode* CreatNode(int val);

二叉树前序遍历

void BinaryTreePrevOrder(BTNode* root);

二叉树中序遍历

void BinaryTreeInOrder(BTNode* root);

二叉树后序遍历

void BinaryTreePostOrder(BTNode* root);

二叉树节点个数

int BinaryTreeSize(BTNode* root);

二叉树叶子节点个数

int BinaryTreeLeafSize2(BTNode* root);

二叉树深度

int  BinaryTreeDepth(BTNode* root);

二叉树销毁

void BinaryTreeDestory(BTNode* root);

二叉树单节点创建
BTNode* CreatNode(int val)

创建一个二叉树节点是比较简单的，malloc一个节点，并赋上初始值

BTNode* CreatNode(int  val)
{
  BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
  assert(tmp);
  tmp->left = NULL;
  tmp->right = NULL;
  tmp->data = val;
  return tmp;
}

二叉树的前序遍历

void BinaryTreePrevOrder(BTNode* root)

从这里开始就要借助递归来完成这个任务，前序遍历简单来说就是程序到某个二叉树节点上时，如果这个节点非空，那就打印出该节点的值，然后再向左遍历和向右遍历

//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}

 中序遍历和后序遍历都是类似的思想，感兴趣可自行尝试递归展开，这里不过多说了，我直接放上代码了

//二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  BinaryTreeInOrder(root->left);
  printf("%d ", root->data);
  BinaryTreeInOrder(root->right);
}
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%d ", root->data);
}

二叉树节点个数
int BinaryTreeSize(BTNode* root)

二叉树的节点个数通过遍历整个二叉树，不是空空间就加1，最终结果就是节点的个数

int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

二叉树叶子节点个数
int BinaryTreeLeafSize2(BTNode* root)

叶子节点就是没有孩子的节点，也就是在遍历数组的过程中，只要发现某个节点，它的左右孩子都为空指针，那么就加1，最终返回的结果就是叶子节点总数

int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  else if (root->left == NULL && root->right == NULL)
    return 1;
  return BinaryTreeLeafSize2(root->left) + BinaryTreeLeafSize2(root->right);
}

二叉树深度
int  BinaryTreeDepth(BTNode* root)

二叉树的深度，就是分别统计左孩子的高度，以及右孩子的高度，然后对比选出最大的那个

int  BinaryTreeDepth(BTNode* root)
{
  if (root == NULL)
    return 0;
  int left = BinaryTreeDepth(root->left) +1;
  int right = BinaryTreeDepth(root->right) +1;
  int max = left > right ? left : right;
  return max;
}

二叉树销毁
void BinaryTreeDestory(BTNode* root)

二叉树的销毁可以借助后序遍历，因为后序遍历是深度优先，上来先去到最深处，然后逐步往上走，在这个过程中不断销毁节点，如果上来就销毁最开始的，那将导致失去后面的节点的地址，无法找到子节点

void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
}