【數(shù)據(jù)結(jié)構(gòu)1-2】二叉樹 - 題單 - 洛谷

?

【數(shù)據(jù)結(jié)構(gòu)】day2-樹_J嬌嬌_的博客-CSDN博客

上學(xué)時的作業(yè)

P1827 [USACO3.4] 美國血統(tǒng) American Heritage

二叉樹特點寫法（非二叉樹）

截取字符串寫法

#include<string>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
string pre,in;
void work(string pre,string inor)
{if(pre.empty())return;char root=pre[0];int k=inor.find(root);pre.erase(pre.begin());string leftpre=pre.substr(0,k);//從0開始切割k個 0 - k-1string rightpre=pre.substr(k);//k到最后 string leftinor=inor.substr(0,k);string rightinor=inor.substr(k+1);work(leftpre,leftinor);work(rightpre,rightinor);printf("%c",root);//因為要輸出后序序列，所以是左右根
}
int main()
{cin>>in>>pre;work(pre,in);putchar('\n');return 0;
}

位置標記寫法

//一定要看清題目中為先中序，再是前序
#include <bits/stdc++.h>  //萬能頭文件
using namespace std;
string a,b;   //把中前遍歷當(dāng)做字符串輸入
void houxu(int x,int y,int p,int q) {  //x~y為前序遍歷 p~q為中序遍歷if(x>y||p>q) return ;//規(guī)定邊界條件else {int i=b.find(a[x]);   //利用根左右的特性來在中序隊列中查找houxu(x+1,x+i-p,p,i-1);      //遞歸左子樹houxu(x+i-p+1,y,i+1,q);    //遞歸右子樹cout<<a[x];
}
}
int main() {cin>>b>>a;//反一下輸入int l=a.length()-1;//因為是0開始，所以要減一houxu(0,l,0,l);//遞歸return 0;
}

二叉樹寫法

#include<bits/stdc++.h>
using namespace std;
typedef struct tree
{char ch;struct tree *Lchild;struct tree *Rchild;
}Nodetree,*Betree;
void CreateTree(Betree *r,char Pre[],char In[],int prel,int prer,int il,int ir)//中序數(shù)組+后序數(shù)組遞歸創(chuàng)建二叉鏈表
{if(il>ir)*r=NULL;else{*r=new Nodetree;(*r)->ch=Pre[prel];int mid=il;while(In[mid]!=Pre[prel])//定位mid{mid++;}CreateTree(&((*r)->Lchild),Pre,In,prel+1,prel+mid-il,il,mid-1);CreateTree(&((*r)->Rchild),Pre,In,prel+mid-il+1,prer,mid+1,ir);}
}
void print(Betree r)
{if(r==NULL)return;else{print(r->Lchild);print(r->Rchild);cout<<r->ch;}
}
int main()
{char Pre[10010],In[10010];cin>>In>>Pre;Betree r;r=new Nodetree;CreateTree(&r,Pre,In,0,strlen(Pre)-1,0,strlen(In)-1);print(r);
}

前序+中序->后序

 CreateTree(&((*r)->Lchild),Pre,In,prel+1,prel+mid-il,il,mid-1);CreateTree(&((*r)->Rchild),Pre,In,prel+mid-il+1,prer,mid+1,ir);

中序+后序->前序

CreateTree(&((*r)->Lchild),Last,In,LastL,LastL+mid-il-1,il,mid-1);
CreateTree(&((*r)->Rchild),Last,In,LastL+mid-il,LastR-1,mid+1,ir);

P1305 新二叉樹

#include<iostream>
#include<string>
#include<cstring>//不加會CE
using namespace std;
int n;
string s;
int main()
{cin>>n;cin>>s;for(int i=2;i<=n;++i)//由于第一個為原串，所以單獨輸入{string ss;cin>>ss;int x=s.find(ss[0]);//找到這個子樹的根節(jié)點在原串中的位置s.erase(x,1);//清除根節(jié)點s.insert(x,ss);//加入子樹}for(int i=0;i<s.size();++i)if(s[i]!='*') cout<<s[i];//不輸出空節(jié)點else continue;
}

#include<iostream> 
using namespace std;
struct programmer
{char lc;char rc;
}lt[130];//數(shù)組，這個十分重要，一會兒輸入字符的時候還要用這個串起來
//其實真正起作用的只有l(wèi)t[73]~lt[122],說這個是為了防止一些人不多想，方便理解的
char h,h1;//儲存一會兒要輸入的節(jié)點，多定義一個h1是為了一會兒將根節(jié)點保留下來先代入函數(shù)
void sm(char x)
{if(x=='*') return;cout<<x;sm(lt[x].lc);sm(lt[x].rc);
}
int main()
{int n;cin>>n;cin>>h1;//根 cin>>lt[h1].lc;//左 cin>>lt[h1].rc;//右 for(int i=2;i<=n;i++){cin>>h;cin>>lt[h].lc;cin>>lt[h].rc;}sm(h1);return 0;
}