SSOJ2491二叉排序树
2846+
作者:crxis 发布:2017-08-24 分类:二叉树
题目大意:对n个数依次插入建立二叉排序树,输出其中序遍历(数值相同编号小的先输出)以及最大路径长度。
题目描述
二叉排序树,其中序遍历就是一个有序序列。如果构建呢?一个一个结点插入到二叉树中,如果数据比当前节点小,就往左边插入,否则往右边插入,这样就保证了左子树的点都比根结点小,右子树的结点都不小于根结点。
现有n个数,请依次插入到二叉树中建立一棵二叉排序树,请将其中序遍历输出来,大小相同的先输出编号小的。最后,把这棵二叉树的最长路径长度输出来。
现有n个数,请依次插入到二叉树中建立一棵二叉排序树,请将其中序遍历输出来,大小相同的先输出编号小的。最后,把这棵二叉树的最长路径长度输出来。
输入
输入两行:
第一行:n
第二行:n个数,空格分隔
第一行:n
第二行:n个数,空格分隔
输出
输出n+1行:
第1到n行,每行两个数,即中序遍历的结点值以及原编号
第n+1行:树的最长路径长度
第1到n行,每行两个数,即中序遍历的结点值以及原编号
第n+1行:树的最长路径长度
样例输入
6
1 3 5 2 3 4
样例输出
1 1
2 4
3 2
3 5
4 6
5 3
4
提示
n不超过10000,所有数字不超过100000
解题思路
逐个点插入到二叉排序树中,最后输出其中序遍历。
建树:比根小的放左边,比根大的放右边。由于要求稳定排序,需要考虑相等的情况。中序遍历,访问顺序是左子树→根→右子树,如果出现相同的,后插入的要晚输出、后遍历,因此相等时也要放在右边。
最后考虑路径长度,再建树时或者输出中序遍历时,都可以建立最大路径长度。
程序实现
代码二:先读入数据,再进行链表操作,好理解。