目录

[模板] 树的深度1

[模板] 树的深度2

【深基16.例3】二叉树深度

新二叉树

[模板] 二叉树的先序遍历

 [模板] 二叉树的中序遍历

[模板] 二叉树的后序遍历

[NOIP2001 普及组] 求先序排列

美国血统 American Heritage

 [NOIP2004 普及组] FBI 树

图的遍历

---

关于树的基本知识：(331条消息) 数据结构：树(Tree)【详解】_UniqueUnit的博客-CSDN博客_数据结构 树

[模板] 树的深度1

邻接表存树，然后dfs或bfs遍历。（链表）

代码1：dfs

#include
using namespace std;
const int N = 5010;
int n;
int h[N], e[N], ne[N], idx;
int d[N],q[N];
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
 
int dfs(int t,int u)
{
    d[t] = u;
    for(int i = h[t]; i != -1; i = ne[i])
        dfs(e[i],u + 1);
}
 
int main()
{
    cin>>n;
    memset(h, -1, sizeof h);
 
    for (int i = 2; i <=n; i ++ )
    {
        int a;
        cin>>a;
        add(a, i);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        cout<' ';
    }
 
    return 0;
}

代码2：bfs（和搜索与图论的图中点的层次）

#include
using namespace std;
const int N = 5010;
int n;
int h[N], e[N], ne[N], idx;
int d[N],q[N];
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
 
int bfs(int x)
{
    int hh=0,tt=0;
    q[0]=1;
    memset(d, 0, sizeof d);
    d[1] = 1;
 
    while (hh<=tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j]==0)
            {
                d[j] = d[t] + 1;
                q[++tt]=j;
            }
        }
    }
    return d[x];
}
 
int main()
{
    cin>>n;
    memset(h, -1, sizeof h);
 
    for (int i = 2; i <=n; i ++ )
    {
        int a;
        cin>>a;
        add(a, i);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<bfs(i)<<' ';
    }
 
    return 0;
}

[模板] 树的深度2

链式前向星存树

代码：

#include
using namespace std;
const int N=5010;
int n;
int d[N];
int head[N],cnt=0;
struct node{
    int to,next;
}edge[N*2];
 
inline void add(int x,int y){
    edge[cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt++;
}
 
void dfs(int u,int t){
     d[u]=t;
    for(int i=head[u];~i;i=edge[i].next){
        int cld=edge[i].to;
        dfs(cld,t+1);
 
    }
}
int main(){
    cin>>n;
    memset(head,-1,4*N);
 
    for(int i=0;i-1;i++)
    {
        int x,y;
        cin>>x>>y;
        add(y,x);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        cout<' ';
    }
 
    return 0;
}

【深基16.例3】二叉树深度

用结构体存储左右儿子，dfs深度搜索遍历

代码：

#include
using namespace std;
int res,n;
struct node
{
	int l,r;
}a[1001000];//记录每个节点的左右节点
 
void dfs(int root,int step)
{
    //cout<<"root="<
	if(root==0) return;//如果该节点为0（即它的爸爸没有这个儿子），返回
	res=max(res,step);//记录最大值
	dfs(a[root].l,step+1);//搜索它的左儿子
	dfs(a[root].r,step+1);//搜索它的右儿子
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].l>>a[i].r;//输入该节点的左节点和右节点
 
	dfs(1,1);//从1号节点，深度为1开始搜索
	cout<//输出最大值
	return 0;
}

新二叉树

输出前序遍历

代码1：和上一题做法一样

#include
using namespace std;
char root,ch;
struct nade
{
	char l,r;
}a[130];
 
void dfs(char x)
{
	if(x=='*') return;
	cout<
	dfs(a[x].l);//找到他的左孩子，继续往下探（如果左孩子是*的话，会返回的）
	dfs(a[x].r);
}
int main()
{
	int n;
	cin>>n;
	cin>>root>>a[root].l>>a[root].r;//输入第一个字母，第一个字母比较特殊，所以单独输入
	for(int i=2;i<=n;i++) cin>>ch>>a[ch].l>>a[ch].r;
	dfs(root);
	return 0;
}

代码2：利用ASCII进行存储

#include
using namespace std;
int n;
struct node//定义二叉树结构体
{
	string data;//自身
	int l,r;//左孩子和右孩子的数组下表。
 
}t[1010];
 
void dfs(int k)//先序遍历
{
	cout<//遍历根节点
	if(t[k].l!=0)//如果有左孩子的话，遍历左孩子（未赋值默认为0）
		dfs(t[k].l);
 
	if(t[k].r!=0)//如果有右孩子的话，遍历右孩子
		dfs(t[k].r);
}
int main()
{
	cin>>n;
	int root;//根节点的下标
	for(int i=1;i<=n;i++)
	{
		char a,b,c;
		cin>>a>>b>>c;
		if(i==1)//第一个输入的是根节点，储存其下标，为其在26个字母中的位置
			root=a-'a'+1;
		t[a-'a'+1].data=a;//储存
		//下面为确定父子关系
        if(b!='*')//如果有左儿子
		{
			t[b-'a'+1].data=b;//存储左儿子
			t[a-'a'+1].l=b-'a'+1;//记录左儿子的下标
		}
		if(c!='*')//同上，记录右儿子
		{
			t[c-'a'+1].data=c;
			t[a-'a'+1].r=c-'a'+1;
		}
	}
	dfs(root);//从根节点开始先序遍历
	return 0;
}

代码3：纯dfs（用二维数组进行存储）

#include
using namespace std;
int n;
char a[30][3];
void f(char x)
{
    if(x=='*') return ;
    cout<
    for(int i=1;i<=n;i++)
        if(a[i][0]==x)
        {
            f(a[i][1]);
            f(a[i][2]);
        }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    f(a[1][0]);
    return 0;
}

[模板] 二叉树的先序遍历

代码：和上一题的代码1一样

#include
using namespace std;
int root,m;
struct node
{
	int l,r;
}a[5010];
 
void dfs(int x)
{
	if(x==0) return;
	cout<' ';
	dfs(a[x].l);
	dfs(a[x].r);
 
}
int main()
{
	int n,p;
	cin>>n>>p;
 
	for(int i=1;i<=n;i++)
    {
        cin>>m>>a[m].l>>a[m].r;
    }
	dfs(p);
	return 0;
}

 [模板] 二叉树的中序遍历

代码：和上一题的代码1一样

#include
using namespace std;
int root,m;
struct node
{
	int l,r;
}a[5010];
 
void dfs(int x)
{
	if(x==0) return;
	//cout<
	dfs(a[x].l);
	cout<' ';
	dfs(a[x].r);
 
}
int main()
{
	int n,p;
	cin>>n>>p;
    int root;
	for(int i=1;i<=n;i++)
    {
        cin>>m>>a[m].l>>a[m].r;
    }
	dfs(p);
	return 0;
}

[模板] 二叉树的后序遍历

代码：和上一题的代码1一样

#include
using namespace std;
int root,m;
struct node
{
	int l,r;
}a[5010];
 
void dfs(int x)
{
	if(x==0) return;
	//cout<
	dfs(a[x].l);
	dfs(a[x].r);
    cout<' ';
}
int main()
{
	int n,p;
	cin>>n>>p;
    int root;
	for(int i=1;i<=n;i++)
    {
        cin>>m>>a[m].l>>a[m].r;
    }
	dfs(p);
	return 0;
}

[NOIP2001 普及组] 求先序排列

题解：看博客题解 P1030 【求先序排列】 - sunyufei 的博客 - 洛谷博客 (luogu.com.cn)

代码：

#include
using namespace std;
void beford(string in,string after)
{
    if (in.size())
    {
        char root=after[after.size()-1];
        cout<//找根输出
        int k=in.find(root);
        beford(in.substr(0,k),after.substr(0,k));
        beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；
    }
}
int main()
{
    string inord,aftord;
    cin>>inord>>aftord;//读入
    beford(inord,aftord);
    return 0;
}

美国血统 American Heritage

代码：同上

#include
using namespace std;
void beford(string in,string pre)
{
    if (pre.size())
    {
        char root=pre[0];
        int k=in.find(root);
        pre.erase(pre.begin());
        beford(in.substr(0,k),pre.substr(0,k));
        beford(in.substr(k+1),pre.substr(k));
        cout<
    }
}
int main()
{
    string preord,inord;
    cin>>inord>>preord;
    beford(inord,preord);
    return 0;
}

 [NOIP2004 普及组] FBI 树

主要是二分递归处理

代码1：string()函数强大的用法

#include
using namespace std;
 
char FBI(string t)
{
	if (t.size()>1)
	{
		cout<<FBI(t.substr(0,t.size()/2));
		cout << FBI(t.substr(t.size()/2,t.size()/2));
	}
	if (t==string(t.size(),'0')) return 'B';  //string函数初始化的用法
	if (t==string(t.size(),'1')) return 'I';
	return 'F';
}
 
int main()
{
	int n;
	cin>>n;
	string s;
	cin >> s;
	cout << FBI(s);
	return 0;
}
 

代码2：纯二分

#include
using namespace std;
char s[1025]; //2^10=1024
void work(int l, int r)
{
    int mid=l+r>>1;
    if(l!=r)
    {
        work(l,mid);
        work(mid+1,r);
    }
    int a=0,b=0;
    for (int i=l;i<=r;i++)
        if (s[i]=='0') a++;
        else b++;
 
    if(a&&b) cout<<"F";
    else if (a) cout<<"B";
    else cout<<"I";
}
int main()
{
    int n;
    cin>>n>>s;  //scanf("&s",s+1)下标从s+1开始
    work(0,pow(2,n)-1);
    return 0;
}

图的遍历

代码：

#include
using namespace std;
const int N=1e5+10;
int n,m,a[N];
vector<int> q[N];
void dfs(int x,int d)
{
    if(!a[x])
    {
        a[x]=d;
        for(int i=0;isize();i++)dfs(q[x][i],d);
    }
}
int main()
{
    int u,v;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        q[v].push_back(u);
    }
    for(int i=n;i>0;i--)dfs(i,i);
    for(int i=1;i<=n;i++)cout<' ';
    return 0;
}