PAT_A1115#Counting Nodes in a BST
Source:
Description:
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 or equal to the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤) which is the size of the input sequence. Then given in the next line are the N integers in [which are supposed to be inserted into an initially empty binary search tree.
Output Specification:
For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:
n1 + n2 = n
where
n1
is the number of nodes in the lowest level,n2
is that of the level above, andn
is the sum.
Sample Input:
9
25 30 42 16 20 20 35 -5 28
Sample Output:
2 + 4 = 6
Keys:
Attention:
- BST定义有时候会不一样,等号跟左子树还是右子树要看清楚,注意审题
Code:
/*
Data: 2019-06-26 15:55:13
Problem: PAT_A1115#Counting Nodes in a BST
AC: 17:15 题目大意:
BST定义:lchild <= root < rchild
根据插入序列建立BST树,统计最底层和次底层的结点数量 基本思路:
建树,记录结点层次,全局变量记录树的最大深度
更新最大深度的同时,统计底层和次底层的结点个数
*/
#include<cstdio>
int deep=,n1=,n2=;
struct node
{
int data;
node *lchild,*rchild;
}; void Insert(node *&root, int x, int height)
{
if(root == NULL)
{
if(deep == height)
n1++;
else if(deep == height+)
n2++;
else if(deep == height-)
{
deep++;
n2 = n1;
n1 = ;
}
root = new node;
root->data = x;
root->lchild = root->rchild = NULL;
}
else if(x <= root->data)
Insert(root->lchild, x, height+);
else
Insert(root->rchild, x, height+);
} int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE int n,x;
scanf("%d", &n);
node *root = NULL;
for(int i=; i<n; i++)
{
scanf("%d", &x);
Insert(root,x,);
}
printf("%d + %d = %d", n1,n2,n1+n2); return ;
}
最新文章
- Force.com微信开发系列(五)自定义菜单进阶及语音识别
- Ubuntu14.04安装GNOME3桌面
- Odoo 库存管理-库存移动(Stock Move)新玩法
- ExtJs自学教程(1):一切从API开始
- NFC(11)MifareUltralight格式规范及读写示例
- [CODEVS3641]上帝选人
- 内存映射+远线程 调用游戏CALL
- leetcode70
- iOS开发之MapKit
- 简述C/C++调用lua中实现的自定义函数
- 洛谷 P1200 [USACO1.1]你的飞碟在这儿Your Ride Is He…【字符串+模拟】
- [UOJ 41]【清华集训2014】矩阵变换
- Golang微服务:万精油NATS在Micro中的应用
- Nowcoder contest 370H Rinne Loves Dynamic Graph【分层图最短路】
- Shell 示例:利用 $RANDOM 产生随机整数
- c# 调用非托管c++dll 参数问题(转)
- 【mysql数据库】Linux下mysql安装连接全过程(含有问题详解)
- Session in BSU CodeForces - 1027F(思维 树 基环树 离散化)
- jetty插件实现 热部署
- 如何选择单片机和Android-LInux-ARM开发板?