1115 Counting Nodes in a BST (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 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 (≤1000) which is the size of the input sequence. Then given in the next line are the N integers in [−10001000] 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, and n
is the sum.
Sample Input:
9
25 30 42 16 20 20 35 -5 28
Sample Output:
2 + 4 = 6
题意:求二叉查找树最低两层结点,并求出他们的和。
分析:先建树,再层序遍历求出最大层数maxlayer,遍历过程中用num数组来记录每层结点个数即可。还有一种方法是用DFS求出最大深度maxdepth,同样也用数组记录每个深度的结点个数。
/** * Copyright(c) * All rights reserved. * Author : Mered1th * Date : 2019-02-27-15.33.36 * Description : A1115 */ #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<string> #include<unordered_set> #include<map> #include<vector> #include<set> #include<queue> using namespace std; ; int a[maxn],n; int num[maxn]; struct node{ int data,layer; node* lchild; node* rchild; }; node* newNode(int v){ node* Node=new node; Node->data=v; Node->lchild=Node->rchild=NULL; return Node; } void insert(node* &root,int x){ if(root==NULL) { root=newNode(x); return; } else if(x>root->data) insert(root->rchild,x); else insert(root->lchild,x); } node* Create(int data[],int n){ node* root=NULL; ;i<n;i++){ insert(root,data[i]); } return root; } ; void BFS(node* root){ queue<node*> q; q.push(root); root->layer=; while(!q.empty()){ node* now=q.front(); q.pop(); num[now->layer]++; if(maxlayer<now->layer) maxlayer=now->layer; if(now->lchild){ now->lchild->layer=now->layer+; q.push(now->lchild); } if(now->rchild){ now->rchild->layer=now->layer+; q.push(now->rchild); } } } int main(){ #ifdef ONLINE_JUDGE #else freopen("1.txt", "r", stdin); #endif scanf("%d",&n); ;i<n;i++){ scanf("%d",&a[i]); } node* root=Create(a,n); BFS(root); printf(],num[maxlayer]+num[maxlayer-]); ; }
/** * Copyright(c) * All rights reserved. * Author : Mered1th * Date : 2019-02-06-00.18.21 * Description : A1115 */ #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<string> #include<unordered_set> #include<map> #include<vector> using namespace std; ; struct node{ int data; node* lchild; node* rchild; }; node* newNode(int v){ node* Node=new node; Node->data=v; Node->lchild=Node->rchild=NULL; return Node; } void insert(node* &root,int x){ if(root==NULL) { root=newNode(x); return; } else if(x>root->data) insert(root->rchild,x); else insert(root->lchild,x); } node* Create(int data[],int n){ node* root=NULL; ;i<n;i++){ insert(root,data[i]); } return root; } },maxdepth=-; void DFS(node* root,int depth){ if(root==NULL){ maxdepth=max(maxdepth,depth); return; } num[depth]++; DFS(root->lchild,depth+); DFS(root->rchild,depth+); } int main(){ #ifdef ONLINE_JUDGE #else freopen("1.txt", "r", stdin); #endif int n,data[maxn]; cin>>n; ;i<n;i++){ cin>>data[i]; } node* root=Create(data,n); DFS(root,); printf(],num[maxdepth-],num[maxdepth-]+num[maxdepth-]); ; }
最新文章
- Java 线程 — ConcurrentHashMap
- python 环境安装
- ecshop transport.js 和 jquery 冲突解决办法
- 一步一步制作yaffs/yaffs2根文件系统(一)---储备好基础知识再打
- linux高级命令组合
- tcl/tk实例详解——返回一个文件夹下所有文件的绝对路径
- day9_python学习笔记_chapter12_模块
- TJ4运行环境
- zabbix利用SNMPTrap接收交换机主动告警
- Flutter之 LimitedBox、Offstage、OverflowBox、SizedBox详解
- 【dfs】p1451 求细胞数量
- linux 启动管理
- 用Executors工具类创建线程池
- js-jquery-SweetAlert2【一】使用
- 双击打开excel时提示:向程序发送命令时出现问题
- Json反序列化为动态类型(dynamic)
- java中,方法可以访问他的类对象的任何私有特性
- kafka 基础知识梳理-kafka是一种高吞吐量的分布式发布订阅消息系统
- 从SNE到t-SNE再到LargeVis
- while循环案例