请输入或粘贴题目内容
搜题
如搜索结果不匹配，请联系老师获取答案
题目内容
（请给出正确答案）
答案
更多“在一棵表示有序集S的二又搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点”相关的问题
第1题
第2题
面试题:二叉树的深度
题目一：输入一棵二叉权的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成的一条路径的长度为树的深度。
二叉树的结点定义如下：
struct BinaryTreeNode
{
int m_nValue ；
BinaryTreeNode* m_pLeft;
BinarvTreeNode* m_pRight ；
}
题目二：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如图6.1中的二叉树就是一棵平衡二叉树。
第3题
所谓半无穷范围查询(semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具体地，这里的查询区域是某一侧无界的广义矩形区域，比如R=[-1，+1]x[0，﹢∞)，即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域，当然，对查询的语义功能要求依然不变——从某一相对固定的点集中，找出落在任意指定区域R内部的所有点。
范围树(176页习题[8-20])稍作调整之后，固然也可交持半无穷范围查询，但若能针对这一特定问题所固有的性质，改用优先级搜索树(priority search tree，PST)之类的数据结构，则不仅可以保持O(r+logn)的最优时间效率，而且更重要的是，可以将空间复杂度从范围树的O(nlogn)优化至O(n)。
如图x10.3所示，优先级搜索树除了首先在拓扑上应是一棵二叉树，还同时遵守以下三条规则。
①首先，各节点的y坐标均不小于其左右孩子(如果存在)——因此，整体上可以视作为以y坐标为优先级的二叉堆。
②此外，相对于任一父节点，左子树中节点的x坐标均不得大于右子树中的节点。
③最后，互为兄弟的每一对左、右子树，在规模上相差不得超过一。
a)试按照以上描述，用C/C++定义并实现优先级搜索树结构;
b)试设计一个算法，在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;
c)试设计一个算法，利用已创建的优先级搜索树，在O(r+logn)时间内完成每次半无穷范围查询，其中r为实际命中并被报告的点数。
第5题
A、h-1
B、h
C、h+1
D、h+2
第6题
设S表示某人拥有的所有的树的集合，M，N，T，P
S，且M是珍贵的树的集合，N是果树的集合，T是去年刚栽的树的集合，P是在果园中的树的集合，下面是3个前提条件和2条结论。
前提：(1)所有的珍贵的树都是去年裁的。
(2)所有的果树都在果园里。
(3)果园里没有去年栽的树。
结论：(1)所有的果树都是去年栽的。
(2)没有一棵珍贵的树是果树。
则前提(1)，(2)，(3)和结论(1)的集合表达式分别为
，根据前提条件，两个结论中正确的是
。
第8题
第9题
第10题
二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中的结点指针的指向。比如输入图4.12中左边的二叉搜索树，则输出转换之后的排序双向链表。
二叉树结点的定义如下：
struct BinaryTreeNode
{
int m_ nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
