PTA刷题总结-Part3.4 树结构专题

作者: 苏wisdom | 来源:发表于2020-04-05 18:46 被阅读0次

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);
        }

    }
}

习题：leetcode-二叉树的层序遍历

这道题注意对于每层节点的处理

习题：二叉树的序列化和反序列化

这道题可以用先序遍历或者层序遍历实现

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

RR旋转：麻烦节点在发现者的右子树的右边

SingleRightRotation

LR旋转：麻烦节点在发现者的左子树的右边

RL旋转：麻烦节点在发现者的右子树的左边
右-左双旋，一次SingleLeftRotation，一次SingleRightRotation

图片.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

    #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分)
输入样例：

输出样例：

no
no
yes
There are 2 components.

注意这道题的节点编号是从1_{N的，我们需要在操作中映射到0}N-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;
}

PTA刷题总结-Part3.4 树结构专题

1 关于树的重要定义

1.1 分类

1.2 二叉树的重要性质

2 二叉树的表示和基本操作

2.1 数组存储完全二叉树

2.2 链表表示的二叉树

2.3 不需要创建树而得到遍历的方法

3 二叉搜索树BST

4 平衡二叉树AVL

5 堆与哈夫曼树

6 并查集

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读