- 浏览: 149984 次
- 性别:
- 来自: 内蒙古
文章分类
最新评论
-
linest:
ethi_teye 写道id可能是0开头的,你用int保存再输 ...
pat-1022 Digital Library -
ethi_teye:
id可能是0开头的,你用int保存再输出,这些0就被忽略了。
pat-1022 Digital Library -
lixuanchong:
在lz的代码上稍作修改即可:
#include<iost ...
pat-1010* Radix -
air_sky:
确实。。result=a0*base^0+a1*base^1+ ...
pat-1010* Radix -
linest:
air_sky 写道
关于“方程只有一个正整数解,就可以用二分 ...
pat-1010* Radix
给后序和中序遍历
求层序遍历
Sample Input:7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:4 1 6 3 5 7 2
注意如果是按char型处理,还要考虑多字符情况 如12
在输入上要加以处理,用int比较简单
求层序遍历
Sample Input:7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:4 1 6 3 5 7 2
注意如果是按char型处理,还要考虑多字符情况 如12
在输入上要加以处理,用int比较简单
#include "stdio.h" #include "stdlib.h" typedef struct bt_node // 定义二叉树结点。 { char data ; struct bt_node * left ; struct bt_node * right ; } bt_node ; //搜索根在中序数组中的下标,若两个序列存在逻辑错误结束程序。 int search(char in[] , int inl , int inh , char ch) { int i ; for(i=inl;i<=inh;i++) { if(in[i]==ch) return i ; } printf("两个序列相互矛盾,无法构造二叉树!\n") ; exit(1) ; } //中根序列、后跟序列构造二叉树。 bt_node * create_bt1(char in[],int inl,int inh,char post[],int postl,int posth) { int mid ; bt_node * r ; if(inl>inh||postl>posth) return NULL; //递归结束条件。 mid = search(in , inl , inh , post[posth]) ; //搜索根在中序数组中的下标。 //printf("%d\n" , mid) ;可以通过这个语句查看有没有搜索正确。 r = (bt_node *)malloc(sizeof(bt_node)) ; r->data = post[posth] ; //构造根结点。 r->left = create_bt1(in,inl,mid-1, post,postl,postl+mid-inl-1) ; //构造左子树。 r->right = create_bt1(in,mid+1,inh, post,postl+mid-inl,posth-1) ; //构造右子树。 return r ; //返回根指针。 } bt_node * create_bt2(char in[],int inl,int inh,char pre[],int prel,int preh) { int mid ; bt_node * r ; if(inl>inh||prel>preh) return(NULL) ; mid = search(in , inl , inh , pre[prel]) ; //printf("%d\n" , mid) ;可以通过这个语句查看有没有搜索正确。 r = (bt_node *)malloc(sizeof(bt_node)) ; r->data = pre[prel] ; r->left = create_bt2(in,inl,mid-1, pre,prel+1,prel+mid-inl) ; r->right = create_bt2(in,mid+1,preh, pre,prel+mid-inl+1,preh) ; return(r) ; } void pre_order(bt_node * r) { if(r==NULL) return ; putchar(r->data) ; pre_order(r->left) ; pre_order(r->right) ; } void in_order(bt_node * r) { if(r==NULL) return ; in_order(r->left) ; putchar(r->data) ; in_order(r->right) ; } void post_order(bt_node * r) { if(r==NULL) return ; post_order(r->left) ; post_order(r->right) ; putchar(r->data) ; } //定义链队列结点。 typedef struct queue_node { struct bt_node * bt_node_pointer ; struct queue_node * next ; } queue_node ; //二叉树的层次遍历。 void wfs_order(bt_node * r) { queue_node * front , * rear , * mid ; front = (queue_node *)malloc(sizeof(queue_node)) ; rear = front ; mid = front ; //定义一个队列,并给予初始化。 rear->bt_node_pointer = r ; rear = (queue_node *)malloc(sizeof(queue_node)) ; mid->next = rear ; mid = rear ; //r进队。 while(front!=rear) //front!=rear指队列非空。 { r = front->bt_node_pointer ; printf("%d",r->data) ; //r出队,并打印r->data。 front = front->next ; if(r->left != NULL) //r->left进队。 { rear->bt_node_pointer = r->left ; rear = (queue_node *)malloc(sizeof(queue_node)) ; mid->next = rear ; mid = rear ; } if(r->right != NULL) //r->right进队。 { rear->bt_node_pointer = r->right ; rear = (queue_node *)malloc(sizeof(queue_node)) ; mid->next = rear ; mid = rear ; } if(front != rear) putchar(' '); } } int main() { int N; int num; scanf("%d",&N); getchar(); char* post = new char[N]; char* in = new char[N]; for(int i=0;i<N;i++) { scanf("%d",&num); post[i] = num; } for(int i=0;i<N;i++) { scanf("%d",&num); in[i] = num; } bt_node * root = create_bt1(in,0,N-1, post,0,N-1); wfs_order(root) ; putchar('\n') ; return 0; }
发表评论
-
pat-1016 Phone Bills
2012-02-27 00:01 3095Sample Input:10 10 10 10 10 10 ... -
pat-1018 Public Bike Management 有问题
2012-02-26 19:55 3542最后一个case还过不了 == 为什么呢 思路dfs遍历到目 ... -
pat-1017* Queueing at Bank
2012-02-25 12:32 2080银行8点至17点开 有固定窗口数 来早了要等,没窗口要等,1 ... -
pat-1021* Deepest Root
2012-02-25 00:36 2727判断图是否都连接构成树,求使树高最大的根 实际上求图上两点间 ... -
pat-1022 Digital Library
2012-02-27 14:26 1741可能的查询 ID值进行map映射 以下代码有问题,原因 ... -
pat-1019 General Palindromic Number
2012-02-23 00:26 1058判断数字在给定进制下是否回文 并打出进制转换后系数 思路,将 ... -
pat-1026 Table Tennis
2012-02-19 19:19 0题意?? 多个桌可用 vip桌可用时 队中vip还是最小号 ... -
pat-1025 PAT Ranking
2012-02-19 15:45 1312不同地点一起排序 先组内排序,再全局排序 将小组添加进全局 ... -
pat-1024 Palindromic Number
2012-02-20 00:56 1955如果不是回文则进行逆序相加操作,打印出最后回文和操作次数 题 ... -
pat-1023 Have Fun with Numbers
2012-02-19 00:26 2504判断一个数乘2后是否是原数的一个排列 思路: int最大值 ... -
pat-1015 Reversible Primes
2011-09-28 20:08 1441将数字转成指定进制,再反序,判断原数和新数是否都是质数。 ... -
pat-1009 Product of Polynomials
2011-09-19 23:31 11821009:多项式乘积。 Sample Input 2 1 2 ... -
pat-1008 Elevator
2011-09-19 23:09 8961008: 电梯上升一层6秒,下降4秒,停留5秒。给出请求序列 ... -
pat-1007 Maximum Subsequence Sum
2011-09-19 22:59 14641007:连续和最大子串。 O(n)时间即可完成,不需存储空 ... -
pat-1006 Sign In and Sign Out
2011-09-18 23:35 13941006:给出进入和离开时间,求最早来和最晚走的人 Samp ... -
pat-1005 Spell It Right
2011-09-18 22:52 10611005:计算各个数字的和,并翻译成英文。 Sample I ... -
pat-1004* Counting Leaves
2011-09-18 22:35 16811004: 统计树的每一层上叶子节点的个数 Sample I ... -
pat-1010* Radix
2011-09-17 19:36 38461010: 给出两个数,已知一个数的进制,求是否可以在某进制下 ... -
pat-1014* Waiting in Line
2011-09-17 10:42 18561014: 排队服务问题,队列实现。 注意条件控制。 # ... -
pat-1012 The Best Rank
2011-09-16 23:58 18671012: 找出最佳排名 代码有点冗余。。。用了一些stl容 ...
相关推荐
给你inorder的栈操作步骤,让你写出postorder后的序列。 http://blog.csdn.net/xkzju2010/article/details/46325457
PTA 7-1 Tree Traversals Again
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,这两个的位置并不一定对应。
This repository contains various classic algorithms about ordenation, graph traversals, dynamic programing and some crypto related stuff as well. 在这个仓库中: - Peak finding (1D/2D) - Binary ...
cd BinaryTree遍历 npm安装 npm开始 浏览到htpp:// localhost:3000 登陆页面 包含一棵静态树。 用户可以选择任何遍历(顺序,前顺序或后顺序),遍历的结果将显示在树下。 您也可以同时签出算法。 预购遍历 后...
c (数据结构) AVLTree Graph Heap Tree Traversals Again 计算器_栈 二叉排序树 二分法查找 线性表 等 值得学习
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...
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...
开源项目-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 ...
iBFS: Concurrent Breadth-First Search on GPUsHang Liu H....- where multiple breadth-first traversals are performed si- multaneously on the same graph. We have designed and developed a new
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.
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) .
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 ...
通用镜头 通常得出等值线,遍历,透镜和棱镜。 该库使用GHC.Generics以类型定向的方式为代数数据类型派生高效的光学系统(遍历,透镜和棱镜),并在可能时侧重于良好的类型推断和错误消息。 该库在论文中进行了描述...
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 ...