PAT 1099 Build A Binary Search Tree[BST性质]
1099 Build A Binary Search Tree(30 分)
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format left_index right_index
, provided that the nodes are numbered from 0 to N−1, and 0 is always the root. If one child is missing, then −1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.
Output Specification:
For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input:
9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42
Sample Output:
58 25 82 11 38 67 45 73 42
题目大意:给定一棵二叉查找树的树结构,和一组不同的数,那么就能形成唯一的一棵BST,给出这棵BST的层次遍历顺序。
我的AC代码,一遍过,开心。
#include <iostream> #include <algorithm> #include <map> #include<queue> #include<vector> using namespace std; struct Node{ int data,left,right; }node[101]; int d[101]; vector<int> in; queue<int> level; void inorder(int root){ if(node[root].left!=-1)inorder(node[root].left); in.push_back(root); if(node[root].right!=-1)inorder(node[root].right); } int main() { int n; cin>>n; int left,right; for(int i=0;i<n;i++){ cin>>left>>right; node[i].left=left; node[i].right=right; } for(int i=0;i<n;i++) cin>>d[i]; sort(d,d+n);//从小到大排列即是中序遍历的结果。 inorder(0); for(int i=0;i<n;i++){ node[in[i]].data=d[i];//安排进去了 } //接下来层次遍历了。 level.push(0); vector<int> lev; while(!level.empty()){ int top=level.front(); level.pop(); lev.push_back(node[top].data); if(node[top].left!=-1)level.push(node[top].left); if(node[top].right!=-1)level.push(node[top].right); } cout<<lev[0]; for(int i=1;i<n;i++){ cout<<" "<<lev[i]; } return 0; }
//猛一看觉得挺难,实际上要利用BST的性质就很好做了。 即中序遍历是数据从小到大排列的。
1.先对给出的二叉树结构,那么此时建树;
2.先对二叉树的下标进行中序遍历,并且将输入的数据从小到大排列,然后直接赋值就可以了。
3.再使用队列对其层次遍历即可。
相关文章
- Data Structures (五) - 二叉树Binary Tree
- tree命令详解
- CF GYM102759 I. Query On A Tree 17
- Golang实现默克尔树(merkle tree)
- 数据结构:红黑树(Red Black Tree)
- sys-tree:一个打印目录树结构的好帮手
- Linux的tree命令原来用处那么大,涨知识了!
- 【Android 性能优化】布局渲染优化 ( GPU 过度绘制优化总结 | CPU 渲染过程 | Layout Inspector 工具 | View Tree 分析 | 布局组件层级分析 )
- 解析B+Tree索引在H2中的实现
- Family Tree Maker 2019 for Mac(族谱家谱制作软件)
- ORA-13230: failed to create temporary table [string] during R-tree creation ORACLE 报错 故障修复 远程处理
- ORA-13237: internal error during R-tree concurrent updates: [string] ORACLE 报错 故障修复 远程处理
- Mysql 索引 BTree 与 B+Tree 的区别(面试)
- Linux tree命令详解程序员
- Oracle索引(B*tree和Bitmap)学习详解数据库
- EasyUI tree 实现点击展开/折叠详解编程语言
- 创建list ALV tree[RS_TREE_LIST_DISPLAY]详解编程语言
- Linux下安装tree:快速构建你的目录树(linux安装tree)
- Linux Tree安装简易教程(linuxtree安装)
- Oracle关联Tree让数据管理再添一种思维方式(oracle关联tree)
- 写了个XML+Tree无穷树js版