1 题目

给出一组整数对 { (a[0], b[0]), (a[1], b[1]) ... (a[n-1], b[n-1]) },全部 a 值和 b 值分别不反复(随意 i != j 满足 a[i] != a[j] 且 b[i] != b[j])。

构造一棵 n 结点的二叉树,将这 n 个整数对分配到各个结点上。根和全部子树满足下面条件:1) 全部结点的 a 值满足二叉查找树的顺序。即 left->a <root->a && root->a < right->a。2) 全部结点的 b 值满足最大堆的顺序。即 root->b
>left->b && root->b > right->b。

问题一:实现 build 函数,输入 n 个整数对。返回一棵构造好的二叉树。

struct pair_t {    int a,b;};struct node_t {    int a, b;    node_t *left, *right;};node_t*build(pair_t* pair, int n);

整数对A满足二叉查找树,B满足最大堆-LMLPHP

问题二:已知满足上述条件的二叉树,设计算法实现插入一个整对 (a, b),使新的二叉树仍满足上述条件。该算法比較复杂。候选人仅仅需描写叙述思路。

若有错误欢迎大家指正,若有更好的方法。欢迎大家不吝赐教!

2 分析

该问题的关键就是找树根。

方法一:当前全部整数对的树根为b中最大值相应的整数对I。由于仅仅有这样才干满足最大堆的性质。然后依据I中的a值将整数对分为比a大于比a小两组,小的作为左子树,大的作为右子树。当整数对个数为0时,返回NULL。该方法时间复杂度O(n)。

方法二(华南理工大神ohm提供):将整数对依照b进行逆向排序,然后依照a进行二分叉树的插入操作就可以。

该方法的时间复杂度为O(nlogn)。

3 实现

方法一实现:

struct pair_t
{
int a, b;
}; struct node_t
{
int a, b;
node_t *left, *right;
}; node_t *build(pair_t *pair, int n);
int findMaxB(pair_t *pair, int n); int findMaxB(pair_t *pair, int n)
{
int pos = 0; for (int i = 1; i < n; ++i)
{
if (pair[pos].b < pair[i].b)
{
pos = i;
}
} return pos;
} node_t *build(pair_t *pair, int n)
{
if (0 == n)
{
return NULL;
}
node_t *root = new node_t[1];
pair_t *pair1 = new pair_t[n];
pair_t *pair2 = new pair_t[n];
int num1 = 0;
int num2 = 0;
int maxB = findMaxB(pair, n);
root->a = pair[maxB].a;
root->b = pair[maxB].b;
int maxBA = pair[maxB].a;
for (int i = 0; i < maxB; ++i)
{
if (pair[i].a < maxBA)
{
pair1[num1].a = pair[i].a;
pair1[num1++].b = pair[i].b;
}
else
{
pair2[num2].a = pair[i].a;
pair2[num2++].b = pair[i].b;
}
}
for (int i = maxB + 1; i < n; ++i)
{
if (pair[i].a < maxBA)
{
pair1[num1].a = pair[i].a;
pair1[num1++].b = pair[i].b;
}
else
{
pair2[num2].a = pair[i].a;
pair2[num2++].b = pair[i].b;
}
}
root->left = build(pair1, num1);
delete []pair1; root->right = build(pair2, num2);
delete []pair2;
return root;
}

方法二实现:

void insert(node_t *&root, pair_t p)
{
if (root == NULL)
{
root = new node_t;
root->a = p.a;
root->b = p.b;
root->left = NULL;
root->right = NULL;
return;
}
if (root->a < p.a)
{
insert(root->right, p);
}
else
{
insert(root->left, p);
}
} node_t *build(pair_t *pair, int n)
{
if (0 == n)
{
return NULL;
}
node_t *root = NULL;
sort(pair, pair + n);
for (int i = 0; i < n; ++i)
{
insert(root, pair[i]);
}
return root;
}

4 问题二

设插入整数对为(nA, nB),当前訪问树中结点为curNode。插入步骤例如以下:

(1) 若curNode.b>nB。则比較curNode.a与nA。若curNode.a>nA,则curNode=curNode->left;反之,curNode=curNode->right。直到curNode.b<nB或curNode=NULL,停止查找。

(2) 若curNode=NULL,则直接将该整数对插入到此位置就可以;反之,将(nA,nB)作为curNode父结点的孩子结点。curNode作为插入结点的孩子结点(依据a的值确定是左孩子还是右孩子)。

(3) curNode作为新插入结点的右(左)孩子。则须要遍历curNode的左(右)子树,找到a值小于nA的子树的根作为新插入结点的左(右)孩子。当然若不存在时先插入结点不存在左(右)孩子。

04-19 20:13