编写接口及实现类。定义抽象类树（tree）有树根（root）、树干（bolo）、树枝（branch）、叶子（leaf）成员，以及树识别的抽象方法realize（)。分别定义接口包含树成员的识别方法，如树根接口的方法rootrealize（)，定义实现类柳树（osier）也有树根、树干、树枝、叶子，但没有花（flower）。并编写测试类进行测试。

A．星型(star)

B．环型(ring)

C．树型(tree)

D．总线型(bus)

A．星型(star)

B．环型(ring)

C．树型(tree)

D．总线型(bus)

设一棵二叉树的结点定义为 struct BinTreeNode{ ElemType data；BinTreeNode*leftchild，*rightchild；)现采用输入广义表表示建立二叉树。具体规定如下： (1)树的根结点作为由子树构成的表的表名放在表的最前面。 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“”)表示输入结束。例如，对于如右图所示的二叉树，其广义表表示为A(B(G))，E(G)，C(F)。

在执行递归过程时，通常使用的数据结构是(39)。

A．堆栈(stack)

B．队列(queue)

C．图(graph)

D．树(tree)

在执行递归过程时，通常使用的数据结构是______。

A．堆栈(stack)

B．队列(queue)

C．图(graph)

D．树(tree)

A．

B．

C．

D．

决策树(decision tree)

呼吸树 respiratory tree

四叉树(quadtree)是2d-树的简化形式，其简化策略包括：

①直接沿区域的(水平或垂直)平分线切分，从而省略了中位点的计算;

②沿垂直方向切出的每一对节点(各自再沿水平方向切分)都经合并后归入其父节点;

③被合并的节点即便原先(因所含输入点不足两个)而未继续切分，在此也需要强行(沿水平方向)切分一次。

于是如图x8.8所示，每个叶节点各含0至1个输入点;每个内部节点则都统一地拥有四个孩子，分别对应于父节点所对应矩形区域经平均划分之后所得的四个象限，该树也由此得名。

a)与kd-树不同，四叉树可能包含大量的空(即不含任何输入点的)节点。更糟糕的是，此类节点的数目无法仅由输入规模n界定。对于任意的N>0，试构造一个仅含n=3个点的输入点集，使得在其对应的四叉树中，空节点的数目超过N个。

b)对于任一输入点集P，若将其中所有点对的最长、最小距离分别记作D和d，则λ=D/d称作P的散布度(spread)，试证明，P所对应的四叉树高度为o(logλ)。

c)试基于四叉树结构设计相应的范围查询算法，并利用你的四叉树结构实现该算法。

d)针对范围查询这一应用，试分别从时间、空间效率的角度，将四叉树与2d-树做一比较。

范围查询的另一解法需要借助范围树(range tree)。

为此，首先仿照如图8.37(教材240页)和图8.38(教材241页)所示的策略，按x坐标将平面上所有输入点组织为一棵平衡二叉搜索树，称作主树(main tree)。

于是如图x8.10(a)和(b)所示，该树中每个节点各自对应于一个竖直的条带区域;左、右孩子所对应的条带互不重叠，均由父节点所对应的条带垂直平分而得;同一深度上所有节点所对应的条带也互不重叠，而且它们合并后恰好覆盖整个平面。

接下来，分别对于主树中每一节点，将落在其所对应条带区域中的输入点视作一个输入子集，并同样采用以上方法，按照y坐标将各个子集组织为一棵平衡二叉搜索树，它们称作关联树(associative tree)。于是如图x8.10(a)和(c)所示，每棵关联树所对应的竖直条带，都会进而逐层细分为多个矩形区域，且这些矩形区域也同样具有以上所列主树中各节点所对应条带区域的性质，至此，主树与这o(n)棵关联树构成了一个两层的嵌套结构，即所谓的范围树。

利用范围树，可按如下思路实现高效的范围查询，对于任一查询范围R=[x₁，x₂]×[y₁，y₂]，首先按照[x₁，x₂]对主树做一次×方向的范围查询。根据8.4.1节的分析结论，如此可以得到o(logn)个节点，而且如x8.10(b)所示，它们所对应的竖直条带互不重叠，它们合并后恰好覆盖了x坐标落在[x₁，x₂]范围内的所有输入点。

接下来，深入这些节点各自对应的关联树，分别按照[y₁，y₂]做一次y方向的范围查询。如此从每棵关联树中取出的一系列节点，也具有与以上取自主树的节点的类似性质，具体地如图x8.10(c)所示，这些节点所对应的矩形区域互不重叠，且它们合并之后恰好覆盖了当前竖直条带内y坐标落在[y₁，y₂]范围内的所有输入点。换而言之，这些点合并之后将给出落在R中的所有点，既无重也不漏。

a)试证明，如此实现的范围树，空间复杂度为o(nlogn);

b)按照以上描述，试利用你的范围树实现新的范围查询算法;

c)试证明，以上范围查询算法的时间复杂度为O(r+log²n)，其中r为实际命中并被报告的点数;

d)继续改进以上范围树，在不增加空间复杂度的前提下，将查询时间减至O(r+logn)。