1 关于树的重要定义
- 节点的高度=从下往上，节点到叶子结点的最长路径（边数）。所以叶子结点高度为1
- 节点的深度=从上往下，根节点到这个节点所经历的边数。所以根节点深度为0
- 节点的层数（层次）=节点深度+1。根节点在1层。（这个地方有时候要看题目的定义的，不绝对）
- 树的高度=根节点的高度
- 树的深度=树的高度
image.png
普通的树用儿子兄弟表示法后，再向右旋转45度，就可以看到一颗二叉树了。
1.1 分类
- 斜二叉树 skewed Binary Tree
- 完美二叉树，满二叉树 Perfect Binary Tree, Full Binary Tree, 除了叶子节点外，每个节点都有左右两个子节点
- 完全二叉树 Complete Binary Tree，n个节点从上到下，从左至右编号后，与满二叉树中相同编号的节点位置相同
斜二叉树和完美二叉树
完全二叉树
1.2 二叉树的重要性质
- 对于n个结点的树（不一定是二叉树），一定有n-1条边
- 第i层( i>=1)的最大结点数是2^(i-1)
- k层(k>=1)的二叉树最大结点总数2^k-1
- 对于任何非空二叉树T，若n0表示叶子结点的个数，n2表示度为2的非叶节点个数，那么满足关系n0=n2+1
2 二叉树的表示和基本操作
表示与存储：
二叉树可以使用数组或者链表进行表示。
一般情况下，对于完全二叉树我们使用数组，其他类型使用链表。因为斜二叉树使用数组表示会浪费大量空间，k层的斜二叉树需要2^k数组空间。
基本操作：
- 创建二叉树
- 判断是否为空
- 前序遍历（DFS）
- 中序遍历（DFS）
- 后序遍历（DFS）
- 层序遍历（BFS）
遍历二叉树的应用：
- 输出二叉树的所有叶子结点
- 求树的高度
- 二元运算表达式树及其遍历
- 根据某两种遍历，确定一颗二叉树
- 树的同构判别
2.1 数组存储完全二叉树
数组顺序存储
注意：
- 从数组下标为1的位置开始存储（如果从0开始排序，左右子树的下标位置都要加1）
- 在数组中的顺序直接就是“层序遍历”的顺序，从上至下，从左至右
- 判断数组中某个结点（下标为k）是否为叶子结点的标志：2*k>N , N为结点总数
- 判断断数组中某个结点（下标为k）是否为空结点的标志：k>N , N为结点总数
04-树6 Complete Binary Search Tree (30分)
给定N (≤1000)个非负整数，创建一个完全二叉树形式的搜索树，输出层序遍历结果。
输入样例：
10
1 2 3 4 5 6 7 8 9 0
输出样例：
6 3 8 1 5 7 9 0 2 4
结题报告：
要求是完全二叉树，那么直接考虑用数组，而且数组从左到右就是层序遍历的顺序。
输入数据不一定有序，需要先排序。
这道题有两种解法，首先是陈越姥姥视频中的解法，根据完全二叉树的性质，递归地找到该有序数组中属于搜索树中点的那个点，依次放入结果序列中。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
vector<int> Arr; // 输入数据
int T[1001]; // 二叉搜索树数组，从1开始
// 计算n个结点的完全二叉树左边有多少个结点
int getLeftLength(int n){
// n 为结点总数，X为最后一层叶子节点总数
// 2^H -1 +X = n
int H = log2(n+1);
int X = n+1-pow(2,H);
int maxLeaf = pow(2,H-1);
int leftx = (X<maxLeaf)? X: maxLeaf;
int L = pow(2,H-1)-1+leftx;
return L;
}
void solve(int ALeft, int ARight, int TRoot){
int n = ARight - ALeft +1;
if (n==0){
return;
}
int L = getLeftLength(n); // 左子树有L个结点
T[TRoot] = Arr[ALeft+L];
int LeftRoot = TRoot*2;
int RightRoot = LeftRoot+1;
solve(ALeft, ALeft+L-1, LeftRoot);
solve(ALeft+L+1, ARight, RightRoot);
}
int main() {
int N = 0;
scanf("%d", &N);
for (int i=0; i<N;i++){
int curr = 0;
scanf("%d", &curr);
Arr.push_back(curr);
}
sort(Arr.begin(), Arr.end());
solve(0, Arr.size()-1, 1);
printf("%d", T[1]);
for (int i=2; i<=N;i++){
printf(" %d", T[i]);
}
return 0;
}
}
方法2更加巧妙，其实输入数据排序后，从左到右是完全二叉树的中序遍历。所以问题转化成通过完全二叉树的中序遍历得到层序遍历。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
int N = 0;
int indexArr = 0;
vector<int> Arr;
int T[1001]; // 从1开始排序
void inOrder(int root){
if (root >N){
return;
}
int left = root*2;
int right = left + 1;
inOrder(left);
T[root] = Arr[indexArr++];
inOrder(right);
}
int main() {
scanf("%d", &N);
for (int i=0; i<N;i++){
int curr = 0;
scanf("%d", &curr);
Arr.push_back(curr);
}
sort(Arr.begin(), Arr.end());
inOrder(1);
printf("%d", T[1]);
for (int i=2; i<=N;i++){
printf(" %d", T[i]);
}
return 0;
}
2.2 链表表示的二叉树
链表存储
先序、中序、后序三种遍历的过程，经历的结点的路线是一样的，只是访问结点的时机不同。每个结点都有3次碰到的机会，先序是在第一次碰到该结点的时候就访问，中序是第二次，后续是第三次。
三种遍历的关联性
递归方式进行的3种遍历
// 前序遍历
void PreorderTraversal( BinTree BT )
{
if( BT ) {
printf("%d ", BT->Data );
PreorderTraversal( BT->Left );
PreorderTraversal( BT->Right );
}
}
// 中序遍历
void InorderTraversal( BinTree BT )
{
if( BT ) {
InorderTraversal( BT->Left );
/* 此处假设对BT结点的访问就是打印数据 */
printf("%d ", BT->Data); /* 假设数据为整型 */
InorderTraversal( BT->Right );
}
}
// 后序遍历
void PostorderTraversal( BinTree BT )
{
if( BT ) {
PostorderTraversal( BT->Left );
PostorderTraversal( BT->Right );
printf("%d ", BT->Data);
}
}
非递归方式表示3种遍历
先序、中序、后序遍历的非递归方法需要借助栈，其实可以理解为深度优先搜索
// 先序遍历
void PreorderTraversal( BinTree BT ){
BinTree T = BT;
stack<BinTree> S;
while (T || !S.empty()){
while (T){
S.push(T);
printf("%d ", T->Data);
T = T->Left;
}
if (!S.empty()){
T = S.top();
S.pop();
T = T->Right;
}
}
}
// 中序遍历
void InorderTraversal( BinTree BT ){
BinTree T = BT;
stack<BinTree> S;
while (T || !S.empty()){
while (T){
S.push(T);
T = T->Left;
}
if (!S.empty()){
T = S.top();
S.pop();
printf("%d ", T->Data);
T = T->Right;
}
}
}
// 后序遍历
// 使用两个栈，s和s2。使用 【根->右->左】 的方式，在第一次遇到结点时，就压入栈s2中，那么最后遍历完了，根据栈的性质，s2依次弹出的就是【左->右->根】的后续遍历了
void PostorderTraversal( BinTree BT ){
BinTree T = BT;
stack<BinTree> s;
stack<ElementType> s2;
while (T || !s.empty()){
while (T){
s.push(T);
s2.push(T->Data);
T = T->Right;
}
if (!s.empty()){
T = s.top();
s.pop();
T = T->Left;
}
}
while (!sr.empty()){
printf("%5d", s2.top());
s2.pop();
}
}
层次遍历
层次遍历需要借助队列，其实可以理解为广度优先搜索。
void LevelorderTraversal( BinTree BT ){
queue<BinTree> Q;
BinTree T;
if (!BT) return;
Q.push(BT);
while (Q.empty() == false){
T = Q.front();
Q.pop();
printf("%d ", T->Data);
if (T->Left){
Q.push(T->Left);
}
if (T->Right){
Q.push(T->Right);
}
}
}
- 这道题注意对于每层节点的处理
习题：二叉树的序列化和反序列化
- 这道题可以用先序遍历或者层序遍历实现
2.3 不需要创建树而得到遍历的方法
03-树3 Tree Traversals Again (25分)
根据题目描述的中序遍历中stack相关操作，输出树的后序遍历。
输入样例：
第一个正整数N(N<=30)表示结点个数
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
输出样例：
3 4 2 6 5 1
解题报告
这道题push操作的顺序其实是树的前序遍历：
1 2 3 4 5 6
而pop操作对应的是树的中序遍历：
3 2 4 1 6 5
也就是说不需要创建树，我们可以根据前序遍历数组和中序遍历数组，直接求得后续遍历数组。
核心算法
#include <stdio.h>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
vector<int> preOarr;
vector<int> inOarr;
int postVector[31];
// preL: 前序遍历数组最左元素下标
// inL: 中序遍历数组最左元素下标
// postL: 后序遍历数组最左元素下标
// n: 当前处理的元素个数
void solve(int preL, int inL, int postL, int n){
if (n==0){
return;
}
if (n==1){
postVector[postL] = preOarr[preL];
}
int root = preOarr[preL];
postVector[postL+n-1] = root;
// 获取root在中序遍历中的下标位置i
int i=0;
for (i=0;i<n;i++){
if (inOarr[inL+i] == root){
break;
}
}
int lenL = i; // 左边数组长度
int lenR = n-i-1; // 右边数组长度
solve(preL+1, inL, postL, lenL);
solve(preL+lenL+1,inL+lenL+1, postL+lenL, lenR);
}
int main() {
int N = 0;
scanf("%d", &N);
stack<int> s1;
for (int i=0; i<2*N;i++){
string str;
cin>>str;
if (str == "Push"){ // Push 2
int currNum = 0;
scanf("%d", &currNum);
preOarr.push_back(currNum);
s1.push(currNum);
} else { // Pop
if (!s1.empty()){
int topNum = s1.top();
s1.pop();
inOarr.push_back(topNum);
}
}
}
int preL = 0;
solve(0,0,0,N);
printf("%d", postVector[0]);
for (int i=1;i<N;i++){
printf(" %d", postVector[i]);
}
return 0;
}
这是最开始使用的方法，我仍然是使用了链表去存储了树结构了，虽然用在这里显得有点重了，但是可以作为“已知先序和中序遍历，构建二叉树”的例子记录在这里。
#include <stdio.h>
#include <stack>
#include <stdlib.h>
#include <string>
#include <vector>
#include <iostream>
#define ElementType int
using namespace std;
typedef struct TNode *BinTree;
struct TNode {
ElementType Data;
BinTree Left;
BinTree Right;
};
BinTree RootTree = NULL;
vector<ElementType> preOarr;
vector<ElementType> inOarr;
vector<ElementType> postVector;
// 当前先序遍历区间[preL, preR]
// 当前中序遍历区间[inL, inR]
BinTree CreateTree(int preL, int preR, int inL, int inR){
if (preL > preR){
return NULL;
}
TNode* RootTree = new TNode;
RootTree->Data = preOarr[preL];
int k = inL;
for (k=inL; k<=inR;k++){
if (inOarr[k] == RootTree->Data){
break;
}
}
int numleft = k - inL;
RootTree->Left = CreateTree(preL+1,preL+numleft,inL,k-1);
RootTree->Right = CreateTree(preL+numleft+1,preR,k+1,inR);
return RootTree;
}
void PostTravelsal(BinTree BT){
if (BT){
PostTravelsal(BT->Left);
PostTravelsal(BT->Right);
postVector.push_back(BT->Data);
}
}
int main() {
int N = 0;
scanf("%d", &N);
stack<ElementType> s1;
for (int i=0; i<2*N;i++){
string str;
cin>>str;
if (str == "Push"){ // Push 2
int currNum = 0;
scanf("%d", &currNum);
preOarr.push_back(currNum);
s1.push(currNum);
} else { // Pop
if (!s1.empty()){
int topNum = s1.top();
s1.pop();
inOarr.push_back(topNum);
}
}
}
RootTree = CreateTree(0,N-1,0,N-1);
PostTravelsal(RootTree);
printf("%d", postVector[0]);
for (int i=1;i<postVector.size();i++){
printf(" %d", postVector[i]);
}
return 0;
}
3 二叉搜索树BST
定义
二叉搜索树又叫二叉查找树
- 空树，或者：
- 其左子树和右子树也是二叉搜索树
- 左子树的所有结点都小于等于根节点
- 右子树的所有结点都大于根节点
二叉搜索树的基本操作
- 建树
- 查找
- 插入
- 删除
其中最麻烦的操作是删除。删除要保证操作结束后仍然是一颗二叉搜索树。如下图要删除结点5，那么找到比5大的最小元素6（右子树的最小值），覆盖结点5， 由于6是最小元素，肯定没有左子树，结点6原来的位置最多有右子树，提上来。
删除结点5
二叉搜索树性质
- 二叉搜索树的中序遍历是有序递增的
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
void PreorderTraversal( BinTree BT );
void InorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
int main()
{
BinTree BST, MinP, MaxP, Tmp;
ElementType X;
int N, i;
BST = NULL;
scanf("%d", &N);
for ( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Insert(BST, X);
}
printf("==遍历:==\n");
printf("先序遍历:");
PreorderTraversal(BST);
printf("\n");
printf("中序遍历:");
InorderTraversal(BST);
printf("\n");
printf("后序遍历:");
PostorderTraversal(BST);
printf("\n");
printf("层次遍历:");
LevelorderTraversal(BST);
printf("\n");
printf("==查询结点:==\n");
MinP = FindMin(BST);
MaxP = FindMax(BST);
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
Tmp = Find(BST, X);
if (Tmp == NULL) printf("%d is not found\n", X);
else {
printf("%d is found\n", Tmp->Data);
if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
}
}
printf("==删除搜索树上的结点:==\n");
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Delete(BST, X);
}
printf("中序遍历:"); InorderTraversal(BST); printf("\n");
return 0;
}
void PreorderTraversal( BinTree BT ){
if (BT){
printf("%d ", BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}
void InorderTraversal( BinTree BT ){
if (BT){
InorderTraversal(BT->Left);
printf("%d ", BT->Data);
InorderTraversal(BT->Right);
}
}
void PostorderTraversal( BinTree BT ){
if (BT){
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
printf("%d ", BT->Data);
}
}
void LevelorderTraversal( BinTree BT ){
queue<BinTree> Q;
BinTree T;
if (!BT) return;
Q.push(BT);
while (Q.empty() == false){
T = Q.front();
Q.pop();
printf("%d ", T->Data);
if (T->Left){
Q.push(T->Left);
}
if (T->Right){
Q.push(T->Right);
}
}
}
BinTree Insert( BinTree BST, ElementType X ){
if (!BST){
BST = (BinTree) malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = NULL;
BST->Right = NULL;
} else {
if (X > BST->Data){
BST->Right =Insert(BST->Right, X);
} else if (X < BST->Data){
BST->Left =Insert(BST->Left, X);
}
}
return BST;
}
Position Find( BinTree BST, ElementType X ){
while(BST){
if (BST->Data == X){
return BST;
} else if (BST->Data < X){
BST = BST->Right;
} else {
BST = BST->Left;
}
}
return NULL;
}
Position FindMin( BinTree BST ){
if (BST){
while (BST->Left){
BST = BST->Left;
}
}
return BST;
}
Position FindMax( BinTree BST ){
if (BST){
while(BST->Right){
BST =BST->Right;
}
}
return BST;
}
BinTree Delete( BinTree BST, ElementType X ){
Position Temp;
if (!BST) {
printf("Not Found\n");
} else{
if (X > BST->Data){
BST->Right =Delete( BST->Right, X );
} else if (X < BST->Data){
BST->Left = Delete( BST->Left, X );
} else {
if (BST->Left && BST->Right){
Temp = FindMin(BST->Right);
BST->Data = Temp->Data;
BST->Right =Delete( BST->Right, BST->Data);
} else {
Temp = BST;
if (!BST->Left){
BST = BST->Right;
} else if (!BST->Right){
BST = BST->Left;
}
free(Temp);
}
}
}
return BST;
}
运行结果
4 平衡二叉树AVL
定义
- 空树，或者：
- 任一结点左子树和右子树的高度差的绝对值小于等于1的二叉搜索树（
|BF(T)| <=1） - BF:Balance Factor 平衡因子，
BF(T)=hL - hR - 注意平衡二叉树仍然是二叉搜索树，只是在二叉搜索树的基础上增加了“平衡”的要求
平衡二叉树的基本操作
- 建树
- 查找，与二叉查找树相同
- 插入， 需要进行调整
- 删除，复杂
平衡二叉树的调整
LL旋转：麻烦节点在发现者的左子树的左边（X < T->Left->Data）
SingleLeftRotation
SingleLeftRotation
SingleLeftRotation
RR旋转：麻烦节点在发现者的右子树的右边
SingleRightRotation
LR旋转：麻烦节点在发现者的左子树的右边
RL旋转：麻烦节点在发现者的右子树的左边
右-左双旋， 一次SingleLeftRotation，一次SingleRightRotation
图片.png
图片.png
04-树5 Root of AVL Tree (25分)
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct AVLNode* Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode {
ElementType Data; /* 结点数据 */
AVLTree Left; /* 指向左子树 */
AVLTree Right; /* 指向右子树 */
int Height; /* 树高 */
};
int GetHeight(AVLTree A) {
if (A) {
return A->Height;
}
else {
return 0;
}
}
int Max(int a, int b)
{
return a > b ? a : b;
}
/* 左单旋 */
AVLTree SingleLeftRotation(AVLTree A)
{
/* 注意：A必须有一个左子结点B */
/* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height = Max(GetHeight(B->Left), A->Height) + 1;
return B;
}
/* 右单旋 */
AVLTree SingleRightRotation(AVLTree A)
{
AVLTree B = A->Right;
A->Right = B->Left;
B->Left = A;
A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height = Max(GetHeight(B->Right), A->Height) + 1;
return B;
}
/* 左-右双旋*/
AVLTree DoubleLeftRightRotation(AVLTree A)
{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
/* 将A、B与C做两次单旋，返回新的根结点C */
/* 将B与C做右单旋，C被返回 */
A->Left = SingleRightRotation(A->Left);
/* 将A与C做左单旋，C被返回 */
return SingleLeftRotation(A);
}
/* 右-左双旋*/
AVLTree DoubleRightLeftRotation(AVLTree A)
{
A->Right = SingleLeftRotation(A->Right);
return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T, ElementType X)
{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */
if (!T) { /* 若插入空树，则新建包含一个结点的树 */
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->Data = X;
T->Height = 0;
T->Left = T->Right = NULL;
} /* if (插入空树) 结束 */
else if (X < T->Data) {
/* 插入T的左子树 */
T->Left = Insert(T->Left, X);
/* 如果需要左旋 */
if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
if (X < T->Left->Data)
T = SingleLeftRotation(T); /* 左单旋 */
else
T = DoubleLeftRightRotation(T); /* 左-右双旋 */
} /* else if (插入左子树) 结束 */
else if (X > T->Data) {
/* 插入T的右子树 */
T->Right = Insert(T->Right, X);
/* 如果需要右旋 */
if (GetHeight(T->Left) - GetHeight(T->Right) == -2)
if (X > T->Right->Data)
T = SingleRightRotation(T); /* 右单旋 */
else
T = DoubleRightLeftRotation(T); /* 右-左双旋 */
} /* else if (插入右子树) 结束 */
/* else X == T->Data，无须插入 */
/* 别忘了更新树高 */
T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
return T;
}
int main() {
AVLTree Head = NULL;
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x = 0;
scanf("%d", &x);
Head = Insert(Head, x);
}
printf("%d", Head->Data);
}
5 堆与哈夫曼树
堆定义
堆是一颗完全二叉树，可以用数组来进行表示。
- 大顶堆：任意节点的数值是其左右子树所有节点的最大值
- 小顶堆：任意节点的数值是其左右子树所有节点的最小值
堆基本操作
- 初始化size=0的堆
- 插入数据（向下过滤）
- 删除数据
- 调整堆
大顶堆
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
ElementType *Data; /* 存储元素的数组 */
int Size; /* 堆中当前元素个数 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */
#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
MaxHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */
MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
return H;
}
bool IsFull( MaxHeap H )
{
return (H->Size == H->Capacity);
}
bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */
int i;
if ( IsFull(H) ) {
printf("最大堆已满");
return false;
}
i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
for ( ; H->Data[i/2] < X; i/=2 )
H->Data[i] = H->Data[i/2]; /* 上滤X */
H->Data[i] = X; /* 将X插入 */
return true;
}
#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
bool IsEmpty( MaxHeap H )
{
return (H->Size == 0);
}
ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
int Parent, Child;
ElementType MaxItem, X;
if ( IsEmpty(H) ) {
printf("最大堆已为空");
return ERROR;
}
MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
/* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
return MaxItem;
}
/*----------- 建造最大堆 -----------*/
void PercDown( MaxHeap H, int p )
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;
X = H->Data[p]; /* 取出根结点存放的值 */
for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
}
void BuildHeap( MaxHeap H )
{ /* 调整H->Data[]中的元素，使满足最大堆的有序性 */
/* 这里假设所有H->Size个元素已经存在H->Data[]中 */
int i;
/* 从最后一个结点的父节点开始，到根结点1 */
for( i = H->Size/2; i>0; i-- )
PercDown( H, i );
}
05-树7 堆中的路径 (25分)
构造小顶堆，并输出路径
输入样例：
5 3
46 23 26 24 10
5 4 3
输出样例：
24 23 10
46 23 10
26 10
图片.png
#include <stdlib.h>
#include <stdio.h>
#define MINDATA -10001 /* 该值应根据具体情况定义为小于堆中所有可能元素的值 */
typedef int ElementType;
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
ElementType *Data; /* 存储元素的数组 */
int Size; /* 堆中当前元素个数 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MinHeap; /* 最小堆 */
MinHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最小堆 */
MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MINDATA; /* 定义"哨兵"为小于于堆中所有可能元素的值*/
return H;
}
bool IsFull( MinHeap H )
{
return (H->Size == H->Capacity);
}
bool Insert( MinHeap H, ElementType X )
{ /* 将元素X插入最小堆H，其中H->Data[0]已经定义为哨兵 */
int i;
if ( IsFull(H) ) {
printf("最小堆已满");
return false;
}
i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
for ( ; H->Data[i/2] > X; i/=2 )
H->Data[i] = H->Data[i/2]; /* 上滤X */
H->Data[i] = X; /* 将X插入 */
return true;
}
int main(){
int N=0, M=0;
scanf("%d %d", &N, &M);
MinHeap H = CreateHeap(N);
for (int i=0; i< N; i++){
int curr = 0;
scanf("%d", &curr);
Insert(H, curr);
}
for (int i=0; i<M;i++){
int curr = 0;
scanf("%d", &curr);
printf("%d", H->Data[curr]);
curr = curr /2;
while (curr>=1){
printf(" %d", H->Data[curr]);
curr = curr /2;
}
printf("\n");
}
}
哈夫曼树
- 哈夫曼树不唯一
6 并查集
数组中，下标表示连接元素的编号，值表示其父节点编号。其中负数都是根节点，负数对应的值表示该集合中元素个数。这种使用负数表示规模的技巧，是对Union方法的优化。
路径压缩，是对Find方法的优化。
图片.png
图片.png
#define MAXN 1000 /* 集合最大元素个数 */
typedef int ElementType; /* 默认元素可以用非负整数表示 */
typedef int SetName; /* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */
void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 这里默认Root1和Root2是不同集合的根结点 */
/* 保证小集合并入大集合 */
if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
S[Root2] += S[Root1]; /* 集合1并入集合2 */
S[Root1] = Root2;
}
else { /* 如果集合1比较大 */
S[Root1] += S[Root2]; /* 集合2并入集合1 */
S[Root2] = Root1;
}
}
SetName Find( SetType S, ElementType X )
{ /* 默认集合元素全部初始化为-1 */
if ( S[X] < 0 )
return X; // 返回集合的根
else
/* 路径压缩 ，尾递归*/
// 先找到X的根，然后覆盖X的父节点，最后返回根
return S[X] = Find( S, S[X] );
}
05-树8 File Transfer (25分)
输入样例：
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
输出样例：
no
no
yes
There are 2 components.
注意这道题的节点编号是从1N的，我们需要在操作中映射到0N-1位置上
#include <stdio.h>
int SetType[10003];
int Find(int x){
if (SetType[x] < 0) {
return x; // x 就是根
} else {
return SetType[x] = Find(SetType[x]); // 路径压缩
}
}
void Union(int RootA, int RootB){
if (SetType[RootA] < SetType[RootB]){
SetType[RootA]+=SetType[RootB];
SetType[RootB] = RootA;
} else {
SetType[RootB] += SetType[RootA];
SetType[RootA] = RootB;
}
}
void initSet(int n){
for (int i=0; i<n;i++){
SetType[i] = -1;
}
}
void Input_Two(int n){
int a = 0, b = 0;
scanf("%d %d\n", &a, &b);
int RootA = Find(a-1);
int RootB = Find(b-1);
Union(RootA, RootB);
}
void Check_Two(int n){
int a = 0, b = 0;
scanf("%d %d\n", &a, &b);
if (Find(a-1) == Find(b-1)){
printf("yes\n");
} else {
printf("no\n");
}
}
void Check_Whole(int n){
int count = 0;
for (int i=0;i<n;i++){
if (SetType[i] < 0){
count++;
}
}
if (count == 1){
printf("The network is connected.");
} else {
printf("There are %d components.", count);
}
}
int main(){
int N = 0;
char in;
scanf("%d\n", &N);
initSet(N);
do{
scanf("%c", &in);
switch(in){
case 'I':Input_Two(N);break;
case 'C':Check_Two(N);break;
case 'S':Check_Whole(N);break;
}
}while (in != 'S');
return 0;
}
