二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

通过上篇博文的讲解我们得知完全二叉树和满二叉树是可以通过数组来进行存储的，它们间的父子关系可以通过下标来表示。这里再强调下物理结构是是在内存当中实实在在存储的，在物理上是数组，但是在逻辑上要把它看出二叉树。

普通的二叉树推荐用链式存储，不适合用数组来存储，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。因为空间利用率高，不会造成浪费。

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

二叉树的堆排序

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段

堆的概念

堆是一个完全二叉树，它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中。堆分为两种：小根堆、大根堆

小堆：每一个父结点的值均小于等于其对应的子结点的值，而根结点的值就是最小的。

大堆：每一个父结点的值均大于等于其对应的子结点的值，而根结点的值就是最大的。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值。

堆总是一棵完全二叉树

通过物理结构可以得知以下两点：

有序的一定是堆
无序的可能是堆

堆向上调整算法

思路：

此算法是为了确保插入数据后的堆依然是符合堆的性质而单独封装出来的函数，就好比如我们后续要插入的数字10

为了确保在插入数字10后依然是个小根堆，所以要将10和28交换，依次比较父结点parent和子结点child的大小，当父小于子结点的时候，就返回，反之就一直交换，直到根部。

parent = (child - 1) / 2，我们操控的是数组，但要把它想象成二叉树

代码实现：

#include<iostream>
#include<string> 
using namespace std;
typedef int HPDataType; //堆中存储数据的类型
//交换
void Swap(HPDataType* pa, HPDataType* pb)
{
  HPDataType tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}
//向上调整算法
void AdjustUp(HPDataType* a, size_t child)
{
  size_t parent = (child - 1) / 2;
  while (child > 0)
  {
    //if (a[child] > a[parent]) //大根堆
    if (a[child] < a[parent]) //小根堆
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//升序
void HeapSort(int* a, int n)
{
  //建堆
  int i = 0;
  for (i = 1; i < n; i++) //应该从i=1时遍历，因为第一个数据在堆里不需要调整，后续再插入时调整
  {
    AdjustUp(a, i);
  }
}
int main()
{
  int a[] = { 4,2,7,8,5,1,0,6 };
  HeapSort(a, sizeof(a) / sizeof(int));
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

堆向下调整算法

思路：

顾名思义，从上往下调整，即

找出左右孩子中最小的那个
跟父亲比较，如果比父亲小，就交换
再从交换的孩子位置继续往下调整

最终变为小根堆

#include<iostream>
#include<string> 
using namespace std;
typedef int HPDataType; //堆中存储数据的类型
//交换
void Swap(HPDataType* pa, HPDataType* pb)
{
  HPDataType tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}
//向下调整算法
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
  int parent = root;
  int child = 2 * parent + 1;
  while (child < size)
  {
    //1、确保child的下标对应的值最小，即取左右孩子较小那个
    if (child + 1 < size && a[child + 1] < a[child]) //得确保右孩子存在
    {
      child++; //此时右孩子小
    }
    //2、如果孩子小于父亲则交换，并继续往下调整
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break; //如果中途满足堆的性质，直接返回
    }
  }
}
//升序
void HeapSort(int* a, int n)
{
  //建堆
  int i = 0;
  //2、向下调整
  for (int i = (n - 1 - 1)/2; i >= 0; i--)//从0开始找父节点根
  {
    AdjustDown(a, n, i);
  }
}
int main()
{
  int a[] = { 4,2,7,8,5,1,0,6 };
  HeapSort(a, sizeof(a) / sizeof(int));
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

堆排序应用之TopK问题

TOP-K问题：N个数里面找出最大/最小的前k个。一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

解决方案：

用前K个数建立一个K个数的小堆，然后剩下的N-K个依次遍历，如果比堆顶的数据大，就替换它进堆（向下调整），最后堆里面的K个数就是最大的K个。

#include<iostream>
#include<string>
#include<stdlib.h> 
using namespace std;
typedef int HPDataType; //堆中存储数据的类型
//交换
void Swap(HPDataType* pa, HPDataType* pb)
{
  HPDataType tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}
//向下调整算法
void AdjustDown(int* a, size_t size, size_t root)
{
  int parent = (int)root;
  int child = 2 * parent + 1;
  while (child < size)
  {
    //1、确保child的下标对应的值最小，即取左右孩子较小那个
    if (child + 1 < size && a[child + 1] < a[child]) //得确保右孩子存在
    {
      child++; //此时右孩子大
    }
    //2、如果孩子小于父亲则交换，并继续往下调整
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}
void PrintTopK(int* a, int n, int k)
{
  // 1. 建堆--用a中前k个元素建堆
  int* kminHeap = (int*)malloc(sizeof(int) * k);
  //assert(kminHeap);
  for (int i = 0; i < k; i++)
  {
    kminHeap[i] = a[i];
  }
  //建小堆
  for (int j = (k - 1 - 1) / 2; j >= 0; j--)
  {
    //从倒数第一个非叶节点开始
    AdjustDown(a, k, j);
  }
  // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
  for (int i = k; i < n; i++)
  {
    if (a[i] > kminHeap[0])
    {
      kminHeap[0] = a[i]; //如果比堆顶大，就替换
      AdjustDown(kminHeap, k, 0); //向下调整确保为堆
    }
  }
  for (int j = 0; j < k; j++)
  {
    printf("%d ", kminHeap[j]);
  }
  printf("\n");
  free(kminHeap);
}
void TestTopk()
{
  int n = 10000;
  int* a = (int*)malloc(sizeof(int) * n);
  //srand(time(0));
  for (size_t i = 0; i < n; ++i)
  {
    a[i] = rand() % 1000000; //产生一个随机数，数值均小于100万
  }
  a[5] = 1000000 + 1;
  a[1231] = 1000000 + 2;
  a[531] = 1000000 + 3;
  a[5121] = 1000000 + 4;//在随机位置设置大于100万的数，若全部找出则算法成立
  a[115] = 1000000 + 5;
  a[2335] = 1000000 + 6;
  a[9999] = 1000000 + 7;
  a[76] = 1000000 + 8;
  a[423] = 1000000 + 9;
  a[3144] = 1000000 + 10;
  PrintTopK(a, n, 10);
}
int main()
{
  TestTopk();
  return 0;
}

二叉树的遍历

由上文得知，普通二叉树也可以使用数组来存储，但是会存在大量的空间浪费，而完全二叉树就不会这样，因为其空间利用率是％100的。既然这样，那普通二叉树该如何进行存储呢？

答案是普通二叉树使用链式结构进行存储。

链式二叉树

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址

链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

创建二叉树

在具体讲解之前，再回顾下二叉树，二叉树是：

空树
非空：根节点，根节点的左子树、根节点的右子树组成的。

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

手动创建一颗二叉树（以上图为例来创建）

在学习二叉树的基本操作前，需要先创建一颗二叉树，然后才能学习其相关的基本操作。由于我们刚刚接触二叉树，为了能够先易后难地学习，我们手动创建一颗简单的二叉树来来方便大家学习。等二叉树结构了解后，后期我们会带着读者研究二叉树地真正的创建方式。

思路：

其实构建一棵树的思想还是挺简单的，按照图示创建6个节点，并根据图中的样子将节点顺次链接起来

代码演示：


#include<iostream>
#include<string>
#include<stdlib.h> 
using namespace std;
//创建二叉链结构
typedef int BTDataType; //本文以int整型为例
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  int data;
}BTNode;
//创建结点
BTNode* BuyBTNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  node->data = x;
  node->left = node->right = NULL;
  return node;
}
//构建树
BTNode* CreatBinaryTree()
{
  //创建6个结点
  BTNode* node1 = BuyBTNode(1);
  BTNode* node2 = BuyBTNode(2);
  BTNode* node3 = BuyBTNode(3);
  BTNode* node4 = BuyBTNode(4);
  BTNode* node5 = BuyBTNode(5);
  BTNode* node6 = BuyBTNode(6);
  //将结点连接起来，构成自己想要的树
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  //返回根结点
  return node1;
}
//前序遍历
void PrevOrder(BTNode*root)
{
  if (root == NULL)
  {
    printf("NULL  "); //如果为空，就打印空
    return;
  }
  printf("%d  ", root->data);
  PrevOrder(root->left);
  PrevOrder(root->right);
}
int main()
{
  BTNode* tree = CreatBinaryTree();
  //PrevOrder(tree);
  return 0;
}

二叉树的遍历方法

以一颗二叉树为例：

后续的遍历均是建立在次二叉树基础上展开。

前序遍历

前序遍历，也叫先根遍历

遍历顺序：根 -> 左子树 -> 右子树

思路：

既然先从根走，根就是1，接下来访问1的左子树，此时又要先访问其左子树的根为2，接着再访问2的左子树->根：3，接着访问其左子树和右子树，不过均为空，递归返回，此时3作为2的左子树访问完毕，访问2的右子树为NULL，再递归返回此时1的左子树就访问完毕了，访问其右子树，同理访问左树4，再访问左树5，接着左右子树NULL，递归返回访问4的右树，……类似的

图示：

代码演示：

前序遍历的代码非常简洁，短短几行即可操作，先看代码：

//前序遍历
void PrevOrder(BTNode*root)
{
  if (root == NULL)
  {
    printf("NULL  "); //如果为空，就打印空
    return;
  }
  printf("%d  ", root->data);
  PrevOrder(root->left);
  PrevOrder(root->right);
}

144. 二叉树的前序遍历 - 力扣（LeetCode）

//写一个辅助函数求出二叉树的节点的个数，方便后续malloc
int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//再写一个辅助函数中专门进行递归，防止用主函数递归时每次都要malloc
void _preorder(struct TreeNode* root, int* a, int* i)
{
    //如果二叉树为空，直接返回
    if (root == NULL)
    {
        return;
    }
    //
    a[(*i)++] = root->val;
    _preorder(root->left, a, i);
    _preorder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    //用size来接收节点个数
    int size = TreeSize(root);
    //动态开辟数组
    int* a = (int*)malloc(sizeof(int) * size);
    int i = 0;
    //注意i要传地址，因为每次递归都会建立栈帧，递归完即销毁
    _preorder(root, a, &i);
    *returnSize = i;
    return a;
}

中序遍历

遍历规则：

中序遍历，也叫中根遍历

遍历顺序：左子树 -> 根结点 -> 右子树

思路：

根据遍历顺序，我们得知，如若想访问1，得先访问其左子树2，访问2还得先访问其左子树3，类似的，再访问其左子树为NULL，递归返回访问根结点3，再访问右子树NULL，递归返回访问根结点2，再访问右子树NULL，递归返回访问根结点1，再访问其右子树，1的右子树访问规律同1的左子树，这里不过多赘述。

画图演示：

代码演示：

中序遍历的代码和前序遍历一样，看起来都非常简洁：

//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL  "); //如果为空，就打印空
    return;
  }
  InOrder(root->left);
  printf("%d  ", root->data);
  InOrder(root->right);
}

94. 二叉树的中序遍历 - 力扣（LeetCode）

//计算树的结点个数，方便后续malloc数组
int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//创建辅助函数专门用来递归
void InOrder(struct TreeNode* root, int* a, int* i)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left, a, i);
    a[(*i)++] = root->val;
    InOrder(root->right, a, i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * size);
    int i = 0;
    InOrder(root, a, &i);
    *returnSize = i;
    return a;
}

后续遍历

遍历规则：

后续遍历，也叫后根遍历

遍历顺序：左子树 -> 右子树 -> 根结点

思路：

要访问1得先访问1的左子树2，继而得先访问2的左子树3，再先访问3的左子树NULL，右子树NULL，根3，递归返回访问2的右子树NULL，根2，再递归返回访问1的右子树……类似的

画图演示：

代码演示：

后续的代码也非常简单，有了前文前序遍历和中序遍历的基础，后续遍历只需要把打印放后面即可

//后序遍历
void PosOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL  "); //如果为空，就打印空
    return;
  }
  PosOrder(root->left);
  PosOrder(root->right);
  printf("%d  ", root->data);
}

145. 二叉树的后序遍历 - 力扣（LeetCode）

//计算结点个数
int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//辅助函数专门递归
void PosOrder(struct TreeNode* root, int* a, int* i)
{
    if (root == NULL)
    {
        return;
    }
    PosOrder(root->left, a, i);
    PosOrder(root->right, a, i);
    a[(*i)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * size);
    int i = 0;
    PosOrder(root, a, &i);
    *returnSize = i;
    return a;
}

层序遍历

遍历规则：

顾名思义，按层遍历（不需要递归）

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

思路：

层序的遍历则是通过队列来实现的；

首先，把根节点1的结点指针先入队列，队列此时不为空，出队头的数据，把队头数据的孩子2的结点指针和4的结点指针入进去，队列不为空，出2，入孩子3，队列不为空，再出4，把孩子5和6入进去，然后再出，没有孩子继续出，出到最后队列为空。总结如下四句话：

先把根入队列，借助队列性质：先进先出

上一层的节点出的时候，带下一层的节点进去

图示：

代码演示：

//层序遍历
void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueuePush(&q, root); //先把根结点入进去
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q); //取队头
    QueuePop(&q); //出队头
    printf("%d ", front->data); //打印队头数据
    if (front->left)
    {
      QueuePush(&q, front->left); //front左孩子不为空，就入
    }
    if (front->right)
    {
      QueuePush(&q, front->right);//front右孩子不为空，就入
    }
  }
  printf("\n");
  QueueDestory(&q);
}

遍历的经典应用

应用一：前序+中序可以重建

已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（）

A.4 2 5 7 6 9 1

B.4 2 7 5 6 9 1

C.4 7 6 1 2 9 5

D.4 7 2 9 5 6 1

答案：C

解析：

通过前序遍历找到子树的根，在中序遍历中找到根的位置，然后确定根左右子树的区间，即根的左侧为左子树中所有节点，根的右侧为右子树中所有节点。

故：根为： 5

5的左子树：4 7 5的右子树： 6 9 1 2

5的左子树的根为: 7 5的右子树的根为：9

7的左子树: 4 7的右：空 9的左子树：6 9的右子树：2

故这棵树的结构为：

应用二：中序+后序可以唯一确定一颗树

已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（）

A.ABDGHJKCEFILM

B.ABDGJHKCEILMF

C.ABDHKGJCEILMF

D.ABDGJHKCEIMLF

答案：B

解析：

由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间

故：根为: A

A的左子树：JGDHKB A的右子树：ELIMCF

A的左子树的根：B A的右子树的根：C

B的左子树：JGDHK B的右子树：空 C的左子树：ELIM C的右子树：F

B的左子树的根：D C的左子树根：E

D的左子树的根：G D的右子树的根：H E的右子树的根:I

故树的结构为：

应用三：层序遍历经典操作

102. 二叉树的层序遍历 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> vv;
        if(root==nullptr)
            return vv;
        queue<TreeNode*> q;
        int levelSize=1;
        q.push(root);
        while(!q.empty())
        {
            vector<int> levelV;
            while(levelSize--)
            {
                TreeNode* front=q.front();
                q.pop();
                levelV.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            vv.push_back(levelV);
            levelSize=q.size();
        }
        return vv;
    }
};

107. 二叉树的层序遍历 II - 力扣（LeetCode）

可以偷懒，末尾加个

reverse(vv.begin(),vv.end());

【数据结构】拿捏二叉树堆排序与遍历

二叉树的存储结构

二叉树的堆排序

堆的概念

堆向上调整算法

堆向下调整算法

堆排序应用之TopK问题

二叉树的遍历

链式二叉树

创建二叉树

二叉树的遍历方法

前序遍历

中序遍历

后续遍历

层序遍历

遍历的经典应用

应用一：前序+中序可以重建

应用二：中序+后序可以唯一确定一颗树

应用三：层序遍历经典操作

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】 拿捏二叉树堆排序与遍历

二叉树的存储结构

二叉树的堆排序

堆的概念

堆向上调整算法

堆向下调整算法

堆排序应用之TopK问题

二叉树的遍历

链式二叉树

创建二叉树

二叉树的遍历方法

前序遍历

后续遍历

层序遍历

遍历的经典应用

应用一：前序+中序可以重建

应用二：中序+后序可以唯一确定一颗树

应用三：层序遍历经典操作

热门文章

最新文章

相关课程

相关电子书

【数据结构】拿捏二叉树堆排序与遍历