算法笔记第九章树

本文主要是介绍算法笔记第九章树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

9.2二叉树的遍历

A1020

本题考察的是由中序序列和其他一个遍历序列建树的算法。关键是写出建树的函数。由于我们要建树，所以返回值可以用node*来表示。又因为要递归表示，所以要注意结束条件。

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 30;
struct node
{
    int data;
    node* lchild;
    node* rchild;
};
node* creatTree(int post[], int in[], int pl, int pr, int il, int ir)
{
    if(pl > pr) return NULL;
    node* root = new node;
    int k;
    for(k = il; k < ir; k++)
    {
        if(in[k] == post[pr]) break;
    }
    root->data = post[pr];
    int numright = ir - k;
    root->rchild = creatTree(post, in, pr- numright, pr - 1, k+1, ir);
    root->lchild = creatTree(post, in, pl, pr - numright - 1, il, k - 1);
    return root;
}
int num = 0, n;
int post[N], in[N];
void BFS(node* root)
{
    queue<node*> qu;
    qu.push(root);
    while(! qu.empty())
    {
        node* now = qu.front();
        qu.pop();
        printf("%d", now->data);
        num++;
        if(num < n) printf(" ");
        if(now->lchild != NULL) qu.push(now->lchild);
        if(now->rchild != NULL) qu.push(now->rchild);
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &post[i]);
    for(int i = 0; i < n; i++)
        scanf("%d", &in[i]);
    node* root = creatTree(post, in, 0, n-1, 0, n-1);
    BFS(root);
    return 0;
}

A1086

本题考察用栈模拟中序和前序遍历，使得利用两个序列建树，最后再后序遍历的算法。由于中序前序遍历都可以用非递归函数模拟，所以我们要自己先将pop出的元素序列写出来，观察它是哪个序列，最后再用中+其他序列的方法建树。

本题还需要注意的是如何处理输入输出。可以用strcmp来比较第一个是push还是pop。如果是push再输入一个x，否则按pop来处理。

#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int N = 40;
struct node
{
    int data;
    node* lchild, *rchild;
};
int pre[N], in[N], preindex = 0, inindex = 0;
int n, num = 0;
node* createTree(int pl, int pr, int il, int ir)
{
    if(pl > pr) return NULL;
    node* root = new node;
    root->data = pre[pl];
    int k;
    for(k = il; k <= ir; k++)
        if(in[k] == pre[pl]) break;
    int numleft = k - il;
    root->lchild = createTree(pl+1, pl+numleft, il, k - 1);
    root->rchild = createTree(pl+numleft+1, pr, k+1, ir);
    return root;
}
void postorder(node* root)
{
    if(root == NULL) return ;
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%d", root->data);
    num++;
    if(num < n) printf(" ");
}
int main()
{
    scanf("%d", &n);
    char str[5];
    int x;
    stack<int> st;
    for(int i = 0; i < 2*n; i++)
    {
        scanf("%s", str);
        if(strcmp(str, "Push") == 0)
        {
            scanf("%d", &x);
            pre[preindex++] = x;
            st.push(x);
        }
        else
        {
            in[inindex++] = st.top();
            if( !st.empty()) st.pop();
        }
    }
    node* root = createTree(0, n-1, 0, n-1);
    postorder(root);
    return 0;
}

A1102

本题是转换二叉树。转换二叉树就是在后序遍历的基础上，当要访问根结点时，invite函数为交换左右子树即可。即：swap(lchild,rchild)。如果要访问反转二叉树的层序遍历那么可以用上述方法。还有种更简便的方法：如果题目要是用前中后序顺序来访问二叉树，可以直接在函数里先访问右子树再访问左子树，其他不变。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 50;
struct
{
    int lchild, rchild;
}node[N];
int n, num1 = 0;
bool isroot[N];
int char2num(char c)
{
    if(c == '-') return -1;
    else
    {
        isroot[c - '0'] = false;
        return c - '0';
    }
}
int findroot()
{
    for(int i = 0; i < n; i++)
        if(isroot[i]) return i;
}
void postinvert(int root)
{
    if(root == -1 ) return;
    postinvert(node[root].lchild);
    postinvert(node[root].rchild);
    swap(node[root].lchild, node[root].rchild);
}
void level_Order(int root)
{
    int num = 0;
    queue<int> q;
    q.push(root);
    while(! q.empty())
    {
        int now = q.front();
        q.pop();
        printf("%d", now);
        num++;
        if(num < n) printf(" ");
        else printf("\n");
        if(node[now].lchild != -1) q.push(node[now].lchild);
        if(node[now].rchild != -1) q.push(node[now].rchild);
    }
}
void inorder(int root)
{
    if(root == -1) return;
    inorder(node[root].lchild);
    printf("%d", root);
    num1++;
    if(num1 < n) printf(" ");
    else printf("\n");
    inorder(node[root].rchild);
}
int main()
{
    memset(isroot, true, sizeof(isroot));
    scanf("%d", &n);
    char lchild, rchild;
    for(int i = 0; i < n; i++)
    {
        scanf("%*c%c %c", &lchild, &rchild);
        node[i].lchild = char2num(lchild);
        node[i].rchild = char2num(rchild);
    }
    int root = findroot();
    postinvert(root);
    level_Order(root);
    inorder(root);
    return 0;
}

9.3 树的遍历

由于普通树用vector数组存放，所以一般遍历时用循环写。又由于循环自带判断条件，所以在dfs中可以不用加结束条件。
普通树的遍历如果需要考虑层次问题时，如果没有考虑叶子结点的权值可以用一个level数组+vector数组来记录层次和数组。

A1079

本题是一个关于一般树的遍历问题。首先要处理输入输出问题，由于本题需要考虑叶子结点的权值，所以可以用包含变量int和vector的结构体来表示。由于已经给定树的编号，所以可以用结构体数组的写法（静态链表）。在输入时根据k的大小判断后序是输入叶子结点还是销售额。又由于要考虑深度的问题，所以可以在preorder中加入一个depth变量用于记录深度。

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 100010;
struct node
{
    int data;
    vector<int> child;
}Node[N];
int n;
double p, r, ans = 0;
void preorder(int root, int depth)
{
    if(Node[root].child.size() == 0)
    {
        ans += pow(1+r, depth)* Node[root].data * p;
    }
    else
    {
        for(int i = 0; i < Node[root].child.size(); i++)
        {
            preorder(Node[root].child[i], depth+1);
        }
    }
}
int main()
{
    int k, child;
    scanf("%d%lf%lf", &n, &p, &r);
    r /= 100;
    for(int i =0; i < n; i++)
    {
        scanf("%d", &k);
        if(k != 0)
        {
            for(int j = 0; j < k; j++)
            {
                scanf("%d", &child);
                Node[i].child.push_back(child);
            }
        }
        else
        {
            scanf("%d", &Node[i].data);
        }
    }
    preorder(0, 0);
    printf("%.1f", ans);
    return 0;
}

A1090

本题和1079没有啥不同，都是关于树的遍历。由于只要找到最大的深度和最大深度的结点个数，不需要考虑权值问题，所以可以用vectornode[N]的写法来表示树。此时判断树是否为叶子结点的条件为node[i].size()==0。所以在递归中，如果是叶子结点则让其与最大深度进行比较如果大于则更新，相等则更新num否则退出。如果不是叶子结点则继续递归。

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 100010;
vector<int> Node[N];
int n, maxdepth = -1, num = 0;
double p, r;
void preorder(int root, int depth)
{
    if(Node[root].size() == 0)
    {
        if(maxdepth < depth)
        {
            maxdepth = depth;
            num = 1;
        }
        else if(maxdepth == depth)
            num++;
        return;
    }
    for(int i = 0; i < Node[root].size(); i++)
    {
        preorder(Node[root][i], depth+1);
    }
    
}
int main()
{
    int parent, root;
    scanf("%d%lf%lf", &n, &p, &r);
    r /= 100;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &parent);
        if(parent == -1) root = i;
        else Node[parent].push_back(i);
    }
    preorder(root, 0);
    printf("%.2f %d", pow(1+r, maxdepth)*p, num);
    return 0;
}

A1094

本题是找同一层最大结点数的题。可以用dfs或者bfs写。
注意点：

由于开始结点是1，所以结点下标是从1~n，遍历时要≤n才行，否则当测试用例只有一个结点的时候会出错。
可以设置结构体，在结构体里加入layer变量，但是由于不需要考虑结点的权值，也可以用vector数组来表示结点，定义两个数组，一个数组levelnumber是层数到层数结点数的映射，另一个数组h是结点到层数的映射。在bfs或者dfs里的访问结点即为，将结点所在层数的层数结点数加1，即：levelnumber[h[id]]++。
给的代码将dfs和bfs都写了一遍，调用任意一个即可。

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N = 110;
vector<int> Node[N];
int n, m;
int levelNumber[N];
int h[N];
void DFS(int root)
{
    levelNumber[h[root]]++;
    for(int i = 0; i < Node[root].size(); i++)
    {
        int child = Node[root][i];
        h[child] = h[root]+1;
        DFS(child);
    }
}
void BFS()
{
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int now = q.front();
        levelNumber[h[now]]++;
        q.pop();
        for(int i = 0; i < Node[now].size(); i++)
        {
            int child = Node[now][i];
            h[child] = h[now]+1;
            q.push(child);
        }
    }
}
int main()
{
    int parent, k, child;
    memset(levelNumber, 0, sizeof(levelNumber));
    memset(h, 0, sizeof(h));
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &parent, &k);
        for(int j = 0; j < k; j++)
        {
            scanf("%d", &child);
            Node[parent].push_back(child);
        }
    }
    h[1] = 1;
    DFS(1);
    int level = 1, number = -1;
    for(int i = 1; i <= n; i++)
    {
        if(levelNumber[i] > number)
        {
            number = levelNumber[i];
            level = i;
        }
    }
    printf("%d %d", number, level);
    return 0;
}

A1106

本题是找深度最小的树，注意开始mindepth要设一个很大的值。

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 100010;
vector<int> Node[N];
int h[N];
int n, mindepth = N, num = 0;
double p, r;
void DFS(int root)
{
    if(Node[root].size() == 0)
    {
        if(h[root] < mindepth)
        {
            mindepth = h[root];
            num = 1;
        }
        else if(h[root] == mindepth)
            num++;
    }
    for(int i = 0; i < Node[root].size(); i++)
    {
        int child = Node[root][i];
        h[child] = h[root]+1;
        DFS(child);
    }
}
int main()
{
    scanf("%d%lf%lf", &n, &p, &r);
    r /= 100;
    int child, k;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &k);
        for(int j = 0; j < k; j++)
        {
            scanf("%d", &child);
            Node[i].push_back(child);
        }
    }
    h[0] = 0;
    DFS(0);
    printf("%.4f %d", pow(1+r, mindepth)*p, num);
    return 0;
}

A1004

本题和1094的思路差不多，都是找同一层次满足条件的个数，但是本题要求比1094难一点，因为1094只需要找到最值，所以可以不用找到最大层数，直接全部遍历即可，但是本题需要逐一输出，所以要找到最大层数。

如果找最大层数，需要注意一开始maxdepth需要和第一层设置的值一样，如果设置第一层为1，那么maxdepth也为1。否则会因为特殊数据(1 0)导致maxdepth不更新，没有输出的情况
没有权值，考虑使用levelnumber数组建立层数到个数的映射，h数组建立结点到层数的映射。用vector数组存储树结点。

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N = 110;
vector<int> Node[N];
int levelnumber[N];
int h[N];
int maxdepth = 1;
void BFS()
{
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        if(Node[now].size() == 0)
            levelnumber[h[now]]++;
        else
        {
            for(int i = 0; i < Node[now].size(); i++)
            {
                int child = Node[now][i];
                h[child] = h[now]+1;
                if(h[child] > maxdepth)
                    maxdepth = h[child];
                q.push(child);
            }
        }
    }
}
int main()
{
    int n, m;
    int parent, k, child;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &parent, &k);
        for(int j = 0; j < k; j++)
        {
            scanf("%d", &child);
            Node[parent].push_back(child);
        }
    }
    h[1] = 1;
    BFS();
    for(int i = 1; i <= maxdepth; i++)
    {
        printf("%d", levelnumber[i]);
        if(i != maxdepth) printf(" ");
    }
    return 0;
}

A1053

本题是树的遍历，只不过需要用dfs搜索，需要注意的一个点是：因为可能会出现一个结点下面有两个子结点权值相等的情况，所以不能先排序，需要将所有的结果存储起来再进行排序。

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m, s;
vector<int> temp;
vector<vector<int> > ans;
struct node
{
    int weight;
    vector<int>child;
}Node[N];
bool cmp(vector<int>a, vector<int> b)
{
    int size = min(a.size(), b.size());
    for(int i = 0; i < size; i++)
    {
        if(a[i] != b[i]) return a[i] > b[i];
    }
}
int path[N];
void DFS(int index, int now)
{
    if(now == s && Node[index].child.size() == 0 )
    {
        ans.push_back(temp);
        return ;
    }
    if(now > s || Node[index].child.size() == 0) return ;
    for(int i = 0; i < Node[index].child.size(); i++)
    {
        int child = Node[index].child[i];
        temp.push_back(Node[child].weight);
        DFS(child, now + Node[child].weight);
        temp.pop_back();
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 0; i < n; i++)
        scanf("%d", &Node[i].weight);
    int parent, k, child;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &parent, &k);
        for(int j = 0; j < k; j++)
        {
            scanf("%d", &child);
            Node[parent].child.push_back(child);
        }
    }
    temp.push_back(Node[0].weight);
    DFS(0,Node[0].weight);
    sort(ans.begin(), ans.end(), cmp);
    for(int i = 0; i < ans.size(); i++)
    {
        for(int j = 0; j < ans[i].size(); j++)
        {
            printf("%d", ans[i][j]);
            if(j != ans[i].size() - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

9.4二叉查找树

二叉查找树有个性质：中序遍历为有序序列。所以任意给定一个遍历序列都可以唯一建立一个二叉树。当给的是先序序列时由于第一个就是根节点所以可以按照循环插入的方法建树，也可以用普通二叉树建立的方法写一个函数。
二叉树的镜像树其实就是在遍历的时候先遍历右子树再遍历左子树

A1043

先根据序列建树，由于给定的是先序序列所以可以用循环插入的方法建树。当建树以后写出preorder和premorder函数。再用temp和pre以及prem对比如果是的则输出post或postm否则输出no。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1010;
struct node
{
    int data;
    node*lchild, *rchild;
};
int n;
void insert(node* & root, int x)
{
    if(root == NULL)
    {
        root = new node;
        root->data = x;
        root->lchild = root->rchild = NULL;
        return;
    }
    else if(x < root->data)
        insert(root->lchild, x);
    else
        insert(root->rchild, x);
}
vector<int> temp, pre, preM, post, postM;
void preorder(node* root, vector<int>& vi)
{
    if(root == NULL) return;
    vi.push_back(root->data);
    preorder(root->lchild, vi);
    preorder(root->rchild, vi);
}
void postOrder(node* root, vector<int>& vi)
{
    if(root == NULL) return;
    postOrder(root->lchild, vi);
    postOrder(root->rchild, vi);
    vi.push_back(root->data);
}
void preMorder(node* root, vector<int>& vi)
{
    if(root == NULL) return ;
    vi.push_back(root->data);
    preMorder(root->rchild, vi);
    preMorder(root->lchild, vi);
}
void postMorder(node* root, vector<int>& vi)
{
    if(root == NULL) return;
    postMorder(root->rchild, vi);
    postMorder(root->lchild, vi);
    vi.push_back(root->data);
}
int main()
{
    int tmp;
    node* root = NULL;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        temp.push_back(tmp);
        insert(root, tmp);
    }
    preorder(root, pre);
    preMorder(root, preM);
    postOrder(root, post);
    postMorder(root, postM);
    if(temp == pre)
    {
        printf("YES\n");
        for(int i = 0; i < post.size(); i++)
        {
            printf("%d", post[i]);
            if(i != post.size() - 1) printf(" ");
            else printf("\n");
        }
    }
    else if(temp == preM)
    {
        printf("YES\n");
        for(int i  = 0; i < postM.size(); i++)
        {
            printf("%d", postM[i]);
            if(i != postM.size() - 1) printf(" ");
            else printf("\n");
        }
    }
    else printf("NO\n");
    return 0;
}

A1064

本题考查给定一个序列如何用数组存储这个序列并建成CBT，用了两个知识点。

BST的中序遍历是递增数列
当用数组存储完全二叉查找树时，按下标递增输出就是层序遍历。

基于上述内容，先将给定的数组递增排序，**因为bst中序是递增，所以可以用中序遍历建树。在访问结点时就是将数值赋给这个结点。**再将数组顺序输出就是层序遍历了。

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1010;
int n, index = 0;
int tmp[N], CBT[N];
void inorder(int root)
{
    if(root > n) return;
    if(root * 2 <= n)
        inorder(root*2);
    CBT[root] = tmp[index++];
    if(root*2 + 1 <= n)
        inorder(root*2+1);
}
void BFS()
{
    int num = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int now = q.front();
        printf("%d", CBT[now]);
        q.pop();
        num++;
        if(num < n) printf(" ");
        if(now*2 <= n) q.push(now*2);
        if(now*2 +1 <= n) q.push(now*2+1);
        
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &tmp[i]);
    sort(tmp, tmp+n);
    inorder(1);
    BFS();
    return 0;
}

A1099

本题本质上和1064的思想一样，都是利用二叉搜索树中序遍历递增的性质在中序遍历时建树。只不过1064是完全二叉树可以用数组存储，而本题是普通二叉树所以需要用结构体实现。

```cpp
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 110;
struct node
{
    int data;
    int lchild, rchild;
}Node[N];
int tmp[N], index = 0, n;
void inorder(int root)
{
    if(root == -1) return ;
    inorder(Node[root].lchild);
    Node[root].data = tmp[index++];
    inorder(Node[root].rchild);
}
void BFS()
{
    int num = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        printf("%d", Node[now].data);
        num++;
        if(num != n) printf(" ");
        else printf("\n");
        if(Node[now].lchild != -1) q.push(Node[now].lchild);
        if(Node[now].rchild != -1) q.push(Node[now].rchild);
    }
}
int main()
{
    int lchild, rchild;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &lchild, &rchild);
        Node[i].lchild = lchild;
        Node[i].rchild = rchild;
    }
    for(int i = 0; i < n; i++)
        scanf("%d", &tmp[i]);
    sort(tmp, tmp + n);
    inorder(0);
    BFS();
    return 0;
}

9.3 AVL树

A1066

本题考察avl树的建立（循环插入），即如何在插入时平衡高度，属于模板题。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 30;
struct node
{
    int data;
    int height;
    node* lchild, *rchild;
};
int getHeight(node* root)
{
    if(root == NULL) return 0;
    else return root->height;
}
void updateHeight(node* root)
{
    root->height =  max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
int getBalanceFactor(node* root)
{
    return getHeight(root->lchild) - getHeight(root->rchild);
}
void L(node* & root)
{
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}
void R(node* & root)
{
    node* temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}
void insert(node* & root, int x)
{
    if(root == NULL)
    {
        root = new node;
        root->data = x;
        root->height = 1;
        root->lchild = root->rchild = NULL;
        return ;
    }
    else if(x < root->data)
    {
        insert(root->lchild, x);
        updateHeight(root->lchild);
        if(getBalanceFactor(root) == 2)
        {
            if(getBalanceFactor(root->lchild) == 1)
            {
                R(root);
            }
            else if(getBalanceFactor(root->lchild) == -1)
            {
                L(root->lchild);
                R(root);
            }
        }
    }
    else 
    {
        insert(root->rchild, x);
        updateHeight(root->rchild);
        if(getBalanceFactor(root) == -2)
        {
            if(getBalanceFactor(root->rchild) == 1)
            {
                R(root->rchild);
                L(root);
            }
            else if(getBalanceFactor(root->rchild) == -1)
            {
                L(root);
            }
        }
    }
}
int main()
{
    int n;
    int a[N];
    node* root = NULL;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        insert(root, a[i]);
    }
    printf("%d", root->data);
    return 0;
}

9.6 并查集

并查集是用数组来实现，其结构图画出来就和树一样。是树的一种应用。

A1107

本题是一道关于并查集题目，由于每个人又不同的兴趣，所以第一个当兴趣的就用来当这个兴趣的负责人。再将当前这个人与同一个兴趣的负责人所在的集合合并。只要有一个兴趣相同就可以合并，所以我们要建立兴趣到负责人的映射，人与人之间的集合。当前这个人读入一个兴趣时，如果这个兴趣已经有人负责了，则加入这个负责人所在的集合。即：Union(i,findfather(course[k]));

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int father[N], course[N];
int isfather[N];
bool cmp(int a, int b)
{
    return a > b;
}
void init(int n)
{
    for(int i = 1; i <= n; i++)
        father[i] = i;
    memset(course, 0, sizeof(course));
}
int findfather(int a)
{
    int x = a;
    while(a != father[a])
        a = father[a];
    while(x != father[x])
    {
        int z = x;
        x = father[x];
        father[z] = a;
    }
    return a;
}
void Union(int a, int b)
{
    int fa = findfather(a);
    int fb = findfather(b);
    if(fa != fb)
    {
        father[fa] = fb;
    }
}
int main()
{
    int n, k, tmp;
    scanf("%d", &n);
    init(n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d:", &k);
        for(int j = 0; j < k; j++)
        {
            scanf("%d", &tmp);
            if(course[tmp] == 0)
                course[tmp] = i;
            Union(i, findfather(course[tmp]));
        }
    }
    for(int i = 1; i <= n; i++)
    {
        isfather[findfather(i)]++;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(isfather[i] != 0) ans++;
    }
    printf("%d\n", ans);
    sort(isfather+1, isfather+n+1, cmp);
    for(int i = 1; i <= ans; i++)
    {
        printf("%d", isfather[i]);
        if(i != ans) printf(" ");
    }
    return 0;
}

9.7堆

堆一般是用数组实现的，其定义为根结点大于(或小于)子结点的值，结构类似于二叉树，是二叉树的一种应用。
建堆：将非叶节点倒着向下调整，即：从n/2~1进行downadjust（i,n）调整。
删除堆顶：用最后一个结点覆盖堆顶，再进行(1,n-1)向下调整
插入结点：将结点插入到数组的最后一个元素，再对最后一个结点进行向上调整，upadjust(1,n+1)。
堆排序：对建立好的堆进行操作，由于堆顶为最大元素，所以将堆顶的元素与最后一个元素呼唤，再进行downadjust(1,n-1)调整，以此类推，直到调整到堆中1~1的情况。

A1098

本题是基础模板题。只需要在排序中设计是否有数组相同的情况，若相同则输出。

本题还有个陷阱，初始序列不能算作相等，因为如果初始序列相等可能会出现两种方法都可以做从而多解的情况。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
int n;
int a[N], b[N], heap[N];
bool flag = false;
bool cmp(int a, int b)
{
    return a < b;
}
bool isSame(int a[], int b[])
{
    for(int i = 1; i <= n; i++)
        if(a[i] != b[i]) return false;
    return true;
}
void disp(int a[])
{
    for(int i = 1; i <= n; i++)
    {
        printf("%d", a[i]);
        if(i != n) printf(" ");
    }
}
void InsertionSort()
{
    bool print = false;
    for(int i = 2; i <= n; i++)
    {
        if(i != 2 &&isSame(a, b))
        {
            printf("Insertion Sort\n");
            print = true;
        }
        sort(a+1, a + i + 1, cmp);
        if(print)
        {
            disp(a);
            flag =  true;
            return ;
        }
    }
}
void downadjust(int low, int high)
{
    int i = low, j = i * 2;
    while(j <= high)
    {
        if(j+1 <= high && heap[j+1] > heap[j])
            j = j + 1;
        if(heap[j] > heap[i])
        {
            swap(heap[j], heap[i]);
            i = j;
            j = i * 2;
        }
        else break;
    }
}
void HeapSort()
{
    bool print = false;
    for(int i = n/2; i >= 1; i--)
        downadjust(i, n);
    for(int i = n; i >= 2; i--)
    {
        if(i != n && isSame(b, heap))
        {
            printf("Heap Sort\n");
            print = true;
        }
        swap(heap[1], heap[i]);
        downadjust(1, i - 1);
        if(print)
        {
            disp(heap);
            return ;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        heap[i] = a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        
    }
    InsertionSort();
    if(!flag) HeapSort();
    return 0;
}

这篇关于算法笔记第九章树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

算法笔记第九章树

9.2二叉树的遍历

A1020

A1086

A1102

9.3 树的遍历

A1079

A1090

A1094

A1106

A1004

A1053

9.4二叉查找树

A1043

A1064

A1099

9.3 AVL树

A1066

9.6 并查集

A1107

9.7堆

A1098

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯