首页 > ACM题库 > HDU-杭电 > HDU 2792-HOJ-Tree Insertions-二叉树-[解题报告]C++
2014
02-14

HDU 2792-HOJ-Tree Insertions-二叉树-[解题报告]C++

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


题意: 依次给出一些点, 插到一棵二叉平衡树(相同的插到右子树),把这些点其中一些打乱插入顺序构建的树不变,  问有多少种不同方案使这树不变.


做法:  有个简单易见的规律 凡是插入的结点如果不在同一个子树上,那么插入的顺序先后没影响. 如果在同一个子树上肯定会影响.  所以最终有


当前结点顺序方案=c(左子树+右子树,左子树) *左子树顺序方案*右子树顺序方案


代码:  直接把__int64换成大整数就OK鸟


#include <iostream>


#include <queue>


#include <stack>


#include <cmath>


 


using namespace std;


 


const int N = 200 + 5;


 


int root;


int vN;


struct Node


{


     int l;


     int r;


     int v;


     int cn;  // 子结点数


}node[N];


 


void init()


{


     root = 0;


     vN = 0;


}


 


void creatTree(int v)


{


     node[root].v = v;


     node[root].l = -1;


     node[root].r = -1;


     node[root].cn = 0;


}


 


void insert(int pos, int v)


{


     node[pos].cn++;


     if (v < node[pos].v)


     {


         if (node[pos].l != -1) insert(node[pos].l, v);


         else


         {


              node[pos].l = ++vN;


              node[vN].v = v;


              node[vN].l = -1;


              node[vN].r = -1;


              node[vN].cn = 0;


         }


     }


     else


     {


         if (node[pos].r != -1) insert(node[pos].r, v);


         else


         {


              node[pos].r = ++vN;


              node[vN].v = v;


              node[vN].l = -1;


              node[vN].r = -1;


              node[vN].cn = 0;


         }


     }


}


 


__int64 cnm(int n, int m)


{


     __int64 ret;


     ret = 1;


     int i, j;


     if (n – m < m) m = n – m;


     for (i = n, j = 1; j <= m; i–, j++)


     {


         ret *= i;


         ret /= j;


     }


     return ret;


}


 


__int64 f(int pos)


{


     __int64 t1;


     __int64 t2;


     t1 = 0;


     t2 = 0;


     if (node[pos].l != -1) t1 = f(node[pos].l);


     else


         t1 = 1;


     if (node[pos].r != -1) t2 = f(node[pos].r);


     else


         t2 = 1;


     int l = node[pos].l;


     int r = node[pos].r;


     if (l == -1 || r == -1) return t1 * t2;


     return cnm(node[l].cn + node[r].cn + 2, node[l].cn + 1) * t1 * t2;


}


 


int main ()


{


     int n, i, v;


     while (scanf(“%d”, &n) != EOF && n)


     {


         init();


         scanf(“%d”, &v);


         creatTree(v);


         for (i = 2; i <= n; i++)


         {


              scanf(“%d”, &v);


              insert(root, v);


         }


         cout << f(root) << endl;


     }


}


 

解题参考:http://akheyun.blog.163.com/blog/static/1382492762010419587811/


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的