问题2091--二叉排序树(bsort)

2091: 二叉排序树(bsort)

时间限制: 1 Sec  内存限制: 128 MB
提交: 36  解决: 21
[提交] [状态] [讨论版] [命题人:]

题目描述

二叉排序树,其中序遍历就是一个有序序列。如果构建呢?一个一个结点插入到二叉树中,如果数据比当前节点小,就往左边插入,否则往右边插入,这样就保证了左子树的点都比根结点小,右子树的结点都不小于根结点。
现有n个数,请依次插入到二叉树中建立一棵二叉排序树,请将其中序遍历输出来,大小相同的先输出编号小的。最后,输出最大树深(1个结点深度算0)。

输入

输入两行:
第一行:n
第二行:n个数,空格分隔

输出

输出n+1行:
第1到n行,每行两个数,即中序遍历的结点值以及原编号
第n+1行:树的最大树深

样例输入 Copy

6
1 3 5 2 3 4

样例输出 Copy

1 1
2 4
3 2
3 5
4 6
5 3
4

提示

n不超过10000,所有数字不超过100000

来源/分类