2 shunfurh shunfurh 于 2017.01.01 09:00 提问

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个回答

caozhy
caozhy   Ds   Rxr 2017.01.05 23:53
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Git历险记
<br />1、初识版本控制系统 Git<br />Git是用于Linux内核开发的版本控制工具。与常用的版本控制工具CVS、Subversion等不同,它采用了分布式版本库的方式,不必服务器端软件支持,使源代码的发布和交流极其方便。本文是《Git Community Book》的译者刘辉在InfoQ上发表的一篇专栏文章,整个系列名为《Git历险记》。本文是系列第一篇,对Git的历史、特点和作者的使用心得进行了概述。以下为正文。<br />作为分布式版本控制系统的重要代表——Git已经为越来越多的人所认识,
Git常用操作命令总结(二)
Git常用操作命令总结(一)本文主要总结一下git中进行分支管理的常用命令:1、创建分支$ git branch bra ## 创建分支bra 2、切换到分支bra$ git checkout bra Switched to branch 'bra' 3、创建并切换分支$ git checkout -b rcm Switched to a new branch 'rcm' ## git checko
Git初体验(1)-初始化、添加、查看
实用性强,边学边练,一点也不枯燥。而且,所学的Git命令是“充分且必要”的,掌握了这些东西,就可以通过Git轻松地完成工作。 Git是什么?他是目前世界上最先进的分布式版本控制系统(没有之一)。 那什么是版本控制系统?如果你用Microsoft Word写过长篇大论,那你一定有这样的经历: 想删除一个段落,又怕将来想恢复找不回来怎么办?有办法,先把当前文件“另存为……”一
从0开始学习Git系列之「Git中阶」
远程管理 创建远程仓库 是时候在github上创建一个远程仓库了。 首先使用你的github账号登录,然后找到New repository这个按钮,点击创建远程仓库,repository name就取之前在本地建的仓库名,description随意。然后,只能选public即公有库(任何人都能看),要是你想拥有private私有库,就需要交费了。到此,你离成功只差最后一步,点击create re
Hiberanate的拦截器和监听事件
创建监听类: SaveOrUpdateListener public classSaveOrUpdateListener extends DefaultSaveOrUpdateEventListener { @Override public voidonSaveOrUpdate(SaveOrUpdateEvent event) { // T
MIT 麻省理工 算法课程-第十节-讲义(经典!)
Red-black Trees, Rotations, Insertions, Deletions
Git(二)
Git11--创建与合并分支 在版本回退里,你已经知道,每次提交,Git都把它们串成一条时间线,这条时间线就是一个分支。截止到目前,只有一条时间线,在Git里,这个分支叫主分支,即master分支。HEAD严格来说不是指向提交,而是指向master,master才是指向提交的,所以,HEAD指向的就是当前分支。 一开始的时候,master分支是一条线,Git用master指向最新的
git统计操作
统计代码git提交的行数 $ git log --author="$(git config --get user.name)" --pretty=tformat: --numstat | gawk '{ add += $1 ; subs += $2 ; loc += $1 - $2 } END { printf "added lines: %s removed lines : %s tota
hdu 5818 Joint Stacks (优先队列)
Joint StacksTime Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 341 Accepted Submission(s): 139Problem Description A stack is a data structure
Git权威指南--改变历史
0.查看版本库最新五次提交 $ git log --stat --oneline -5 e2609ca 加结束标志 test_git.txt | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) 1f5c128 此处省略一万字 test_git.txt | 3 ++- 1 file changed, 2 insertions(+),