• 树结构的讲解与二叉树的基本运用

    目录：

     一，树的基本知识

    二，树的类型

    三，树的存储

    四，树的基本运算

    五，二叉树堆的基本运用

     一，树的基本知识

            树是一种非线性的数据结构，它是由n个有限结点组合而成为一个具有层次关系的集合，把它叫做树因为它看起来像一颗倒挂的树，也就是说它的根是朝上，叶朝下的。由于树的此种连接性层次结构，所以树是递归定义的，如下图：

            注意：在以上的所有结点中，其中，A结点称为根结点，而根节点是没有前驱结点，且树中有且只有一个根节点(要是有多个根节点或者没有根节点就不是树)。其它结点都是通过层次非线性进行连接，它们彼此间都不相交（注意此特点，要是相交的话就不是树）。如下图：

            以上图中都不是树，因为它们要么有结点相交，要么存在多个根节点。

    树结构中有以下常用的关健名：

    结点的度：一个结点含有的子树个数称为该结点的度，如上图：A有子树B，C，D，度为3。

    叶子结点或终端结点：度为0的结点称为叶结点，如上图中的J，F，K，L，H，I。

    双亲结点：若一个结点含有子结点，则这个结点称为其子结点的双亲结点，如上图中A是B的双亲结点。

    孩子结点：一个结点含有的子树的根结点称为该结点的子结点，如上图：B是A的孩子结点。

    兄弟结点：具有相同父结点的结点互为兄弟结点，如上图：B，C，D是兄弟结点。

    树的度：一棵树中，最大的结点的度称为树的度，如上图：树的度为3。

    结点的层次：从根开始定义起，根为第一层，根的结点为第二层，其余的以此类推。

    树的高度或深度：树中结点的最大层次，如上图：树的高度为4。

    树的祖先：一颗树的根节点称为所有子结点的祖先，如上图：A为祖先。

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

    森林：由多棵不相交的树的集合称为森林。

    二，树的类型

            树的类型根据结构来讲有多种，我们最常用的类型就是二叉树，在初步学习中先深入学习二叉树即可。

    1，二叉树的概念

    二叉树具有以下特征：

           二叉树的结构中不存在度大于2的结点，即在二叉树中，最多由两个结点。

           二叉树的子树有左右之分，次序不可颠倒，因为二叉树是有序结构。

    2，特殊的二叉树

           满二叉树：假设一颗二叉树的高度为h，每一层的结点都是满的，即每个结点的度都为2。

           完全二叉树：假设一颗二叉树的高度是h，前h-1层都是满的，最后一层不一定满，且从左到右都连续。

            

    三，树的存储

           首先，我们要明白一点，在二叉树中，最多就有两个结点，并且这两个结点还都是有序的，在设计中，可能用到增添查找，用数组的结构存储在运用中比较麻烦，因此，二叉树最好用链表的形式来存储，而普通的树结构中结点并不确定，要用链式结构很是麻烦，普通的树结构最好用数组的形式进行存储，但这只是一般情况，而具体要用什么结构存储还需根据我们要实现的功能而定，比如需要随机访问或要求时间效率高的，我们就要使用线性表结构来存储。需要我们插入，删除元素的或不确定要存储元素的数量，我们就要使用链表结构来存储。一般情况下的具体定义如下：

    1，二叉树的形式

    struct TreeNode
    {
        //在这里树中存储整型数据，也可换成其它类型
        int val;
        //左子树，不存在通常置为NULL
        struct TreeNode* left;
        //右子树，不存在通常置为NULL
        struct TreeNode* right;
    };

    2，普通树的形式

    //说明树的度
    #define Max = 10;
    struct TreeNode
    {

        //使用动态顺序表存放孩子指针
        struct TreeNode* child;
        //记录树的大小
        int size;

        //记录数的容量

        int capacity;
    };

    3，线性表存储特殊二叉树

            当我们使用线性表来存储二叉树时，大多情况下是为了随机访问，方便我们很快的找出双亲结点或孩子结点，具体使用和公式如下图：

             通过以上公式，当我们在运用中可很方便的找到双亲结点和孩子结点，但是要说明的是，此公式只适用于完全二叉树或满二叉树，且如果遇到其它树结构，线性表的优势似乎已无大用，这时就要考虑链式结构了。

            总：树的设计方式其实还有很多种，但以上两种方式是我们目前最为基础的使用，在后面深入学习中还会设计更为精妙的存储方式。补充一点，在我们计算机上的文件系统基本就是通过精妙建立的树状结构来存储，只是这种结构比较复杂，在后面的文章会给大家进行介绍。

    四，树的基本运算

            在了解以上的基本知识点后我们必须学会对树进行基本的运算，而笔者对树的研究总结了以下几点重要公式和定理，在树的计算中可很方便的运用。

    1，若规定根结点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点。

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

    3，对任何一颗二叉树，如果度为0，其叶结点(即度为0)个数为n0，度为2的分支结点个数为n2，则有n0 = n2 + 1。(此公式为重点公式)

    4，若规定根结点的层数为1，具有n个结点的满二叉树的深度h = log2(n + 1)。

    5，一颗完全二叉树度为1的结点数要么为1，要么为0，因为其有序结构是从左向右排布的。

            在以上公式中，第三个和第五个为重点记忆，运用较多，第一个和第二个较为简单，可自行推理，第四个运用的比较少。

            明白以上的逻辑后我们需注意在树计算中的几点隐含条件，接下来我用例题的形式跟大家进行解说。        

            在树的运算中要注意的是n1的情况(以上的情况只限制与在完全二叉树中)，其它的运算掌握以上的公式和定理，并且自行灵活运用都比较简单。

    五，二叉树堆的基本运用

    堆的概念：

            首先我们先了解下堆的概念，对于这个名词我们很是熟悉，在计算机的存储方式中就有堆的存储，即堆区，但这里的堆并不是存储方式的那个堆，而是一种非线性结构中的完全二叉树。通常我们会将二叉树改制为堆结构或直接将数据改成堆结构，而在改制之前，我们先了解以下知识。

    堆的分类：

            1，小堆：树中任意一个父亲都小于或等于孩子。

            2，大堆：树中任意一个父亲都大于或等于孩子。

    完全二叉树父子结点的关系：

            上面我们说过，如若我们用顺序表的形式进行存储完全二叉结构(下标从0开始)，在完全二叉树中，我们易得出不同两层之间的双亲结点与孩子结点之间的数学联系：如图所示(因为这点非常重要，我再次强调一下)：

            堆结构的最大问题就在于排序的时候其中的逻辑连接，有了以上知识后，我们就要思考如何用孩子结点找双亲结点之间的关系来进行算法的设置，总的来说就是通过双亲与孩子的比较，进而进行大堆或小堆的建立，其中，最为主要的算法为向下调整或向下调整，代码如下：

    //数据从下往上调整
    void AdjustUp(int* a, int child)//child是孩子结点，a是顺序表
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            //大堆树状规则排序法
            if (a[child] > a[parent])
            {
                //交换
                int t = a[child];
                a[child] = a[parent];
                a[parent] = t;
                //继续往上遍历
                child = parent;
                parent = (parent - 1) / 2;
            }
            //当满足排序状况就可退出算法
            else
            {
                break;
            }
        }
    }

            从下往上调整算法是先从孩子结点开始与双亲结点比较，如若不满足排序状况就进行交换，因为在交换后并不能确定上层的双亲结点与之有序，所以还要继续往上进行遍历，当满足结点之间的有序序列时就说明已经排序好。

            从下往上调整算法，其实就相当于顺序表中后面的元素往前面有序的元素进行排序，从而使不同层次间的双亲结点和孩子结点有序。

    注意要点：

            当进行交换时，要继续往上进行遍历，必须确定上层中双亲结点与孩子结点满足堆的概念，即不同层次间的双亲结点和孩子结点有序，否则将会出现错误。

    //数据从上往下调整
    void AdjustDown(int* a, int n, int parent)//a是顺序表，n是大小，parent是双亲结点
    {
        int child = parent * 2 + 1;
        while (child < n)
        {
            //大堆树状规则排序法
            // 找出小的那个孩子，在这里要注意的是控制下一个孩子结点的不能超出范围
            if (child + 1 < n && a[child + 1] > a[child])
            {
                ++child;
            }
            if (a[child] > a[parent])
            {
                //交换
                int t = a[child];
                a[child] = a[parent];
                a[parent] = t;
                // 继续往下调整
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }

            从上往下调整算法是先从双亲结点开始与孩子结点比较，如若不满足排序状况就进行交换，因为在交换后并不能确定下层的孩子结点与之有序，所以还要继续往下进行遍历，当满足结点之间的有序序列时就说明已经排序好。

            从上往下调整算法，其实就相当于顺序表中前面的元素往后面有序的元素进行排序，从而使不同层次间的孩子结点和双亲结点有序。

    注意要点：

            当进行交换时，要继续往下进行遍历，必须确定下层中双亲结点与孩子结点满足堆的概念，即不同层次间的双亲结点和孩子结点有序，否则将会出现错误。

    效率分析：

            下面，我们来分析下调整算法的效率，显然，空间复杂度为O(1)，时间效率是运用二分思想，所以，时间复杂度为O(logn).

            调整算法明白了之后，接下来就要开始建堆了。上面提到过，无论是向上调整算法还是向下调整算法在交换时都要满足上层相连的结点或下层相连的结点有序，所以运用向上调整算法建堆是要从根节点的左孩子开始，即child = 1，然后不断往后面进行遍历建堆；运用向下调整算法建堆时要从最后一个结点的双亲结点开始，即parent = (n - 1 - 1) / 2，然后不断往前面进行遍历建堆，如下。

    //运用向上调整算法将数组a改成堆结构
    void CreatHeap(int* a, int n) {
        //开始时，孩子结点的下标为1,即child = 1,然后继续往后面遍历，直到最后一个结点为止
        for (int i = 1; i < n; i++) {
            AdjustUp(a, i);
        }
    }

    //运用向下调整算法将数组a改成堆结构
    void CreatHeap(int* a, int n) {
    //开始时，最后一个结点的下标为n-1,其双亲结点的下标为(n - 1 - 1) / 2,然后继续往前面遍历
        for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
            AdjustDown(a, n, i);
        }
    }

    效率分析：

            前面已经说过调整算法的效率，而在建堆时基本要循环遍历所有数据进行调整，所以，建立堆结构的效率：时间复杂度：O(nlogn)      空间复杂度：O(1)。

            学习完如何建堆后接下来就要了解堆结构中的算法，即建立空堆，插入，删除，判断堆是否为空，堆销毁。

            由于这方面设计了很多算法，所以我们可设置一个自己的头文件"Heap.h"来进行算法声明，如下：

    #pragma once
    #include
    #include
    #include
    #include
    #include
    //堆结构，运用动态结构，防止数组大小不够
    typedef struct Heap {
        int* a;
        int size;
        int capacity;
    }Heap;
    void Swap(int* x, int* y);
    //向上调整建小堆
    void AdjustUp(int* a, int child);
    //向下调整建小堆
    void AdjustDown(int* a, int n, int parent);
    //堆的初始化
    void HeapInit(Heap* p);
    //创建空堆
    Heap* HeapCreat(int n);
    //将数据x放入堆p中
    void HeapPush(Heap* p, int x);
    //删除堆的首元素
    void HeapPop(Heap* p);
    //判断堆是否为空
    bool HeapEmpty(Heap* p);
    //销毁堆
    void HeapDestory(Heap* p);

    具体实现代码如下：

    1. #include "Heap.h"
    2. void Swap(int* x, int* y) {
    3. 	int t = *x;
    4. 	*x = *y;
    5. 	*y = t;
    6. }
    7. //建立小堆的调整算法
    8. void AdjustUp(int* a, int child) {
    9. 	assert(a);
    10. 	int parent = (child - 1) / 2;
    11. 	while (parent >= 0) {
    12. 		if (a[parent] > a[child]) {
    13. 			Swap(a + parent, a + child);
    14. 			child = parent;
    15. 			parent = (child - 1) / 2;
    16. 		}
    17. 		if (a[parent] <= a[child]) {
    18. 			return;
    19. 		}
    20. 	}
    21. }
    22. //建立小堆的调整算法
    23. void AdjustDown(int* a, int n, int parent) {
    24. 	assert(a);
    25. 	int child = parent * 2 + 1;
    26. 	while (child < n) {
    27. 		if (child + 1 < n && a[child] > a[child + 1]) {
    28. 			child++;
    29. 		}
    30. 		if (a[child] < a[parent]) {
    31. 			Swap(a + child, a + parent);
    32. 			parent = child;
    33. 			child = parent * 2 + 1;
    34. 		}
    35. 		if (a[child] >= a[parent]) {
    36. 			return;
    37. 		}
    38. 	}
    39. }
    40. //初始化
    41. void HeapInit(Heap* p) {
    42. 	assert(p);
    43. 	p->a = 0;
    44. 	p->size = p->capacity = 0;
    45. }
    46. Heap* HeapCreat(int n) {
    47. 	Heap* p = (Heap*)malloc(sizeof(Heap));
    48. 	HeapInit(p);
    49. 	p->a = (int*)malloc(sizeof(int) * n);
    50. 	p->capacity = n;
    51. 	memset(p->a, 0, sizeof(int) * n);
    52. 	return p;
    53. }
    54. void HeapPush(Heap* p, int x) {
    55. 	assert(p);
    56. 	//当数据满了之后要扩容
    57. 	if (p->size == p->capacity) {
    58. 		p->a = (int*)realloc(p->a, sizeof(int) * p->capacity * 2);
    59. 		p->capacity *= 2;
    60. 	}
    61. 	p->a[p->size++] = x;
    62. 	//加入数据后要将其向上调整，保证加入数据后还是小堆
    63. 	AdjustUp(p->a, p->size - 1);
    64. }
    65. void HeapPop(Heap* p) {
    66. 	assert(p);
    67. 	if (!p->size) {
    68. 		return;
    69. 	}
    70. 	//将开头元素与末尾交换，然后再删除末尾元素就相当删除开头元素了
    71. 	Swap(p->a, p->a + p->size - 1);
    72. 	p->size--;
    73. 	//删除后左右孩子仍是堆结构，这时只需将其元素向下调整即可
    74. 	AdjustDown(p->a, p->size, 0);
    75. }
    76. void HeapPrint(Heap* p) {
    77. 	assert(p);
    78. 	for (int i = 0; i < p->size; i++) {
    79. 		fprintf(stdout, "%d ", p->a[i]);
    80. 	}
    81. 	puts("");
    82. }
    83. bool HeapEmpty(Heap* p) {
    84. 	assert(p);
    85. 	return p->size == 0;
    86. }
    87. void HeapDestory(Heap* p) {
    88. 	free(p->a);
    89. 	free(p);
    90. }
    91. int main() {
    92. 	//创建拥有4个元素的空堆
    93. 	Heap* p = HeapCreat(4);
    94. 	//将以下的数据加入小堆中
    95. 	for (int i = 2; i < 7; i++) {
    96. 		HeapPush(p, i - 1);
    97. 		HeapPush(p, i + 2);
    98. 	}
    99. 	//输出
    100. 	HeapPrint(p);
    101. 	return 0;
    102. }

    运行图：

            补：以上只是学习堆结构本身，而在堆的运用中，由于堆的效率很高，我们可利用堆结构来进行排序，即排序算法中的堆排序，后文将详细介绍。

  • 相关阅读:
    android开发工作笔记
    正统类加载器Tomcat(tomcat二探)
    热迁移中VirtIO-PCI设备的配置空间处理
    python+selenium的web自动化上传操作的实现
    自定义注解实现验证信息的功能
    保护香港服务器的方法
    Java-多线程基础及线程安全
    进程概念（跑路人笔记）
    最短路径之Dijkstra（迪杰斯特拉）路由算法C语言验证
    IRIS的镜像配置(1)
  • 原文地址：https://blog.csdn.net/m0_74246469/article/details/133185054