二叉树遍历

前序遍历：

1
2
3
4
5
6
7
void First_traversal(int p)//前序遍历
{
    if(p==0) return;
    cout<<a[i].now;
    First_traversal(a[i].leftchild);
    First_traversal(a[i].rightchild);
}

中序遍历：

1
2
3
4
5
6
7
void Second_traversal(int p)//中序遍历
{
    if(p==0) return;
    First_traversal(a[i].leftchild);
    cout<<a[i].now;
    First_traversal(a[i].rightchild);
}

后序遍历：

1
2
3
4
5
6
7
void Third_traversal(int p)//后序遍历
{
    if(p==0) return;
    First_traversal(a[i].leftchild);
    First_traversal(a[i].rightchild);
    cout<<a[i].now;
}

二叉树重建：

中序和后序得出前序遍历

1
2
3
4
5
6
7
8
9
10
11
void Tree_Second_to_Third(int n,int la,int lb)//中序和后序得出前序遍历
{  
    if(n<=0) return;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        cout<<b[lb];
        Tree_Second_to_Third(i-la,la,lb-n-la+i);
        Tree_Second_to_Third(la+n-i-1,i+1,lb-1);
    }
}

前序和中序得出后序遍历

1
2
3
4
5
6
7
8
9
10
11
void Tree_First_to_Second(int n,int la,int lb)//前序和中序得出后序遍历
{
    if(n<=0) return;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        Tree_First_to_Second(i-la,la,lb+1);
        Tree_First_to_Second(la+n-i-1,i+1,lb+i-la+1);
        cout<<b[lb];
    }
}

前序+中序→重建

1
2
3
4
5
6
7
8
9
10
11
12
13
int Build_Frist_to_Second(int n,int la,int lb)//前序+中序→重建
{
    if(n<=0) return 0;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        int This=++now;
        tree[This].ID=a[i];
        tree[This].leftchild=Build_Frist_to_Second(i-la,la,lb+1);
        tree[This].rightchild=Build_Frist_to_Second(la+n-i-1,i+1,lb+i-la+1);
        return This;
    }
}

后序+中序→重建

1
2
3
4
5
6
7
8
9
10
11
12
13
int Build_Second_to_Third(int n,int la,int lb)//后序+中序→重建
{
    if(n<=0) return 0;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        int This=++now;
        tree[This].ID=a[i];
        tree[This].leftchild=Build_Second_to_Third(i-la,la,lb-n-la+i);
        tree[This].rightchild=Build_Second_to_Third(la+n-i-1,i+1,lb-1);
        return This;
    }
}

并查集

并查集递归版本（数据量大了会爆栈）

1
2
3
4
5
6
int Getfather(int x)//并查集递归版本（数据量大了会爆栈）
{
    if(father[x]==x) return x;
    father[x]=Getfather(father[x]);
    return father[x];
}

并查集while循环版本

1
2
3
4
5
6
7
8
9
10
11
12
13
int Getfather(int x)//并查集while循环版本
{
    int Fanily_father=x;
    while(father[Fanily_father]!=Fanily_father)
    Fanily_father=father[Fanily_father];
    while(Fanily_father!=x)
    {
        int This=father[x];
        father[x]=Fanily_father;
        x=This;
    }
    return Fanily_father;
}

并查集的初始化

1
2
3
4
5
int Father_Firstly()//并查集的初始化
{
    for(int i=1;i<=n;i++)
    father[i]=i;
}

并查集的合并

1
2
3
4
5
int together(int x,int y)//并查集的合并
{
    father[Getfather(y)]=Getfather(x);
    //这里合并的是两个集合（集合可以只有一个元素）
}

二叉搜索树

查找最大值：

1
2
3
4
5
6
7
8
9
int Search(int Left,int Right,int Root)
{
    if(y<Left||x>Right) return -123456789;
    if(x<=Left&&y>=Right) return a[Root];
    int Mid=(Left+Right)/2;
    int First=Search(Left,Mid,Root*2);
    int Second=Search(Mid+1,Right,Root*2+1);
    return max(First,Second);
}

修改值：

1
2
3
4
5
6
7
8
9
10
11
12
13
void Change(int Left,int Right,int Root)
{
    if(x<Left||x>Right) return;
    if(Left==Right)
    {
        a[Root]=y;
        return;
    }
    int Mid=(Left+Right)/2;
    Change(Left,Mid,Root*2);
    Change(Mid+1,Right,Root*2+1);
    a[Root]=max(a[Root*2],a[Root*2+1]);
}

二叉索引树

修改代码：

1
2
3
4
5
6
7
8
void Change(int x,int add)
{
    while(x<=n)
    {
        c[x]+=add;
        x+=Lowbit(x);
    }
}

查询代码：

1
2
3
4
5
6
7
8
9
10
int Question(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=Lowbit(x);
    }
    return ans;
}