codeup 9.2小节——数据结构专题(2)->二叉树的遍历

问题 A: 复原二叉树

时间限制: 1 Sec  内存限制: 32 MB
提交: 333  解决: 202
[提交][状态][讨论版][命题人:外部导入]

题目描述

小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出

对于每组输入，输出对应的二叉树的后续遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
char pre[N],in[N];
struct node{
char data;
node* lchild,*rchild;
};
node* Create(int preL,int preR,int inL,int inR){
if(preL>preR) return NULL;
node* root=new node;
root->data=pre[preL];
int k;
for(k=0;k<=inR;k++){
if(in[k]==pre[preL]) break;
}
int leftNum=k-inL;
root->lchild=Create(preL+1,preL+leftNum,inL,k-1);
root->rchild=Create(preL+leftNum+1,preR,k+1,inR);
return root;
}
void postorder(node* root){
if(root==NULL) return;
postorder(root->lchild);
postorder(root->rchild);
cout<<root->data;
}
int main(){
// freopen("inputa.txt","r",stdin);
node* root;
while(cin>>pre>>in){
int len=strlen(pre);
root=Create(0,len-1,0,len-1);
postorder(root);
cout<<endl;
}
return 0;
}

问题 B: 二叉树

时间限制: 1 Sec  内存限制: 32 MB
提交: 315  解决: 159
[提交][状态][讨论版][命题人:外部导入]

题目描述

    如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

    比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。

输入

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。

输出

 对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

样例输入

3 7
142 6574
2 754
0 0

样例输出

3
63
498

本题直接BFS会超时，其实只用算出该子树有几层就行了

#include<iostream>
using namespace std;
//看子树有几层即可
int main(){
// freopen("inputb.txt","r",stdin);
int m,n;
while(cin>>m>>n&&n){
int t=1,i=1;
while(m*t<=n){
t*=2;
i++;
}
i--;
//此时前i层都是的 且t正好是2^i
//第i层范围起始下标m*2^(i-1)，长度2^(i-1)个
//前i-1层 2^(i-1)-1个
t=2^i
t/2=2^i-1
int sum=t/2-1;
//第i层多少个？ [m*t/2,m*t/2+t/2)内筛选下就行了
for(int j=m*t/2;j<m*t/2+t/2;j++){
if(j<=n) sum++;
else break;
}
cout<<sum<<endl;
}
return 0;
}

化简一下，就成了下面可怕的版本：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int m,n;
while(cin>>m>>n&&n){
int t=1;
while(m*t<=n) t*=2;
cout<<t/2-1+min(n-m*t/2+1,t/2)<<endl;
}
return 0;
}

问题 C: 二叉树遍历

时间限制: 1 Sec  内存限制: 32 MB
提交: 178  解决: 139
[提交][状态][讨论版][命题人:外部导入]

题目描述

二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入

两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出

输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。

样例输入

ABC
CBA
ABCDEFG
DCBAEFG

样例输出

CBA
DCBGFEA

#include<iostream>
#include<string>
using namespace std;
string pre,in;
struct node{
char data;
node *lchild,*rchild;
};
node* Create(int preL,int preR,int inL,int inR){
if(preL>preR) return NULL;
node* root=new node;
root->data=pre[preL];
int k=0;
while(in[k]!=pre[preL]) k++;
int leftNum=k-inL;
root->lchild=Create(preL+1,preL+leftNum,inL,k-1);
root->rchild=Create(preL+leftNum+1,preR,k+1,inR);
return root;
}
void postOrder(node* root){
if(root==NULL) return;
postOrder(root->lchild);
postOrder(root->rchild);
cout<<root->data;
}
int main(){
// freopen("inputc.txt","r",stdin);
while(cin>>pre>>in){
postOrder(Create(0,pre.length()-1,0,in.length()-1));
cout<<endl;
}
return 0;
}

问题 D: 二叉树遍历

时间限制: 1 Sec  内存限制: 32 MB
提交: 212  解决: 126
[提交][状态][讨论版][命题人:外部导入]

题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：
ABC##DE#G##F###
其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入

输入包括1行字符串，长度不超过100。

输出

可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。

样例输入

a#b#cdef#####
a##

样例输出

a b f e d c
a 

#include<iostream>
using namespace std;
bool first;
char c;
struct node{
char data;
node *lchild,*rchild;
};
void create(node* &root){
if(!first) cin>>c;
else first=false;
if(c=='#') root=NULL;
else{
root=new node;//分配内存
root->data=c;
create(root->lchild);
create(root->rchild);
}
}
void inorder(node* root){
if(root==NULL) return;
inorder(root->lchild);
cout<<root->data<<" ";
inorder(root->rchild);
}
int main(){
// freopen("inputd.txt","r",stdin);
while(cin>>c){
node* root;
first=true;
create(root);
inorder(root);
cout<<endl;
}
return 0;
}

最后

以上就是认真往事为你收集整理的codeup 9.2小节——数据结构专题(2)->二叉树的遍历的全部内容，希望文章能够帮你解决codeup 9.2小节——数据结构专题(2)->二叉树的遍历所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。