链接:http://pat.zju.edu.cn/contests/pat-a-practise/1020
题意:给定二叉树的后序遍历和中序遍历,求层序遍历。
分析:根据后续遍历和中序遍历,可以递归的构建树,建好树之后利用queue层序遍历。
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct Node{ int val; struct Node* left; struct Node* right; }Node; int post[35]; int in[35]; int n; Node* root; int* findRoot(int num){ int i; for(i=0;i<n;i++) { if(in[i]==num) return &in[i]; } return NULL; } Node* build(int n,int *post,int *in){ if(n<=0) return NULL; Node* root=(Node*)malloc(sizeof(Node)); root->val=post[n-1]; int p=findRoot(post[n-1])-in; root->left=build(p,post,in); root->right=build(n-1-p,post+p,in+p+1); return root; } int main(){ // freopen("in.txt","r",stdin); scanf("%d",&n); int i; for(i=0;i<n;i++) scanf("%d",&post[i]); for(i=0;i<n;i++) scanf("%d",&in[i]); root=build(n,post,in); Node queue[1000]; int front=0; int rear=0; memcpy(&queue[rear++],root,sizeof(Node)); Node* cur; int count=n; while(front<rear){ cur=&queue[front++]; printf("%d",cur->val); if(--count) printf(" "); if(cur->left) memcpy(&queue[rear++],cur->left,sizeof(Node)); if(cur->right) memcpy(&queue[rear++],cur->right,sizeof(Node)); } printf("\n"); return 0; }
相关推荐
给你inorder的栈操作步骤,让你写出postorder后的序列。 http://blog.csdn.net/xkzju2010/article/details/46325457
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the ...
思路后序和中序构造二叉树唯一一个注意的地方,在注释中。// 注意这里是pos-right_num-1而不是想当然的pos_inr-1,这两个的位置并不一定对应。
PTA 7-1 Tree Traversals Again
3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 I 3.7.2 Postorder . . . . . . . . . . . . . . ....
25 IsReadOnly .......................................................................................................................................... 25 Doubly Linked List ...........................
c (数据结构) AVLTree Graph Heap Tree Traversals Again 计算器_栈 二叉排序树 二分法查找 线性表 等 值得学习
cd BinaryTree遍历 npm安装 npm开始 浏览到htpp:// localhost:3000 登陆页面 包含一棵静态树。 用户可以选择任何遍历(顺序,前顺序或后顺序),遍历的结果将显示在树下。 您也可以同时签出算法。 预购遍历 后...
Binary_tree_order_traversals 在该项目中,我们可以看到树的顺序,前顺序和后顺序。 该程序将打开一个菜单,并允许用户通过一个接一个地导入数据(节点)来创建他/她的树: '''0。退出 插入 展示 搜索 为了 预购...
* Traversals: Traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network...
Breadth first search algorithm in C. Example are countries in Romania traversals.
In debug build this will cause full traversals of the tree when the validate is called on insert and remove. Useful for debugging but very slow.
Tree traversals, search Stack Queue Graph traversals(BFS, DFS) 最短路径数学题 从之前的采访中吸取的错误和教训: 调度: 更加注意时间安排,在公司现场面试前保持2-3天的开放时间。 除非非常关键,否则不要立即...
Tree Serialization, Finding the Top k Elements of Data Streams, MapReduce, Partial Sorting, the Skyline Problem, DFS, BFS and Topological Sorting of Dags, the Alternative Alphabet and the Phone Words...
Grok and perform effective ...Chapter 8: Traversals – Mapping/Filtering/Folding/Reducing Chapter 9: Higher Order Functions Chapter 10: Actors and Message Passing Chapter 11: It's a Paradigm Shift
Before all : Pure-FTPd was designed on Unix and for Unix. The Windows port has been done because some people are forced to work on Win32 by their ...traversals, device opening, etc) .
开源项目-mdempsky-unbed.zip,unbed: refactoring tool to remove implicit field traversals
Study the in-built graph algorithms for better traversals and discover Spring-Data-Neo4j Look under the hood of Neo4j, covering concepts from the core classes in the source to the internal storage ...
The interrupt execution environment is recorded in a PCB and subsequent portal traversals chain PCBs as a stack. <br>Resume() restores the most recent PCB (analogous to a return-from-interrupt ...
Dissect layout traversals on Android. Features Intercept View methods. onMeasure(int, int) onLayout(boolean, int, int, int, int) draw(Canvas) and onDraw(Canvas) requestLayout() Override any of ...