【数据结构1-2】二叉树 - 题单 - 洛谷

 

【数据结构】day2-树_J娇娇_的博客-CSDN博客

上学时的作业

P1827 [USACO3.4] 美国血统 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;   //把中前遍历当做字符串输入
void houxu(int x,int y,int p,int q) {  //x~y为前序遍历 p~q为中序遍历if(x>y||p>q) return ;//规定边界条件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)//中序数组+后序数组递归创建二叉链表
{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]);//找到这个子树的根节点在原串中的位置s.erase(x,1);//清除根节点s.insert(x,ss);//加入子树}for(int i=0;i<s.size();++i)if(s[i]!='*') cout<<s[i];//不输出空节点else continue;
}

#include<iostream> 
using namespace std;
struct programmer
{char lc;char rc;
}lt[130];//数组，这个十分重要，一会儿输入字符的时候还要用这个串起来
//其实真正起作用的只有lt[73]~lt[122],说这个是为了防止一些人不多想，方便理解的
char h,h1;//储存一会儿要输入的节点，多定义一个h1是为了一会儿将根节点保留下来先代入函数
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;
}