2345游戏盒子_寓意八方来财的公司名字_站长全网指数查询_百度查看订单

🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏⭐评论✍️

1. 树的相关概念

1.1 树的概念

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

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

1.2 树的相关概念

• 结点的度：一个结点含有的子树的个数称为该结点的度；
• 叶结点或终端结点：度为0的结点称为叶结点；
• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
• 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
• 兄弟结点：具有相同父结点的结点互称为兄弟结点；
• 树的度：一棵树中，最大的结点的度称为树的度；
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
• 树的高度或深度：树中结点的最大层次；
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟；
• 结点的祖先：从根到该结点所经分支上的所有结点；
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。

1.3 树的表示

这里先提一嘴，对于一般的树我们可以用结点来实现。我们先了解其表示方法，后面再做说明。

我们可以用孩子兄弟表示法：（这样以后就可以每一个都遍历到了）

typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};

2. 二叉树

2.1 二叉树的概念

二叉树即每个节点最多有两个子结点（度最多为2）

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

2.2 特殊的二叉树

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

2.3 二叉树的性质

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

3. 堆的实现

3.1 堆的概念

对于一般的二叉树，我们不能用数组来存储，因为会造成空间的大量浪费。但是对于完全二叉树除外，反而完全二叉树非常适合用数组来存储。

堆也是一种完全二叉树，根据双亲与孩子的大小关系可以分为大堆和小堆。

• 大堆：任何一个父亲结点都大于其子结点
• 小堆：任何一个父亲结点都小于其子结点
  

3.2 堆的代码实现

• 堆的结构：

typedef int DataType;typedef struct heap
{DataType* arr;int size;int capacity;
}HP;

我们看到堆是用顺序表来实现的，但实际上堆并不是线性结构；我们用顺序表来表示堆后，堆的逻辑结构是不连续的，但是堆的物理结构是连续的 ；利用父节点与子结点的下标的关系我们就可以处理相关的插入和删除问题

• 堆的初始化：

void HPInit(HP* hp)
{hp->arr = (DataType*)malloc(4 * sizeof(DataType));hp->capacity = 4;hp->size = 0;
}

• 堆的插入（涉及向上调整算法）：

void swap(DataType* x, DataType* y)
{DataType t;t = *x;*x = *y;*y = t;
}void AdjustUp(DataType* arr, int size)
{int child = size - 1;int parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]) //大堆{swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HPPush(HP* hp, DataType x)
{if (hp->size == hp->capacity){DataType* tmp = (DataType*)realloc(hp->arr, 2 * hp->capacity * sizeof(DataType));if (!tmp){perror("malloc:");exit(1);}hp->arr = tmp;hp->capacity *= 2;}//开始先在最后插入，但是此时不一定符合堆结构hp->arr[hp->size++] = x;//利用向上调整算法进行调整,也就是判断父节点和子结点的大小关系AdjustUp(hp->arr, hp->size);
}

• 堆的删除（涉及向下调整算法）：

/向下调整算法的前提是子树已经满足了堆结构，只有父节点不满足
void AdjustDown(DataType* arr, int size)
{int parent = 0;int child = parent * 2 + 1;//假设左子树最小while (child < size){if (child + 1 < size && arr[child] < arr[child + 1]){child++;}if (arr[parent] < arr[child]){swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HPPop(HP* hp)  //对于堆来说，一般删除的是根节点的数据
{//首先交换数组中第一个和最后一个元素，将根节点放到最后swap(&hp->arr[0], &hp->arr[hp->size - 1]);//删掉最后一个元素也就是根节点，但是这个时候结构不一定满足堆结构hp->size--;//向下调整算法AdjustDown(hp->arr, hp->size);
}

• 获取堆的根节点以及判空

DataType HPTop(HP* hp)
{assert(hp->size);return hp->arr[0];
}int HPEmpty(HP* hp)
{return hp->size == 0;
}

由于堆的根节点一定是最大的或者是最小的，所以我们可以利用这个特点实现排序（但是一般不这么麻烦，因为这样还要先实现堆的结构和方法，只要利用向上向下调整就行了）

4. 堆排序

首先将已知的数组建堆，有两种方法：

1. 向上调整建堆：

//首先使数组满足堆的特点
//方法一：利用向上调整建堆
int i;
for (i = 1; i < size; i++)
{AdjustUp(arr, i);
}

这个主要是模拟堆Push

2. 向下调整建堆：

//方法二：利用向下调整建堆
int i;
for (i = (size - 1) / 2; i >= 0; i--)
{AdjustDown2(arr, size, i);
}

由于向下调整需要子树满足堆的条件，所以我们从第一个非叶子结点开始建堆。

• 模拟堆删除，进行排序

//模拟堆的PoP特点，进行排序
//降序建小堆  升序建大堆
while (size)
{swap(&arr[0], &arr[size - 1]);size--;AdjustDown(arr, size);
}

需要注意的是，升序我们需要建大堆，一次将根节点（最大）换到最后；降序我们需要建小堆