wkc959 2015-08-23 03:19 采纳率: 0%
浏览 1657

一道关于二叉树的编程题

给出一组整数对 { (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);

例如,输入是 {(5, 8), (2, 10), (4, 3), (1, 5), (0, 2), (9, 1)},输出是下列二叉树:

提示:1) 构造出的二叉树的形态是存在且唯一的。 2) 想办法确定树根。

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

  • 写回答

1条回答 默认 最新

  • havedream_one 2015-08-23 06:16
    关注

    是阿里的笔试题吗????

    评论

报告相同问题?

悬赏问题

  • ¥20 matlab计算中误差
  • ¥15 对于相关问题的求解与代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料
  • ¥15 使用R语言marginaleffects包进行边际效应图绘制
  • ¥20 usb设备兼容性问题
  • ¥15 错误(10048): “调用exui内部功能”库命令的参数“参数4”不能接受空数据。怎么解决啊