若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK 、中序遍历(左、根、右)序列为HFIEJKG, 则该二叉树根结点的左孩子结点和右孩子结点分别是（）。

A.A,I.KB.F,IC.F,GD.I,G

A.1.0

B.2.9

C.3.4

D.5

A.6

B.10

C.12

D.15

A.6

B.8

C.12

D.14

设一棵二叉树的结点结构为(LLINK，INFO，RLINK)，ROOT为指向该二叉树根结点的指针，p和g分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR(RDOT，p，q，r)，该算法找到p和q的最近共同祖先结点r。【吉林大学2000二、3(12分)】【中山大学1994六(15分)】

数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性： (1)树根不包含元素。 (2)其左子树是一小堆(MIN HEAP)，其右子树是一大堆(MAX HEAP)。 (3)若右子树非空，设i是左子树的任一结点，j是右子树中与i相应的结点。若这样的j结点不存在，则取j为右子树中与i的父结点相对应的结点；结点i的关键字值总是小于或等于结点j的关键字值。一个DEAP的例子如右图所示。

与结点15相对应的结点为20，与结点19对应的结点为25。 (1)给出在该DEAP中插

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

若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树共有（）个叶子结点。

A．17

B．18

C．19

D．20

A.2n

B.2n-1

C.2n+l

D.2n+2

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