• 【二叉树】树的概念、结构、应用/堆

    目录

    1_树的概念及其结构

    1.1_树的相关概念

    1.2_树的表示

    ​编辑

    1.3_树的应用

    2_二叉树概念及结构

    2.1_概念

    2.2_特殊的二叉树

    2.3_二叉树的性质

    2.4_二叉树的存储结构

    3_堆

    3.1_堆的性质

    3.2_堆的实现

    3.2.1_堆向下调整算法

    3.2.2_堆的插入

    3.2.3_堆的插删除

    3.2.4_建堆的时间复杂度

    3.3_堆的应用

    3.3.1_top_K问题

    3.3.2_堆排序

     

    1_树的概念及其结构

    1.1_树的相关概念

    • 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：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.2_树的表示

    树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

    1. typedef int DataType;
    2. struct Node
    3. {
    4.     struct Node* _firstChild1; // 第一个孩子结点
    5.     struct Node* _pNextBrother; // 指向其下一个兄弟结点
    6.     DataType _data; // 结点中的数据域
    7. };

     

    1.3_树的应用

    表示文件系统的目录树结构

     

    2_二叉树概念及结构

    2.1_概念

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

    1. 或者为空

    2. 或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成

     

    注意：对于任意的二叉树都是由以下几种情况复合而成的：

    2.2_特殊的二叉树

    1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

    2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

     

    2.3_二叉树的性质

    1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有个2^{i-1}个结点.

    2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数2^h-1 .

    3. 对任何一棵二叉树, 如果度为0其叶结点个数为n_0 , 度为2的分支结点个数为 ,则有 n_0＝n_2 ＋1

      假设树上所有的边数为B,结点总数为n

      n=n_0+n_1+n_2

      B=n-1=2n_2+n_1

      联立解得 n_0＝n_2 ＋1

    2.4_二叉树的存储结构

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

    顺序存储

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

    链式存储

    二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后续的红黑树会用到三叉链。

    1. typedef int BTDataType;
    2. // 二叉链
    3. struct BinaryTreeNode
    4. {
    5.     struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    6.     struct BinTreeNode* _pRight; // 指向当前节点右孩子
    7.     BTDataType _data; // 当前节点值域 
    8. }
    9.  
    10. // 三叉链
    11. struct BinaryTreeNode
    12. {
    13.     struct BinTreeNode* _pParent; // 指向当前节点的双亲
    14.     struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    15.     struct BinTreeNode* _pRight; // 指向当前节点右孩子
    16.     BTDataType _data; // 当前节点值域
    17. }；

    3_堆

    3.1_堆的性质

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

    2. 堆总是一棵完全二叉树。

     

    3.2_堆的实现

    3.2.1_堆向下调整算法

    现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

    向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

    样例说明:

    int array[] = {27,15,19,18,28,34,65,49,25,37};

     

    3.2.2_堆的插入

    先插入一个数到数组的尾上，再进行向上调整算法，直到满足堆。

    // 堆插入数据对其他结点没有影响
// 只是可能会影响从他到根节点路径上的结点关系

    3.2.3_堆的插删除

    删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

    结束条件：

    1. 父亲 <= 小的孩子，则停止

    2. 调整到了叶节点的位置（叶子特征：没有左孩子，左孩子的下标超出数组的范围，不存在）

    3.2.4_建堆的时间复杂度

    因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)

    每层结点的个数 * 每层最多向下调整的次数

      

    3.3_堆的应用

    3.3.1_top_K问题

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

    对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

    最佳的方式就是用堆来解决，基本思路如下：

    1. 用数据集合中前K个元素来建堆

      1. 前k个最大的元素，则建小堆

      2. 前k个最小的元素，则建大堆

    2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

    以求前K个最大的数为例： 1.用前K个数建立一个K个数的小堆 2.剩下的N-K个数，依次跟堆顶的数据进行比较 如果比堆顶数据大，就替换堆顶的数据，再向下调整 3.最后堆里面K个数就是最大的K个数

    3.3.2_堆排序

    堆排序即利用堆的思想来进行排序，总共分为两个步骤：

    1. 建堆

      1. 升序：建大堆

        1. 建立大堆，选出最大的数

        2. 最大的数跟最后一个数交换

        3. 把最后一个数不看做是堆里面的数据，进行向下调整，就可以选出次大的数，以此类推，重复上述过程

      2. 降序：建小堆

    2. 利用堆删除思想来进行排序(从后往前逐渐排序成功)

    建堆的时间复杂度是O(n),堆排序的效率是O(nlogN)

    1. void AdjustDown(int* a, int n, int parent)
    2. {
    3.     int child = parent * 2 + 1;
    4.     while (child < n)
    5.     {
    6.         // 选出左右孩子中小的那一个
    7.         if (a[child + 1] < a[child] && child + 1 < n)
    8.         {
    9.             ++child;
    10.         }
    11. ​
    12.         // 如果小的孩子小于父亲，则交换，并继续向下走
    13.         if (a[child] < a[parent])
    14.         {
    15.             Swap(&a[child], &a[parent]);
    16.             parent = child;
    17.             child = parent * 2 + 1;
    18.         }
    19.         else break;
    20.     }
    21. }
    22. // 方法1：从最后一层叶节点的上一层开始向下调整
    23. // <==> 从满足堆性质的结点开始向下调整
    24. for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    25. {
    26.     AdjustDwon(a, n, i);
    27. }
    28. // 方法2：依次选数，调整堆
    29. for (int end = n - 1; end > 0; end--)
    30. {
    31.     Swap(&a[end], &a[0]);
    32.     // 再调堆，选出次小数
    33.     AdjustDwon(a, end, 0);
    34. }
    35. ​

    1. 二叉搜索树
       

    2. 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

    3. Huffman Tree(哈夫曼树)

  • 相关阅读:
    C#学习系列之装箱、拆箱、自定义转化、重载运算符
    利用python可视化散点图及其计算欧式距离分析相关性
    04.OpenWrt-连接有线网络
    『力扣刷题本』:链表分割
    防止泄露，保护隐私！如何清除你的谷歌搜索历史记录
    SELinux for Android的基本知识和实战
    VUE UI组件ui-libs.vercel.app 花了太长时间进行响应怎么解决？
    C++运动会分数统计系统
    CSP-J 2020 第二轮 优秀的拆分（power）题解 —— 特别篇
    leecode |美化数组的最小删除个数
  • 原文地址：https://blog.csdn.net/forever_bryant/article/details/127584981