- 浏览: 36651 次
- 性别:
- 来自: 杭州
最新评论
PAT1020 Tree Traversals
- 博客分类:
- PAT
已知中序遍历 后序遍历,求层次遍历
Sample Input:
7 2 3 1 5 7 6 4 1 2 3 4 5 6 7Sample Output:
4 1 6 3 5 7 2
#include <string.h> #include <iostream> using namespace std; #define MAX_TREE_SIZE 30 typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree CreateBT(int *postorder,int *inorder,int n) { BiTree bt; int *p; int k; if (n<=0) { return NULL; } bt=(BiTree)malloc(sizeof(BiTNode)); bt->data = *(postorder); for(p = inorder; p < inorder + n; p++) { if (*p == *postorder) { break; } } k = p-inorder; bt->lchild = CreateBT(postorder-n+k,inorder,k); bt->rchild = CreateBT(postorder-1,p+1,n-k-1); return bt; } void LevelOrder(BiTree b, int K) { int Tree[MAX_TREE_SIZE] = {0}; int i = 0; BiTree p; BiTree qu[MAX_TREE_SIZE]; //定义环形队列,存放结点指针 int front = -1, rear = -1; //定义队头和队尾指针 rear++; qu[rear] = b; //根结点指针进入队列 while (front != rear) //队列不为空 { front = (front+1)%MAX_TREE_SIZE; p = qu[front]; //队头出队列 Tree[i++] = p->data; //访问结点 if (p->lchild != NULL) //有左孩子时将其进队 { rear = (rear+1)%MAX_TREE_SIZE; qu[rear] = p->lchild; } if (p->rchild != NULL) //有右孩子时将其进队 { rear = (rear+1)%MAX_TREE_SIZE; qu[rear] = p->rchild; } } for (int j = 0; j < K - 1; j++) { cout<<Tree[j]<<" "; } cout<<Tree[K - 1]; } int main() { BiTree T; int Tree1[MAX_TREE_SIZE] = {0}; int Tree2[MAX_TREE_SIZE] = {0}; int K; cin>>K; for (int i = 0; i < K; i++) { int x; cin>>x; Tree1[i] = x; } for (int i = 0; i < K; i++) { int x; cin>>x; Tree2[i] = x; } T = CreateBT(Tree1 + K - 1, Tree2 , K); LevelOrder(T,K); return 0; }
发表评论
-
PAT1013 Battle Over Cities
2012-11-29 23:59 773Sample Input 3 2 3 1 2 1 3 ... -
PAT1003 Emergency
2012-11-29 23:46 662Sample Input 5 6 0 2 1 2 1 ... -
PAT1041 Be Unique
2012-11-23 23:43 760找出只出现过一次的数,用各种排序必然超时,需要用数组做hash ... -
PAT1042 Shuffling Machine
2012-11-23 23:42 733扑克洗牌 #include < ... -
PAT1040 Longest Symmetric String
2012-11-23 23:41 959求最长回文子串 #include < ... -
PAT1036 Boys vs Girls
2012-11-23 23:41 716Sample Input 1: 3 Joe M Mat ... -
PAT1035 Password
2012-11-23 23:40 616Sample Input 1: 3 Team0000 ... -
PAT1031 Hello World for U
2012-11-22 23:54 656Sample Input: helloworld! S ... -
PAT1029 Median
2012-11-22 23:54 651用标准库的排序全部超时,需要自己实现,另外还不能用cin co ... -
PAT1028 List Sorting
2012-11-22 23:53 808用vector最后一个用例超时了。。。 Sample ... -
PAT1027 Colors in Mars
2012-11-22 23:52 623Sample Input 15 43 71 Samp ... -
PAT1025 PAT Ranking
2012-11-22 23:51 772Sample Input: 2 5 123456789 ... -
PAT1023 Have Fun with Numbers
2012-11-21 23:55 687大数的相加 比较两个字符串中字符完全相同 Sa ... -
PAT1019 General Palindromic Number
2012-11-21 23:53 537十进制转任意进制,并比较是否是回文数 Sample I ... -
PAT1037 Magic Coupon
2012-11-21 15:46 663Sample Input: 4 1 2 4 -1 ... -
PAT1038 Recover the Smallest Number
2012-11-20 23:52 1668由一道面试题改的 把数组排成最小的数 不同之处是这 ... -
PAT1024 Palindromic Number
2012-11-20 23:51 648Sample Input 1: 67 3 Sampl ... -
PAT1015 Reversible Primes
2012-11-19 23:51 771十进制转任意进制 假设十进制数为number,转 ... -
PAT1012 The Best Rank
2012-11-19 23:50 927四门功课,输出排名最高的是哪个 Sample Inpu ... -
PAT1011 World Cup Betting
2012-11-19 23:50 534Sample Input 1.1 2.5 1.7 1.2 ...
相关推荐
给你inorder的栈操作步骤,让你写出postorder后的序列。 http://blog.csdn.net/xkzju2010/article/details/46325457
思路后序和中序构造二叉树唯一一个注意的地方,在注释中。// 注意这里是pos-right_num-1而不是想当然的pos_inr-1,这两个的位置并不一定对应。
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 ...
PTA 7-1 Tree Traversals Again
c (数据结构) AVLTree Graph Heap Tree Traversals Again 计算器_栈 二叉排序树 二分法查找 线性表 等 值得学习
cd BinaryTree遍历 npm安装 npm开始 浏览到htpp:// localhost:3000 登陆页面 包含一棵静态树。 用户可以选择任何遍历(顺序,前顺序或后顺序),遍历的结果将显示在树下。 您也可以同时签出算法。 预购遍历 后...
Binary_tree_order_traversals 在该项目中,我们可以看到树的顺序,前顺序和后顺序。 该程序将打开一个菜单,并允许用户通过一个接一个地导入数据(节点)来创建他/她的树: '''0。退出 插入 展示 搜索 为了 预购...
Tree traversals, search Stack Queue Graph traversals(BFS, DFS) 最短路径数学题 从之前的采访中吸取的错误和教训: 调度: 更加注意时间安排,在公司现场面试前保持2-3天的开放时间。 除非非常关键,否则不要立即...
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 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...
3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 I 3.7.2 Postorder . . . . . . . . . . . . . . ....
Breadth first search algorithm in C. Example are countries in Romania traversals.
开源项目-mdempsky-unbed.zip,unbed: refactoring tool to remove implicit field traversals
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) .
This repository contains various classic algorithms about ordenation, graph traversals, dynamic programing and some crypto related stuff as well. 在这个仓库中: - Peak finding (1D/2D) - Binary ...
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 ...
can support thousands of concurrent users, complex traversals, and analytic graph queries. Learn More The project homepage contains more information on JanusGraph and provides links to ...
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 ...
* 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...
conda4.7.12 资料来源1: : 数据源2: : 软体:Jupyter Notebook,Pandas Library,CityPy,Python Request,API,JSON Traversals概括第一部分:获取每个城市的天气描述和降水量笔记本:Weater_Database.ipynb ...