【c++提高1】二叉樹&二叉堆（萬字總結(jié)）-創(chuàng)新互聯(lián)

方法1：
① 找根：基于先序序列的首元素即是根，找出樹的根。
② 劃分子問題：基于中序序列、根和先序序列，劃分出左右子樹的中序和先序序列。
③ 治理子問題：基于左右子樹的中序和先序序列，遞歸的處理左右子樹。
④ 合并：將左右子樹根節(jié)點的存儲位置，合并為原樹的左右子樹。
⑤ 后序遍歷：基于構(gòu)建出的樹，進行后序遍歷，輸出后序序列。

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);
}

① 找根：基于先序序列的首元素即是根，找出樹的根。
② 劃分子問題：基于中序序列、根和先序序列，劃分出左右子樹的中序和先序序列。
③ 治理子問題：基于左右子樹的中序和先序序列，遞歸的處理左右子樹。
④ 合并：將左右子樹根節(jié)點的存儲位置，合并為原樹的左右子樹。
⑤ 層次遍歷：基于構(gòu)建出的樹，進行層次遍歷，輸出層次序列。

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);
}

通過中序序列可以得到左子樹和右子樹各自所包含的所有節(jié)點，左子樹的所有節(jié)點中最先
出現(xiàn)在層次遍歷序列中的節(jié)點是左子樹的根，同理可得右子樹的根。

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，且所有葉子的深度都相同。所有節(jié)點從上到下，從左到右的編號為1,2,3...,2^D-1.

在結(jié)點1處放一個小球，它會往下落，每個內(nèi)結(jié)點上都有一個開關(guān)（開關(guān)的狀態(tài)是false或true），初始時全部是false狀態(tài)，當每次有小球落到這個結(jié)點上時，開關(guān)的狀態(tài)被改變。

當小球達到一個內(nèi)結(jié)點時，如果該結(jié)點的開關(guān)狀態(tài)是關(guān)閉的，則小球往左走，否則往右走，直到走到葉子結(jié)點。

如下圖所示：



表示結(jié)點編號為1,2,3...15，大深度為4的完全二叉樹，由于初始時，所有的結(jié)點的開關(guān)狀態(tài)是false，所以第一個球下落時經(jīng)過結(jié)點1 2 4最終落在結(jié)點8上，第二個球下落時經(jīng)過結(jié)點1 3 6最終落在結(jié)點12上，第三個球下落時，經(jīng)過結(jié)點1 2 5最終落在結(jié)點10上。

現(xiàn)在給出多組測試數(shù)據(jù)，最多包含1000組，每組測試數(shù)據(jù)兩個值。第一個值是D，表示二叉樹的大深度。第二個值是L，表示小球的個數(shù)L。

假設(shè)I不超過整棵樹的葉子個數(shù)，2≤D≤20，and 1≤L≤5000

編寫一個程序，計算出小球從節(jié)點1處依次開始下落，最后一個小球L將會落下哪里？輸出第L個小球最后所在的葉子編號。

輸入格式
第一行一個整數(shù)n，表示測試數(shù)據(jù)的組數(shù)

接下來n行，每行兩個整數(shù)分別表示二叉樹的深度D和小球的個數(shù)L，用空格隔開

最后一行，“-1”，表示測試數(shù)據(jù)結(jié)束

輸出格式
輸出n行，分別表示每組測試數(shù)據(jù)，第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;
}

農(nóng)夫約翰非常認真地對待他的奶牛們的血統(tǒng).然而他不是一個真正優(yōu)秀的記帳員.他把他的奶牛們的家譜作成二叉樹,并且把二叉樹以更線性的”樹的中序遍歷“和”樹的前序遍歷“的符號加以記錄而不是用圖形的方法.

你的任務(wù)是在被給予奶牛家譜的”樹中序遍歷“和”樹前序遍歷“的符號后,創(chuàng)建奶牛家譜的”樹的后序遍歷“的符號。每一頭奶牛的姓名被譯為一個唯一的字母. （你可能已經(jīng)知道你可以在知道樹的兩種遍歷以后可以經(jīng)常地重建這棵樹.）顯然,這里的樹不會有多余 26 個的頂點.

這是在樣例輸入和 樣例輸出中的樹的圖形表達方式：

                 C
                /   \
               /     \
              B       G
             / \     /
            A   D   H
               / \
              E   F
樹的中序遍歷是按照左子樹，根，右子樹的順序訪問節(jié)點。

樹的前序遍歷是按照根，左子樹，右子樹的順序訪問節(jié)點。

樹的后序遍歷是按照左子樹，右子樹，根的順序訪問節(jié)點。

輸入格式
第一行: 樹的中序遍歷

第二行: 同樣的樹的前序遍歷

輸出格式
單獨的一行表示該樹的后序遍歷.

輸入輸出樣列
輸入樣例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;
}

二叉堆使用完全二叉樹實現(xiàn)，分為大根堆和小根堆兩種：
大根堆：任意一個分支結(jié)點的值都大于或者等于其子節(jié)點的值。
小根堆：任意一個分支結(jié)點的值都小于或者等于其子節(jié)點的值。

插入操作要求在不影響二叉堆性質(zhì)的前提下，在二叉堆中添加一個新元素。
性質(zhì)1：完全二叉樹結(jié)構(gòu)，插入新元素后需要繼續(xù)保持完全二叉樹的結(jié)構(gòu)。
性質(zhì)2：任何一個分支節(jié)點的值都大于等于(大根堆)或小于等于(小根堆)其子節(jié)點的值。

① 堆尾插入：每次在堆尾插入新元素（確保插入后仍然是完全二叉樹結(jié)構(gòu)）。
② 向上調(diào)整（和父節(jié)點比較），將新元素調(diào)整到合適的位置。

刪頂操作要求在不影響二叉堆性質(zhì)的前提下，將堆頂元素刪除。
性質(zhì)1：完全二叉樹結(jié)構(gòu)，刪除堆頂后需要繼續(xù)保持完全二叉樹的結(jié)構(gòu)。
性質(zhì)2：任何一個分支節(jié)點的值都大于等于(大根堆)或小于等于(小根堆)其子節(jié)點的值。

① 將堆頂賦值為堆尾元素的值，接著刪除堆尾節(jié)點。（保持完全二叉樹結(jié)構(gòu)）
② 向下調(diào)整(和孩子節(jié)點比較)，堆頂元素調(diào)整到合適的位置。

插入操作：堆尾添加元素時間復(fù)雜度O(1)，向上調(diào)整的次數(shù)大為完全二叉樹的層數(shù)：
log2 n + 1，故插入操作的時間復(fù)雜度為：O(log2 n )。
刪頂操作：堆頂復(fù)制和堆尾刪除時間復(fù)雜度O(1)， 向下調(diào)整的次數(shù)大為完全二叉樹
的層數(shù)： log2 n + 1，故刪頂操作的時間復(fù)雜度為：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中各取一個數(shù)相加可以得到N^2個和，求這N^2個和中最小的N個。

輸入格式
第一行一個正整數(shù)N；

第二行N個整數(shù)Ai,滿足Ai<=Ai+1且Ai<=10^9;（i和i+1表示序列的下標）

第三行N個整數(shù)Bi, 滿足Bi<=Bi+1且Bi<=10^9。（i和i+1表示序列的下標）

輸出格式
輸出僅一行，包含N個整數(shù)，從小到大輸出這N個最小的和，相鄰數(shù)字之間用空格隔開。

輸入輸出樣列
輸入樣例1：
3
2 6 6
1 4 8
輸出樣例1：
3 6 7
說明
【數(shù)據(jù)規(guī)模】

對于50%的數(shù)據(jù)中，滿足1<=N<=1000；

對于100%的數(shù)據(jù)中，滿足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<