在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树中的结点数加1。试写时间复杂度为O(logrn)的算法，确定树中第k小的结点的位置。

在平衡二叉树的每个结点中增设一个数据成员Isize，存储以该结点为根的左子树中的结点个数加一的值。编写一个算法，确定树中第k（k≥1)个结点的位置。

设有一个双向链表，每个结点中除有prior、 data 和next域外，还有一个访问频度freq域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次Locata（L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locata（L,x)算法。

₀;则树的最大高度为()，其叶结点数为();树的最小高度为()，其叶结点数为();若采用链表存储结构，则有()个空链域。

A、n/2

B、

C、log2ⁿ

D、n

E、n₃+n₁+n₂

F、1+n₂

G、n₂+1

H、1

L、n+1

J、n₁

K、n₂

L、n₁+1

编写一个递归算法，从大到小输出二叉搜索树中所有值不小于x的关键码。要求算法的时间复杂度为O（log₂n+m)，n为树中结点数，m为输出的关键码个数。

gth。并以图8-27为例，验证新算法的正确性。

的思想是在遍历过程中沿着结点的左子女或右子女方向“下降”时，临时改变其leftChild或rightChild的值，使之指向该结点的父结点，从商为以后的“上升”提供路径;在上升的过程中将结点的leftChild或rightChild的值恢复原来的值。为了在上升的过程中区分是从该结点的左子树上升的还是从右子树上升的，在结点中设置一个tag标志。进人算法时，所有结点的tag设为0，当遍历过程中进入结点的左子树时，将该结点的tag置为l、从左子树退出进人右子树时再将该结点的tag置为0.

树插入一个元素时，若树中已存在与该元素的关键码柑同的结点，则就使该结点的count域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入要求编写一个算法。