1.廣度優先遍歷

2.深度優先遍歷

1.前序遍歷

根結點--左子樹--右子樹

void pre(int p){
	printf("%d\n",p);
    if(tree[p].l)pre(tree[p].l);
    if(tree[p].r)pre(tree[p].r);
}

2.中序遍歷

左子樹--根結點--右子樹

void in(int p){
	if(tree[p].l)in(tree[p].l);
    printf("%d\n",p);
    if(tree[p].r)in(tree[p].r);
}

3.后序遍歷

左子樹--右子樹--根結點

void post(int p){
	if(tree[p].l)post(tree[p].l);
    if(tree[p].r)post(tree[p].r);
    printf("%d\n",p);
}

3.已知先中求后

P1827 [USACO3.4] 美國血統 American Heritage

#include<bits/stdc++.h>
using namespace std;
string a,b;
void dfs(int l,int r,int ql,int qr){
	for(int i=ql;i<=qr;i++){
		if(a[i]==b[l]){
			dfs(l+1,l+i-ql,ql,i-1);  //i-ql表示左子樹長度
			dfs(l+i-ql+1,r,i+1,qr);
			cout<<b[l];
		}
	}
}
int main(){
	cin>>a>>b;
	dfs(0,a.length()-1,0,a.length()-1);
	return 0;
}

4.已知中后求先

P1030 [NOIP 2001 普及組] 求先序排列

反過來即可

#include<bits/stdc++.h>
using namespace std;
string a,b;
void dfs(int l,int r,int ql,int qr){
	for(int i=qr;i>=ql;i--){
		if(a[i]==b[r]){
			cout<<b[r];
			dfs(l,r-(qr-i)-1,ql,i-1);  
			dfs(r+i-qr,r-1,i+1,qr);
			 
		}
	}
}
int main(){
	cin>>a>>b;
	dfs(0,a.length()-1,0,a.length()-1);
	return 0;
}

5.已知先后求中的可能個數

P1229 遍歷問題

有n個只有一個子樹的結點就有2^n種可能

輸入例子：

前：abc

后：cba

若兩個字母在前序與后序中位置相鄰且相反，那便是一個單子樹結點

因為前序是根左右

后序是左右根

若存在兩個子樹

那么相鄰一定不一樣

#include<bits/stdc++.h>
using namespace std;
string a,b; 
long long ans;
int main(){
	cin>>a>>b;
	int n=a.length();
	for(int i=0;i<=n-2;i++){
		for(int j=0;j<=n-1;j++){
			if(a[i]==b[j]&&a[i+1]==b[j-1])ans++;
		}
	}
	cout<<pow(2,ans);
	return 0;
}