目录

二叉排序树

  • 先序遍历：根->左->右
  • 中序遍历：左->根->右
  • 后序遍历：左->右->根

1.二叉排序树(代码)

输入
7
5 4 3 3 3 2 1
输出
1 2 3 3 3 4 5

//二叉排序树（左<根<右）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
struct node{
    ll val,lc,rc,w;//W表示这个位置有多少个重复的值；lc左子树；rc右子树；val权值
}T[N];
ll n,cnt,a[N];
void ins(ll o,ll v)//插入点
{
    if(!T[o].val){T[o].val=v;T[o].w++;return ;}//如果没插入过就直接插入
    if(T[o].val==v){T[o].w++;return ;}//如果val相同就w++;
    if(v<T[o].val)//如果要插入的值小于要插入的位置的值，就往左子树插入
    {
        if(!T[o].lc)T[o].lc=++cnt;//若未定义就定义左子树
        ins(T[o].lc,v);
    }
    if(v>T[o].val)
    {
        if(!T[o].rc)T[o].rc=++cnt;
        ins(T[o].rc,v);
    }
}
void dfs(ll o)//中序遍历（左->根->右）
{
    if(!T[o].val)return ;
    if(T[o].lc)dfs(T[o].lc);//左子树有就往左搜
    for(ll i=1;i<=T[o].w;i++)//把值相同的遍历一遍
        printf("%lld ",T[o].val);
    if(T[o].rc)dfs(T[o].rc);//右子树有就往右搜
}
int main()
{
    cnt=1;//往1插
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",a+i);
    for(int i=1;i<=n;i++)
        ins(1,a[i]);
    dfs(1);
    return 0;
}

P1087 FBI树 (建树)

P1087 FBI树
题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：T的根结点为R，其类型与串S的类型相同；若串
S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1
​构造R的左子树T1，由右子串S2​构造R的右子树T2。现在给定一个长度为2^N的“
01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入格式
第一行是一个整数N(0≤N≤10)，
第二行是一个长度为2^N的“01”串。
输出格式
一个字符串，即FBI树的后序遍历序列。
输入 #1

3
10001011

输出 #1

IBFBBBFIBFIIIFF

一颗二叉树
需要从树底往树根从下往上走，所以用递归，到底了（y<x）才开始输出，实现从下往上的后序遍历

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
string s;
ll n;
void make_tree(ll x ,ll y)
{
    if(y>x)
    {
        make_tree(x,(x+y)>>1);
        make_tree((x+y+1)>>1,y);
    }
    ll B=1,I=1;
    for(ll i=0;i<=y-x;i++)
    {
        if(s[x+i]=='1')B=0;
        else if(s[x+i]=='0')I=0;
    }
    if(B)cout<<"B";
    else if(I)cout<<"I";
    else cout<<"F";
}
int main()
{
    cin>>n>>s;
    make_tree(0,(1<<n)-1);
    return 0;
}

HDU 4707 Pet

HDU 4707 Pet
Problem Description
One day, Lin Ji wake up in the morning and found that his pethamster escaped. He searched in the room but didn’t find the hamster. He tried to use some cheese to trap the hamster. He put the cheese trap in his room and waited for three days. Nothing but cockroaches was caught. He got the map of the school and foundthat there is no cyclic path and every location in the school can be reached from his room. The trap’s manual mention that the pet will always come back if it still in somewhere nearer than distance D. Your task is to help Lin Ji to find out how many possible locations the hamster may found given the map of the school. Assume that the hamster is still hiding in somewhere in the school and distance between each adjacent locations is always one distance unit.

Input
The input contains multiple test cases. Thefirst line is a positive integer T (0<T<=10), the number of test cases. For each test cases, the first line has two positive integer N (0<N<=100000) and D(0<D<N), separated by a single space. N is the number of locations in the school and D is the affective distance of the trap. The following N-1lines descripts the map, each has two integer x and y(0<=x,y<N), separated by a single space, meaning that x and y is adjacent in the map. Lin Ji’s room is always at location 0.

Output
For each test case, outputin a single line the number of possible locations in the school the hamster may be found.

题目大意：所有房子组成一棵树，求出离根节点0的距离大于d的节点个数
Sample Input

1
10 2
0 1
0 2
0 3
1 4
1 5
2 6
3 7
4 8
6 9

Sample Output

2

本题输入过多，cin不加速就过不了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100010;
ll n,dis[N],d,ans;
vector<ll>G[N];
void addedge(ll u,ll v)//建树
{
    G[u].push_back(v);
    G[v].push_back(u);
}
void dfs(ll u,ll f)//F指的是父节点
{
    if(dis[u]>d)ans++;
    for(ll i=0;i<G[u].size();i++)
    {
        ll v=G[u][i];
        if(v==f)continue;//往下遍历防止重复
        dis[v]=dis[u]+1;
        dfs(v,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll t;
    cin>>t;
    while(t--)
    {
        memset(dis,0,sizeof(dis));
        for(int i=0;i<n;i++)G[i].clear();
        cin>>n>>d;ans=0;
        for(int i=1;i<n;i++)
        {
            ll u,v;
            cin>>u>>v;
            addedge(u,v);
        }
        dfs(0,0);
        cout<<ans<<endl;
    }
    return 0;
}