二叉树系列题目

1.利用二叉树性质解题.

UVA 679 - Dropping Balls

有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右 编号为1, 2, 3,…, 2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关， 初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个内结点 时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点，如图6-2所示。

一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？输入叶子深度D和 小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D≤20。 输入最多包含1000组数据。

方法1：模拟但会TLE,对 I 个球进行模拟下落,到落到某一结点就开关变换.数据较大时会有 2^20 * 20
方法2：利用奇偶性+递归思想.对前两个进行分析：第一个往左,第二个显然往右. 分析可得 如果 I 为 偶数 则最后一个球为往右走的 第 I/2个 ,反之为 往左走的 第（I+1) /2 。
然后再将当前结点作为根.继续判断是往左还是往右.

模拟TLE代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int vis[N];
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(vis,0,sizeof vis);
		int d,n,k=1;
		cin>>d>>n;
		while(n--){
			k=1;
			for(int i=1;i<d;i++)
			{
				vis[k]=!vis[k]; //当球到某个点 该点开关改变.如果此时是开说明之前是关则往左走,反之往右走. 
				k = vis[k]?2*k:2*k+1;
			}
		}
		cout<<k<<endl;
	}
	return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int d,n,k=1;
		cin>>d>>n;
		d--;
		while(d--){
			if(n&1) k*=2,n=(n+1)/2;
			else k=k*2+1,n>>=1; 
		}
		cout<<k<<endl;
	}
	return 0;
}

总结：本题是一棵完全二叉树.利用了根结点（从1开始编号 ）的左儿子为 2n ,右儿子为 2n+1 这一性质。加上奇偶性分析得出规律大大减少时间。另外从0开始编号的完全二叉树 左儿子为 2n+1 ,右儿子为 2n +2

二叉树的遍历.

这里主要有BFS和DFS.我们来主要来谈谈DFS.

DFS：分为三种：先序，后序，中序遍历。先序顺序：根左右。后序顺序：左右根。中序顺序：左根右
相关的性质：已知先序和中序可以确定一棵树。已知后序和中序也可以确定一棵树。但是已知先序和后序不一定能确定一棵树。下面上几个题目。

题型1：给两段字符串，分别为中序和先序，或者分别为中序和后序。让你打印后序（先序）。
主要思想：已知先序或后序可以确定根的位置。然后在中序中找到根的位置。根的左边即为左子树，右边为右子树。
再分别对左右子树进行递归搜索。即可以得到结果。下面上代码。

已知中序和先序，求后序

#include<bits/stdc++.h>
using namespace std;
void dfs(string a,string b){//a:中序字符串 b：先序字符串. 
	if(a.size()>0)
	{
		char c=b[0];//根 
		int k=a.find(c);//根在中序的位置. 
		dfs(a.substr(0,k),b.substr(1,k)); //递归搜索左子树 
		dfs(a.substr(k+1),b.substr(k+1,a.size()-k-1));//递归搜索右子树 
		cout<<c; //最后打印根. 满足左右根的顺序 即为后序遍历. 
	}
}
int main(){  //求后序. 
	string a,b;
	cin>>a>>b;
	dfs(a,b);
	return 0;
}

已知中序和后序，求先序

#include<iostream>
#include<string>
using namespace std;
void dfs(string a,string b){//a：中序字符串 b:后序字符串 
	 if(a.size()>0) //当子树存在时. 
	 {
	 	char c=b[b.size()-1]; //根为后序的最后位置 
		cout<<c;//先输出根 
		int pos=a.find(c);//根在中序的位置 pos也是左子树的结点数. 
		dfs(a.substr(0,pos),b.substr(0,pos));//dfs 左子树 
		dfs(a.substr(pos+1),b.substr(pos,a.size()-pos-1));	// dfs 右子树 
	 }  //满足根左右的顺序. 
}
int main(){
	string a,b;
	cin>>a>>b;
	dfs(a,b);
	return 0;
}