当前位置:首页 > 数据结构 > 二叉树 > 正文
SSOJ2491二叉排序树
2846+

题目大意:对n个数依次插入建立二叉排序树,输出其中序遍历(数值相同编号小的先输出)以及最大路径长度。

题目描述

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

输入

输入两行:
第一行:n
第二行: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

解题思路

逐个点插入到二叉排序树中,最后输出其中序遍历。

建树:比根小的放左边,比根大的放右边。由于要求稳定排序,需要考虑相等的情况。中序遍历,访问顺序是左子树→根→右子树,如果出现相同的,后插入的要晚输出、后遍历,因此相等时也要放在右边。

最后考虑路径长度,再建树时或者输出中序遍历时,都可以建立最大路径长度。

程序实现

代码二:先读入数据,再进行链表操作,好理解。

About

坚决不Copy代码!

本文标签:,,,,

SSOJ2491二叉排序树:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!