P7133: 二叉树查找

---

【题目描述】

【题目描述】
相信大家对二叉查找树都很熟悉了，现在给你N个整数的序列，每个整数都在区间[1,N]内，且不重复。现在要你按照给定序列的顺序，建立一个二叉查找树，把第一个整数作为根，然后依次插入后面的整数。
每个结点X的插入过程其实就是模拟下面的 insert(X, root) 过程：
insert (number X, node N)
{
    increase the counter C by 1 //每次进来都会使C加1
    if X is less than the number in node N //如果X小于结点N的值
    {
        if N has no left child //N没有左孩子
   create a new node with the number X and set it to be the left child of node N //新建一个节点，把X作为N的左孩子
else
   insert(X, left child of node N) //递归插入到N左子树
    }
    else (X is greater than the number in node N) //如果X大于结点N的值
    {
if N has no right child //N没有右孩子
   create a new node with the number X and set it to be the right child of node N //新建一个节点，把X作为N的右孩子
else
   insert(X, right child of node N) //递归插入到N右子树
    }
}
你的任务是：每次把序列的一个整数插入到二叉查找树后，输出到目前为止计数累加器C的值是多少？注意：第一次插入根时，计数器C的值是0。
【输入描述】
第一行为一个整数N，表示序列中有多少个整数 (1≤N≤300000)。
接下来有N行，每行一个整数X，X在区间[1,N]内，且不重复，这N个整数组成了一个有序的序列。
【输出描述】
N 行，每行一个整数，第一行表示把序列的第一个数插入到二叉查找树后，当前计数器C的值是多少。
【输入样例 1 】
4
1
2
3
4
【输出样例 1 】
0
1
3
6
【输入样例 2 】
5
3
2
4
1
5
【输出样例 2 】
0
1
2
4
6
【输入样例 3 】
8
3
5
1
6
8
7
2
4
【输出样例 3 】
0
1
2
4
7
11
13
15
【样例1说明】：
第一次插入根1， 不执行过程insert(number x, node N)，所以C是0，第二次插入2, C加1, 所以插入2完毕后，输出C的值是1，第三次插入3，依次执行了insert(3,1)、insert(3,2)，所以C加2，变成3；第四次插入4，依次执行了insert(4,1)、insert(4,2)、insert(4,3)，所以C加3，变成6。
【数据范围】
对于50%的数据，保证1≤N≤1000。
对于100%的数据，保证1≤N≤300000。
【来源】
2023重庆NOI培训考试
 

题目类型~

2023重庆NOI培训考试 

咻咻~

提交答案 状态 返回