小工具知识网

当前位置: 首页 > 行业知识 > 【海贼王的数据航海:利用数据结构成为数据海洋的霸主】探究二叉树的奥秘

行业知识

【海贼王的数据航海:利用数据结构成为数据海洋的霸主】探究二叉树的奥秘

2026-11-16 10:11:57 来源:互联网转载

���录

1 -> 树的概念及结构

1.1 -> 树的概念

1.2 -> 树的相关概念

1.3 -> 树的表示

1.4 -> 树在实际中的运用(表示文件系统的目录树结构)

2 -> 二叉树概念及结构

2.1 -> 二叉树的概念

2.2 -> 现实中的二叉树

2.3 -> 特殊的二叉树

2.4 -> 二叉树的性质

2.5 -> 二叉树的存储结构

3 -> 二叉树的顺序结构及实现

3.1 -> 二叉树的顺序结构

3.2 -> 堆的概念及结构

3.3 -> 堆的实现

3.3.1 -> 堆向下调整算法

3.3.2 -> 堆的创建

3.3.3 -> 建堆的时间复杂度

3.3.4 -> 堆的插入

3.3.5 -> 堆的删除

3.3.6 -> 堆的代码实现

Heap.h

Heap.c

3.4 -> 堆的应用

3.4.1 -> 堆排序

4 -> 二叉树链式结构的实现

4.1 -> 前置说明

4.2 -> 二叉树的遍历

4.2.1 -> 前序、中序和后序遍历

 4.3 -> 节点个数以及高度


1 -> 树的概念及结构

1.1 -> 树的概念

树是一种非线性的数据结构,它是由n(n >= 0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,叶朝下。

  • 有一个特殊的结点,称为根结点,根结点没有前驱结点。
  • 除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、……、Tn,其中每一个集合Ti(1 0)棵互不相交的树的集合称为森林;

    1.3 -> 树的表示

    树结构相对线性表比较复杂,要存储表示起来比较麻烦,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式,如:双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。最常用的是孩子兄弟表示法。

    #include using namespace std;typedef int DataType;typedef struct Node{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域}Node;int main(){return 0;}

    1.4 -> 树在实际中的运用(表示文件系统的目录树结构)

    2 -> 二叉树概念及结构

    2.1 -> 二叉树的概念

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

    1. 或为空
    2. 由一个根结点加上两颗分别称为左子树和右子树的二叉树组成

    从上图可以看出:

    1. 二叉树不存在度大于2的结点
    2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

    注:

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

    2.2 -> 现实中的二叉树

    2.3 -> 特殊的二叉树

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

      2.4 -> 二叉树的性质

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

        2.5 -> 二叉树的存储结构

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

        1. 顺序存储:

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

        2. 链式存储:

        二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。
        #include using namespace std;typedef int BTDataType;// 二叉链struct BinaryTreeNode{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域};// 三叉链struct BinaryTreeNode{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域};

        3 -> 二叉树的顺序结构及实现

        3.1 -> 二叉树的顺序结构

        普通的二叉树不适合用数组存储,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中内存管理的一块区域分段。

        3.2 -> 堆的概念及结构

        如果有一个关键码的集合 ,把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:且(且) i = 0,1,2,……,则称为小堆(或大堆)。将根结点的最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。

        堆的性质:

        • 堆中某个结点的值总是不大于或不小于其父节点的值;
        • 堆总是一棵完全二叉树。

          3.3 -> 堆的实现

          3.3.1 -> 堆向下调整算法

          现在给出一个数组,逻辑上看做一棵完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

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

          3.3.2 -> 堆的创建

          int arr[] = {1,5,3,8,7,6};

          3.3.3 -> 建堆的时间复杂度

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

          因此:建堆的时间复杂度为O(N).

          3.3.4 -> 堆的插入

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

          3.3.5 -> 堆的删除

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

          3.3.6 -> 堆的代码实现

          Heap.h
          #pragma once#define  _CRT_SECURE_NO_WARNINGS 1#include #include #include #include typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;// 堆的初始化void HeapInit(HP* php);// 堆的销毁void HeapDestory(HP* php);// 堆的向上调整void AdjustUp(HPDataType* a, int child);// 堆的向下调整void AdjustDown(HPDataType* a, int child);// 堆的插入void HeapPush(HP* php, HPDataType x);// 堆的删除void HeapPop(HP* php);// 取堆顶的数据HPDataType HeapTop(HP* php);// 堆的数据个数int HeapSize(HP* php);// 堆的判空bool HeapEmpty(HP* php);
          Heap.c
          #include "Heap.h"// 堆的初始化void HeapInit(HP* php){assert(php);php->a = NULL;php->size = 0;php->capacity = 0;}// 堆的销毁void HeapDestory(HP* php){assert(php);free(php->a);php->a = NULL;php->capacity = php->capacity = 0;}void Swap(HPDataType* p1, HPDataType* p2){HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}// 堆的向上调整void AdjustUp(HPDataType* a, int child){int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}// 堆的向下调整void AdjustDown(HPDataType* a, int child){int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustDwon(php->a, php->size - 1);}// 堆的删除void HeapPop(HP* php){assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);}// 取堆顶的数据HPDataType HeapTop(HP* php){assert(php);assert(!HeapEmpty(php));return php->a[0];}// 堆的数据个数int HeapSize(HP* php){assert(php);return php->size;}// 堆的判空bool HeapEmpty(HP* php){assert(php);return php->size == 0;}

          3.4 -> 堆的应用

          3.4.1 -> 堆排序

          堆排序即利用堆的思想来进行排序,总共分两个步骤:

          1. 建堆

          • 升序:建大堆
          • 降序:建小堆

            2. 利用堆删除思想来进行排序

            建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。

            4 -> 二叉树链式结构的实现

            4.1 -> 前置说明

            手动快速创建简单的二叉树:

            typedef int BTDataType;typedef struct BinaryTreeNode{ BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right;}BTNode;BTNode* CreatBinaryTree(){ BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6);  node1->_left = node2; node1->_right = node4; node2->_left = node3; node4->_left = node5; node4->_right = node6; return node1;}

            注:

            上述代码并不是创建二叉树的方式。

            4.2 -> 二叉树的遍历

            4.2.1 -> 前序、中序和后序遍历

            学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

            按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

            1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
            2. 中序遍历((Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
            3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
            由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 前序遍历:
            void PrevOrder(BTNode* root){if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);}

            中序遍历:

            void InOrder(BTNode* root){if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);}

            后序遍历:

            void PostOrder(BTNode* root){if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}

            4.2.2 -> 层序遍历

            层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

            层序遍历:

            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);if (front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);}

             4.3 -> 节点个数以及高度

            // 求节点的个数int BTreeSize(BTNode* root){/*if (root == NULL)return 0;return BTreeSize(root->left)+ BTreeSize(root->right)+ 1;*/return root == NULL ? 0 : BTreeSize(root->left)+ BTreeSize(root->right) + 1;}// 求叶子节点的个数int BTreeLeafSize(BTNode* root){if (root == NULL){return 0;}if (root->left == NULL&& root->right == NULL){return 1;}return BTreeLeafSize(root->left)+ BTreeLeafSize(root->right);}// 求二叉树的高度int BTreeHeight(BTNode* root){if (root == NULL)return 0;int leftHeight = BTreeHeight(root->left);int rightHeight = BTreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}// 二叉树第k层结点个数int BTreeLevelKSize(BTNode* root, int k){assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return BTreeLevelKSize(root->left, k - 1)+ BTreeLevelKSize(root->right, k - 1);}// 二叉树查找值为x的结点BTNode* BTreeFind(BTNode* root, BTDataType x){if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = BTreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = BTreeFind(root->right, x);if (ret2)return ret2;return NULL;}

            感谢各位大佬支持!!!

            大佬们互三啦!!!

上一篇:田鸡下载攻略,轻松获取,步骤详解!

下一篇:麦块怎么换服务器皮肤?