博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【1710】Binary Tree Traversals ( HDUOJ)
阅读量:7199 次
发布时间:2019-06-29

本文共 2637 字,大约阅读时间需要 8 分钟。



                           Binary Tree Traversals

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3357    Accepted Submission(s): 1508
Problem Description
A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.
In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.
In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.
In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.
Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.
 
Input
The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.
 
Output
For each test case print a single line specifying the corresponding postorder sequence.
 
Sample Input
 
9 1 2 4 7 3 5 8 9 6 4 7 2 1 8 5 9 3 6
 
Sample Output
 
7 4 2 8 9 5 6 3 1
 
#include 
#include
#include
struct node{
int data; struct node *left,*right;};struct node *creat(int n,int *str1,int *str2){
struct node *root; int *p; if(n==0) return NULL; root=(struct node *)malloc(sizeof(struct node )); root->data=str1[0]; for(p=str2;p!='\0';p++) {
if(*p==str1[0]) break; } int t=p-str2; root->left=creat(t,str1+1,str2); root->right=creat(n-t-1,str1+t+1,p+1); return root;};int houxu(struct node *root,int n){
if(root==NULL) return 0; houxu(root->left,n+1); houxu(root->right,n+1); if(n==0) printf("%d\n",root->data); else printf("%d ",root->data);}int main(){
int n,i; int str1[1100],str2[1100]; struct node *root; while(~scanf("%d",&n)) {
root=(struct node *)malloc(sizeof(struct node )); for(i=0;i

转载于:https://www.cnblogs.com/jiangyongy/p/3971660.html

你可能感兴趣的文章
《从面试题来看源码》,单参数,多参数,如何正确使用@Param
查看>>
《JavaScript设计模式》学习日志
查看>>
MySql 建表、添加字段、修改字段、添加索引SQL语句写法
查看>>
Core Bluetooth框架之三:最佳实践
查看>>
Gson序列化时@SerializedName的使用
查看>>
windows上pip install 报编码错误
查看>>
boost asio学习笔记 [1] - 同步通讯
查看>>
什么是BMC商业模式?
查看>>
不同浏览器中单选框和文字对齐的兼容
查看>>
Python 浮点数在列表中排序的问题
查看>>
一个失业三年后,又重新找回自信的小伙靠的是什么?
查看>>
JFinal学习-Excel导出
查看>>
linuxbridge 小贴士
查看>>
红旗inWise操作系统V8.0发布了!!!
查看>>
tiles2
查看>>
vi 合并多个文件
查看>>
切换npm源
查看>>
细数JDK里的设计模式
查看>>
Oracle中增加Split函数
查看>>
nagios 报警频率控制
查看>>