【c++提高1】二叉树&二叉堆（万字总结）-创新互联

方法1：
① 找根：基于先序序列的首元素即是根，找出树的根。
② 划分子问题：基于中序序列、根和先序序列，划分出左右子树的中序和先序序列。
③ 治理子问题：基于左右子树的中序和先序序列，递归的处理左右子树。
④ 合并：将左右子树根节点的存储位置，合并为原树的左右子树。
⑤ 后序遍历：基于构建出的树，进行后序遍历，输出后序序列。

struct Node{char dat;
	int l,r;
}tr[N];
int tot;
string in,pr;
int build(int ib,int ie,int pb,int pe){int r=++tot;
	tr[r].dat=pr[pb];
	int rps=in.find(tr[r].dat);
	int len=rps-ib;
	if(rps>ib)tr[r].l=build(ib,rps-1,pb+1,pb+len);
	if(rpsif(!r)return;
	ODR(tr[r].l);
	ODR(tr[r].r);
	cout<cin>>in>>pr;
	int r=build(0,in.size()-1,0,pr.size()-1);
	ODR(r);
}

方法2：
在算法1处理过程中，找到根后先储存，当递归处理完左右子树后，再输出根。

string in,pr;
void solve(int ib,int ie,int pb,int pe){char r=pr[pb];
	int rps=in.find(r);
	int len=rps-ib;
	if(rps>ib)solve(ib,rps-1,pb+1,rp+len);
	if(rpscin>>in>>pr;
	solve(0,in.size()-1,0,pr.size()-1);
}

① 找根：基于先序序列的首元素即是根，找出树的根。
② 划分子问题：基于中序序列、根和先序序列，划分出左右子树的中序和先序序列。
③ 治理子问题：基于左右子树的中序和先序序列，递归的处理左右子树。
④ 合并：将左右子树根节点的存储位置，合并为原树的左右子树。
⑤ 层次遍历：基于构建出的树，进行层次遍历，输出层次序列。

struct Node{char dat;
	int l,r;
}tr[N];
int tot;
string in,pr;
int build(int ib,int ie,int pb,int pe){int r=++tot;
	tr[r].dat=pr[pb];
	int rps=in.find(tr[r].dat);
	int len=rps-ib;
	if(rps>ib)tr[r].l=build(ib,rps-1,pb+1,pb+len);
	if(rpscout<queueq;q.push(r);
	Prnt(r);
	while(!q.empty()){int n=q.ront();q.pop();
		if(tr[n].l){	Prnt(tr[n].l);
			q.push(tr[n].l);
		}
		if(tr[n].r){	Prnt(tr[n].r);
			q.push(tr[n].r);
		}
	}
}
int main(){cin>>in>>pr;
	int r=build(0,in.size()-1,0,pr.size()-1);
	bfs(r);
}

① 找根：基于层次遍历的首元素是整棵树的根，找出树根。
② 划分子问题：基于中序序列和根可以划分出左右子树的中序序列。

通过中序序列可以得到左子树和右子树各自所包含的所有节点，左子树的所有节点中最先
出现在层次遍历序列中的节点是左子树的根，同理可得右子树的根。

string in,l;
int fr(int ib,int ie){for(int i=0;iint r=fr(ib,ie);cout<ib)solve(ib,r-1);
	if(rcin>>in>>l;solve(0,in.size()-1);
}

有一棵二叉树，大深度为D，且所有叶子的深度都相同。所有节点从上到下，从左到右的编号为1,2,3...,2^D-1.

在结点1处放一个小球，它会往下落，每个内结点上都有一个开关（开关的状态是false或true），初始时全部是false状态，当每次有小球落到这个结点上时，开关的状态被改变。

当小球达到一个内结点时，如果该结点的开关状态是关闭的，则小球往左走，否则往右走，直到走到叶子结点。

如下图所示：



表示结点编号为1,2,3...15，大深度为4的完全二叉树，由于初始时，所有的结点的开关状态是false，所以第一个球下落时经过结点1 2 4最终落在结点8上，第二个球下落时经过结点1 3 6最终落在结点12上，第三个球下落时，经过结点1 2 5最终落在结点10上。

现在给出多组测试数据，最多包含1000组，每组测试数据两个值。第一个值是D，表示二叉树的大深度。第二个值是L，表示小球的个数L。

假设I不超过整棵树的叶子个数，2≤D≤20，and 1≤L≤5000

编写一个程序，计算出小球从节点1处依次开始下落，最后一个小球L将会落下哪里？输出第L个小球最后所在的叶子编号。

输入格式
第一行一个整数n，表示测试数据的组数

接下来n行，每行两个整数分别表示二叉树的深度D和小球的个数L，用空格隔开

最后一行，“-1”，表示测试数据结束

输出格式
输出n行，分别表示每组测试数据，第L个小球最后所在的叶子编号

输入输出样列
输入样例1：
5
4 2
3 4
10 1
2 2
8 128
-1
输出样例1：
12
7
512
3
255

这道题就是个大大大大大氵题，直接按照题目的思路模拟即可。

#include#define debug(x) cout<< #x<< '='<< x<< '\n';
using namespace std;
bool tr[1000010]; //lson=t*2,rson=t*2+1
int T;
void slove(){memset(tr,0,sizeof(tr));
	int D,L;scanf("%d%d",&D,&L);
	int a=(1<int now=1;
		while(now	int t=now;
			if(!tr[now])now=now<<1;
			else now=now<<1|1;
			tr[t]^=1;
		}x=now;
	}
	printf("%d\n",x);
}
int main () {scanf("%d",&T);
	while(T--)slove();
	return 0;
}

农夫约翰非常认真地对待他的奶牛们的血统.然而他不是一个真正优秀的记帐员.他把他的奶牛们的家谱作成二叉树,并且把二叉树以更线性的”树的中序遍历“和”树的前序遍历“的符号加以记录而不是用图形的方法.

你的任务是在被给予奶牛家谱的”树中序遍历“和”树前序遍历“的符号后,创建奶牛家谱的”树的后序遍历“的符号。每一头奶牛的姓名被译为一个唯一的字母. （你可能已经知道你可以在知道树的两种遍历以后可以经常地重建这棵树.）显然,这里的树不会有多余 26 个的顶点.

这是在样例输入和 样例输出中的树的图形表达方式：

                 C
                /   \
               /     \
              B       G
             / \     /
            A   D   H
               / \
              E   F
树的中序遍历是按照左子树，根，右子树的顺序访问节点。

树的前序遍历是按照根，左子树，右子树的顺序访问节点。

树的后序遍历是按照左子树，右子树，根的顺序访问节点。

输入格式
第一行: 树的中序遍历

第二行: 同样的树的前序遍历

输出格式
单独的一行表示该树的后序遍历.

输入输出样列
输入样例1：
ABEDFCHG
CBADEFGH
输出样例1：
AEFDBHGC

模板题啊。

#include#define debug(x) cout<< #x<< '='<< x<< '\n';
using namespace std;
string p, i;
void build (string p, string i) {if (p.empty ()) return;
    char r = p[0];
    int k = i.find (r);
    p.erase (p.begin ());
    string l1 = p.substr (0, k);
    string r1 = p.substr (k);
    string l2 = i.substr (0, k);
    string r2 = i.substr (k + 1);
    build (l1, l2);
    build (r1, r2);
    cout<< r;
}
int main () {cin >>i >>p;
    build (p, i);
	return 0;
}

二叉堆使用完全二叉树实现，分为大根堆和小根堆两种：
大根堆：任意一个分支结点的值都大于或者等于其子节点的值。
小根堆：任意一个分支结点的值都小于或者等于其子节点的值。

插入操作要求在不影响二叉堆性质的前提下，在二叉堆中添加一个新元素。
性质1：完全二叉树结构，插入新元素后需要继续保持完全二叉树的结构。
性质2：任何一个分支节点的值都大于等于(大根堆)或小于等于(小根堆)其子节点的值。

① 堆尾插入：每次在堆尾插入新元素（确保插入后仍然是完全二叉树结构）。
② 向上调整（和父节点比较），将新元素调整到合适的位置。

删顶操作要求在不影响二叉堆性质的前提下，将堆顶元素删除。
性质1：完全二叉树结构，删除堆顶后需要继续保持完全二叉树的结构。
性质2：任何一个分支节点的值都大于等于(大根堆)或小于等于(小根堆)其子节点的值。

① 将堆顶赋值为堆尾元素的值，接着删除堆尾节点。（保持完全二叉树结构）
② 向下调整(和孩子节点比较)，堆顶元素调整到合适的位置。

插入操作：堆尾添加元素时间复杂度O(1)，向上调整的次数大为完全二叉树的层数：
log2 n + 1，故插入操作的时间复杂度为：O(log2 n )。
删顶操作：堆顶复制和堆尾删除时间复杂度O(1)， 向下调整的次数大为完全二叉树
的层数： log2 n + 1，故删顶操作的时间复杂度为：O(log2 n )。

int heap[N],tt;
bool empty(){return !tt;}
int sz(){return tt;}
int tp(){return heap[1];}
int psh(int v){heap[++tt]=v;
	int x=tt;
	while(x>1&&heap[x]>1]){swap(heap[x>>1],heap[x]);
		x>>=1;
	}
}
void pop(){heap[1]=heap[tt--];
	int x=1,p=x<<1;
	while(p<=tt){if(p+1<=tt&&heap[p+1]

priority_queue,greater>qg;
priority_queue,less>ql;

q.push(x);

q.pop();

struct Node{int a;
	bool operator<(const Node&W)const{return a>W.a;
	}
}
priority_queue,less>q;

struct Node{int a;
	bool operator<(const Node&W)const{return a,greater>q;

有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。

输入格式
第一行一个正整数N；

第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9;（i和i+1表示序列的下标）

第三行N个整数Bi, 满足Bi<=Bi+1且Bi<=10^9。（i和i+1表示序列的下标）

输出格式
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。

输入输出样列
输入样例1：
3
2 6 6
1 4 8
输出样例1：
3 6 7
说明
【数据规模】

对于50%的数据中，满足1<=N<=1000；

对于100%的数据中，满足1<=N<=100000。

#includeusing namespace std;
typedef pairPII; 
const int N=1e5+10;
int n,a[N],b[N],t[N];
priority_queue,greater>q;
int main(){cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)q.push(make_pair(a[1]+b[i],i)),t[i]=1;
	for(int i=1;i<=n;i++){cout<