编程介的小学生 2017-01-01 01:00 采纳率: 20.5%
浏览 859
已采纳

Tree Insertions

描述 :

All modern banks employ information systems to process their data. The amount of data is enormous. Imagine all the transactions, payments, e-banking, web services, etc. Therefore, advanced data structures must be used to store the data and allow to access them very quickly.

A Binary Search Tree (BST) is one example of such a data structure It holds a collection of values with some comparison operation that provides linear ordering on these values.

BST consists of nodes, each of them contains one value and has at most two subnodes: left and right (BST is a binary tree). The left subtree always contains only values strictly less than the node value, the right subtree only values greater than or equal to the node value.

As a consequence, values may easily be looked up by traversing the tree recursively. We begin with the root node and compare its value with the value we are searching for. Depending on the result, we descend either into the left or into the right subtree, but we never need to walk through both.

If we want to insert values to an existing tree, the procedure is also simple. The first value (when the tree is empty) is always put as the root. If the tree already exists, we start with the root node and traverse the tree recursively, as in the case of searching. When the traversal leads us to a missing subnode, we create a new leaf node at that position and assign it the new value.

The figures below show the tree after subsequently adding the following sequence of numbers: 3, 4, 3, 5, 4, 1, and 2.

You may notice that different permutations of the same numbers will often result in the same BST. For example, the tree from the fifth figure above may be constructed by three different input sequences:

3, 4, 3, 5, 4

3, 4, 5, 4, 3

3, 4, 5, 3, 4

Interesting, isn’t it? Your task is to compute how many different permutations are there that will result into the same BST.

输入:

The input will consist of several trees, each of them specified on two lines. The first line contains a single integer N (1 ≤ N ≤ 100), the number of values in the tree. The second line contains N values separated by a space. These values, if inserted in the given order, form a BST to be examined. All values will be between 0 and 1000.

The last tree is followed by a line containing a single zero.

输出:

The input will consist of several trees, each of them specified on two lines. The first line contains a single integer N (1 ≤ N ≤ 100), the number of values in the tree. The second line contains N values separated by a space. These values, if inserted in the given order, form a BST to be examined. All values will be between 0 and 1000.

The last tree is followed by a line containing a single zero.

样例输入:

5
3 4 3 5 4
7
3 4 3 5 4 1 2
31
16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
0
样例输出:

3
45
74836825861835980800000

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-01-05 15:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 LiBeAs的带隙等于0.997eV,计算阴离子的N和P
  • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
  • ¥15 来真人,不要ai!matlab有关常微分方程的问题求解决,
  • ¥15 perl MISA分析p3_in脚本出错
  • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
  • ¥15 ubuntu虚拟机打包apk错误
  • ¥199 rust编程架构设计的方案 有偿
  • ¥15 回答4f系统的像差计算
  • ¥15 java如何提取出pdf里的文字?
  • ¥100 求三轴之间相互配合画圆以及直线的算法