• 二叉树详解

    目录

    一、树

    1.树的概念

    2.树与非树的判断

    3.树的表示方法

    二、二叉树

    1.概念及结构

    2.二叉树的实现方法

    三、堆

    1.堆的概念

    2.堆的实现

    3.堆排序

    四、链式二叉树的实现

    1.链式二叉树的概念

    2.前序遍历

    3.中序遍历与后序遍历

    4.层序遍历

    一、树

    1.树的概念

    树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。

    把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

    有一个特殊的结点，称为根结点，根节点没有前驱结点除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(0<=i<=m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继因此，树是递归定义的。

    注意，不含数据的空树也是树，用空集表示

    2.树与非树的判断

    （1）基本概念

    • 节点的度：一个节点含有的子树的个数称为该节点的度。
    • 叶子节点或终端节点：度为0的节点称为叶节点。比如B、C、H、I...等节点为叶节点非终端节点或分支节点度不为0的节点
    • ，比如图中D、E、F、G...等节点为分支节点。
    • 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。（有些人认为叫父节点忽视女性就搞了个双亲结点，不管怎么样支持男女平等，抵制田园女权）例如，A是B的父节点。
    • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。例如，B是A的子节点。
    • 兄弟节点：具有相同父节点的节点互称为兄弟节点。如图，B、C是兄弟节点。
    • 度：一棵树中，最大的节点的度称为树的度。如图：树的度为2.
    • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推……
    • 树的高度或深度：树中节点的最大层次。如图，树的高度为4.
    • 堂兄弟节点：双亲在同一层的节点互为堂兄弟。如图，H、I互为兄弟节点。
    • 节点的祖先：从根到该节点所经分支上的所有节点。比如，A是所有节点的祖先。
    • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。
    • 森林：由m（m>0）棵互不相交的树的集合称为森林。

    突然想起了过年时，你爸妈让你给不认识的亲戚拜年，挨个叫人的场景……

    （2）判断方法

    • 子树是不相交的
    • 除根节点外，每个节点只有一个父节点
    • 一棵有N个节点的树有N-1条边

    3.树的表示方法

    我们上面图中的树都是简单的二叉树，一个树的度可以有很多，那么如何表示所有的树呢？兄弟表示法，给我们找到了出路。

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

    通过树的根节点向下寻找大儿子直到需要的一代，每一代的大儿子又连接着这一代其他兄弟，这样就可以做到对树的不同度的节点的定义。

    二、二叉树

    1.概念及结构

    （1）概念：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

    特点：

    • 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
    • 二叉树的子树有左右之分，其子树的次序不能颠倒。

    （2）特殊的二叉树：

    • 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
    • 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

    注意，完全二叉树必须最多只有最后一层不满

    2.二叉树的实现方法

    二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。在这里我们首先使用顺序结构，也就是通过数组实现二叉树；然后通过链表的模式实现二叉树。

    顺序结构二叉树的性质：

    • 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。
    • 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
    • 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1.
    • 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (Log2(n+1)是log以2为底，n+1为对数)
    • 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：若i>0，i位置节点的双亲序号为(i-1)/2；i=0，i为根节点编号，无父节点；若2i+1，左孩子序号：2i+1，2i+1>=n否则无左孩子；若2i+2，右孩子序号：2i+2，2i+2>=n否则无右孩子。

    三、堆

    1.堆的概念

    普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储，这种顺序的二叉树最具有代表性的数据结构就是堆。

    我们引入堆的概念：

    如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki i+1 且 Kii+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。

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

    将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

    堆的性质：堆中某个节点的值总是不大于或不小于其父节点的值，堆总是一棵完全二叉树。

    2.堆的实现

    注意，我们这里建堆建的是大根堆

    （1）初始化

    void HeapInit(HP* php);

    单纯的顺序表初始化（确信）

    1. void HeapInit(HP* php)
    2. {
    3.     assert(php);
    4.     php->capacity = 0;
    5.     php->size = 0;
    6.     php->a = NULL;
    7. }

    （2）打印堆元素

    void HeapPrint(HP* php);

    单纯的顺序表打印（确信）

    1. void HeapPrint(HP* php)
    2. {
    3.     assert(php);
    4.     int i = 0;
    5.     for (i = 0; i < php->size; i++)
    6.     {
    7.         printf("%d ", php->a[i]);
    8.     }
    9.     printf("\n");
    10. }

    （3）交换元素

    void Swap(HPDataType* p1, HPDataType* p2);

    在许多函数中需要交换不同位置的数据，我们写一个函数

    1. void Swap(HPDataType* p1, HPDataType* p2)
    2. {
    3.     assert(p1 && p2);
    4.     HPDataType temp;
    5.     temp = *p1;
    6.     *p1 = *p2;
    7.     *p2 = temp;
    8. }

    （4）向上调整

    void AdjustUp(HPDataType* a, int child);

    我们在向堆中插入数据时会遇到父节点数据小于子节点的情况，那我们就需要让这个元素与父节点进行比较，如果父节点小于子节点就交换这两个元素，直到父节点大于或等于子节点就停止交换。

    1. void AdjustUp(HPDataType* a, int child)
    2. {
    3.     assert(a);
    4.     int parent = (child-1)/2;
    5.     while(parent>0)
    6.     {
    7.         if(a[parent]
    8.         {
    9.             swap(&a[parent],&a[child]);
    10.             child = parent;
    11.             parent = (child-1)/2;
    12.         }
    13.         else
    14.             break;
    15.     }
    16. }

    （5）插入元素

    void HeapPush(HP* php, HPDataType x);

    首先和顺序表一样插入元素，然后对这个元素与父节点进行比较，交换位置至对应位置处。

    堆的建立只需要多次插入数据即可。

    1. void AdjustDown(HPDataType* a, int n, int parent)
    2. {
    3.     assert(a);
    4.     int need_child = parent*2+1;
    5.     while(need_child//节点的下标一定在有效数据范围内
    6.     {
    7.         if(a[need_child]1] && need_child+1//比较左孩子和右孩子哪一个最大，大的作为交换的对象
    8.             need_child++;
    9.         if(a[need_child]>a[parent])
    10.         {
    11.             swap(&a[need_child],&a[parent]);
    12.             parent = need_child;
    13.             need_child = parent*2+1;        
    14.         }
    15.         else
    16.             break;            
    17.     }
    18. }

    （6）向下调整

    void AdjustDown(HPDataType* a, int n, int parent);

    我们在删除元素的时候会遇到数据父节点小于子节点的情况，此时我们就需要将这个节点向下调整到对应位置。

    1. //向堆中插入数据
    2. void HeapPush(HP* php, HPDataType x)
    3. {
    4.     assert(php);
    5.     if (php->capacity == php->size)
    6.     {
    7.         int newcapacity = (php->capacity == 0 ? 4 : 2 * php->capacity);
    8.         HPDataType* p1 = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
    9.         if (p1 == NULL)
    10.         {
    11.             perror("realloc fail");
    12.             return;
    13.         }
    14.         php->a = p1;
    15.     }
    16.     php->a[php->size] = x;
    17.     php->size++;
    18.     AdjustUp(php->a, php->size - 1);
    19. }

    （7）删除数据

    void HeapPop(HP* php);

    堆的元素删除一般都是删除堆顶的头节点。所以，我们首先将末位元素与首元素交换。然后，有效数据的个数减一，让堆不能管理那块空间。最后，将堆顶的元素换到想订的位置。

    1. // 删除堆顶元素
    2. void HeapPop(HP* php)
    3. {
    4.     assert(php);
    5.     Swap(&php->a[0], &php->a[php->size - 1]);
    6.     php->size--;
    7.     AdjustDown(php->a, php->size, 0);
    8. }

    （8）返回堆顶元素

    HPDataType HeapTop(HP* php);

    直接返回数组第一个元素。

    1. // 返回堆顶的元素
    2. HPDataType HeapTop(HP* php)
    3. {
    4.     assert(php);
    5.     return php->a[0];
    6. }

    （9）判断堆是否为空

    bool HeapEmpty(HP* php);

    看size为不为0

    1. bool HeapEmpty(HP* php)
    2. {
    3.     assert(php);
    4.     return php->size == 0;
    5. }

    （10）堆的大小

    int HeapSize(HP* php);

    返回size

    1. int HeapSize(HP* php)
    2. {
    3.     assert(php);
    4.     return php->size;
    5. }

    （11）堆的销毁

    void HeapDestroy(HP* php);

    老步骤，数据个数变零，释放空间，指针置空

    1. void HeapDestroy(HP* php)
    2. {
    3.     assert(php);
    4.     php->capacity = 0;
    5.     php->size = 0;
    6.     php->a = NULL;
    7.     free(php->a);
    8. }

    3.堆排序

    堆排序是一个效率十分高的排序算法，它真的可以说吊打我们学过的冒泡排序，下面介绍一下堆排序的步骤：

    （1）建立大堆

    你可能会想，为什么不建小堆呢？小堆可以让数组更加有序。

    其实不然，小堆确实可以确定头节点为最小值，数组也相对有序。但是，你无法找到次小元素，因为小堆只保证父节点小于子节点，但是你无法判断左右子节点数据的大小。所以，我们通过建立大堆就一定可以在头节点找到最大的元素。

    （2）交换首尾元素并让堆的有效数据减一

    大堆的头节点一定是最大的元素，那么我们交换最大的数据到最后，它也就在了它最终该在的位置。然后有效数据减一，让整个堆不再管辖最后的这个正确位置的数据。

    （3）重新建堆

    并不是把整个堆清空，而是将你交换到头节点的元素向下调整构成新的堆。

    （4）重复上述步骤直到堆中不存在元素即可

    整体思路就是删除数据的变形

     （5）代码实现

    1. void HeapSort(int* a, int n)
    2. {
    3.     HP s;
    4.     HP* p = &s;
    5.     HeapInit(p);
    6.     int i = 0;
    7.     for (i = 0; i < n; i++)//通过一个一个插入数据来建堆
    8.     {
    9.         HeapPush(p, a[i]);
    10.     }
    11.     for (i = 0; i < p->size; i++)
    12.     {
    13.         Swap(&p->a[0], &p->a[p->size - 1 - i]);//交换首元素和尾元素
    14.         AdjustDown(p->a, p->size - i - 1, 0);//将首元素向下调整
    15.     }
    16.     for (i = 0; i < n; i++)//将堆数组中的所有数据传回给原数组
    17.     {
    18.         a[i] = p->a[i];
    19.     }
    20.     HeapDestroy(p);
    21. }

    四、链式二叉树的实现

    1.链式二叉树的概念

    类似于双向带头循环链表，二叉树每一个节点是由一个left指针，一个right指针还有一个有效数据组成的一个结构体。

    其中左指针指向它左子树的头节点（子树可以为空），右指针指向它右子树的头节点，数据储存在有效数据内。这样一层一层地向下构建就形成了二叉树。

    不管如何，我们先建立起下面这个树

    1. //构建二叉树
    2. BTNode* BinaryTreeCreate()
    3. {
    4.     BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    5.     BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
    6.     BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    7.     BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    8.     BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    9.     BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
    10.     BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
    11.  
    12.     n1->data = 1;
    13.     n2->data = 2;
    14.     n3->data = 3;
    15.     n4->data = 4;
    16.     n5->data = 5;
    17.     n6->data = 6;
    18.     n7->data = 7;
    19.  
    20.     n1->left = n2;
    21.     n1->right = n4;
    22.     n2->left = n3;
    23.     n2->right = NULL;
    24.     n3->left = NULL;
    25.     n3->right = NULL;
    26.     n4->left = n5;
    27.     n4->right = n6;
    28.     n5->left = NULL;
    29.     n5->right = NULL;
    30.     n6->left = n7;
    31.     n6->right = NULL;
    32.     n7->left = NULL;
    33.     n7->right = NULL;
    34.     
    35.     return n1;
    36.  
    37. }

    2.前序遍历

    前序遍历是指我们在访问一棵二叉树的时候先访问根节点数据，后访问左子树，最后访问右子树，当左右子树为空树的时候就返回前面的节点。

    对于上面的二叉树，我们对它进行前序遍历

    有些人可能已经学过了前序遍历，但是前对于空树的遍历那部分依旧模糊，我们可以通过遇到空树打印的方式更加熟悉前序遍历。

    代码实现：

    1. //二叉树前序遍历
    2. void TreePrevOrder(BTNode* root)
    3. {
    4.     //空树返回
    5.     if (root == NULL)
    6.     {
    7.         printf("NULL ");//可以注释掉，打印是为了更好理解前序遍历
    8.         return;
    9.     }
    10.     //根
    11.     printf("%d ", root->data);
    12.     //左子树
    13.     TreePrevOrder(root->left);
    14.     //右子树
    15.     TreePrevOrder(root->right);
    16. }

    3.中序遍历与后序遍历

    所谓的前中后序遍历就是指访问节点数据的顺序在前在中还是在后，这三个遍历二叉树的方式都要使用递归。

    根据前序遍历的思想可知，中序遍历会先遍历左子树，然后读取根节点，最后遍历右子树；后序遍历会先遍历左子树，然后遍历右子树，最后读取根节点。

    所以对于上面的这个树而言，遍历的结果如下（控制遇到NULL也打印）：

    前序遍历：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 7 NULL NULL NULL
    中序遍历：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 7 NULL 6 NULL
    后序遍历：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 7 NULL 6 4 1

    代码实现：

    1. //二叉树中序遍历
    2. void TreeInOrder(BTNode* root)
    3. {
    4. //空树返回
    5. if (root == NULL)
    6. {
    7. printf("NULL ");
    8. return;
    9. }
    10. //左子树
    11. TreeInOrder(root->left);
    12. //根
    13. printf("%d ", root->data);
    14. //右子树
    15. TreeInOrder(root->right);
    16. }
    17.  
    18.  
    19. //二叉树后序遍历
    20. void TreePostOrder(BTNode* root)
    21. {
    22. //空树返回
    23. if (root == NULL)
    24. {
    25. printf("NULL ");
    26. return;
    27. }
    28. //左子树
    29. TreePostOrder(root->left);
    30. //右子树
    31. TreePostOrder(root->right);
    32. //根
    33. printf("%d ", root->data);
    34. }

    4.层序遍历

    层序遍历，顾名思义就是一层一层遍历元素，它是二叉树遍历中一种不需要递归的方式，它可以解决递归过深栈溢出的问题。

    层序遍历需要用到栈，大致思路就是当我们遍历完根节点后先出栈该节点，然后入栈左子树和右子树的根节点，当左右子树为空树时就不再入栈。

    打印完上一层的一个节点就入栈下面的两个节点，由于栈先入先出的特点，各个节点会逐个打印。这一层的所有节点打印完成或，下一层的节点也已经全部入栈，重复这样的步骤即可完成层序遍历。

    1. //层序遍历
    2. void TreeLevelOrder(BTNode* root)
    3. {
    4.     queue pq;
    5.     queue* p = &pq;
    6.     initqueue(p);
    7.     if (root)
    8.     queuepush(p, root);
    9.     while (!QueueEmpty(p))
    10.     {
    11.         BTNode* front = queuefront(p);//另外保存一份地址
    12.         queuepop(p);//出队列的是该节点的地址的数据，原来二叉树的那个节点依旧存在
    13.         printf("%d ", front->data);//打印该节点
    14.         if (front->left)
    15.             queuepush(p, front->left);//入栈左节点
    16.         if (front->right)
    17.             queuepush(p, front->right);//入栈右节点
    18.     }
    19.     destory(p);
    20. }
  • 相关阅读:
    IntelliJ IDEA 打开近期工作的项目的对话框的快捷键
    尚硅谷大数据项目《在线教育之离线数仓》笔记007
    Alvaria宣布客户体验行业资深人士Jeff Cotten担任新首席执行官
    【附源码】计算机毕业设计SSM万达影院售票管理系统
    2022-07-18 jenkins部署
    卷积神经网络原理及其C++/Opencv实现(2)
    Mybatis使用
    Redis的持久化机制
    五金零售批发商城小程序的作用是什么
    git工具下载和安装
  • 原文地址：https://blog.csdn.net/qq_65285898/article/details/126600208