试完成编码表生成算法coding。根结点指针root指向的是...

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

【Test-9-3】假设二叉树存放于二叉链表中，树中结点的关键字值互不相同。下面算法的功能是：判别给定的二叉树是否二叉排序树。请在空白处填入正确的语句。 void binSearchTree(BiTNode *t, BiTNode *&pr, int& bs) { //在以 t 为根的子树中判断该子树是否二叉排序树。是则引用参数 bs 为 1，否则 bs //为 0。引用参数 pr 是当前子树根结点 t 的前驱指针，在主调程序中应为各参数初 //始化： t 赋予根结点指针 root， pr 赋予 NULL， bs 赋予 1。 if(t != NULL && bs) { _______________①_________________; //递归到左子树判断 if(pr == NULL) { pr = t; //t 为中序第一个结点 bs = 1; } else { if(__________②___________) { pr = t; bs = 1; } else bs = 0; } if(bs) ____________③__________________; //递归到右子树判断 } }

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

已知一棵度为12的树，它的根结点的地址为root。该树是用顺序方式存储的，说明如下： struct node{ int data; ／／树中结点的数据场 int son[12]； ／／给出结点的第1个，第2个，第3个……第12个儿子结点地址 }tnode[M]； ／／M是树中结点数，常量 请设计一个非递归的程序，按前序遍历该树，打印每个结点的数据场之值。注意：如用递归程序实现，做零分处理。【上海交通大学2003一(15分)】

二叉树的遍历算法可写为通用形式。例如，通用的中序遍历为：

  void Inorder(BinTree T，void(*Visit)(Datatype x))

  { if(T)

    {Inorder(T-＞lchild，Visit);  /*遍历左子树*/

    Visit(T-＞data)；  /*通过函数指针调用它所指的函数来访问结点*/

    Inorder(T-＞rchild，Visit)；  /*遍历右子树*/

    }

  }

  其中Visit是一个函数指针，它指向形如void f(DdataType x)的函数。因此我们可以将访问结点的操作写在雨数f中，通过调用语句Inorder(root，f)将f的地址传递给Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成中序遍历。

设二叉树以二叉链表方式存储，试完成下列问题的递归算法。 设二叉树结点和二叉树结构体定义如下： typedef struct btnode { ElemType element; struct btnode* lchild, *rchild; }BTNode; typedef struct binarytree{ BTNode* root; }BinaryTree; （1）求一棵二叉树的高度； int Depth(BTNode *p) { int lh, rh; if (!p) return 0; lh = ______________; rh = _____________; if (lh > rh) return _________; else return ________; } int DepthofBT(BinaryTree Bt) { return ___________; } （2）求一棵二叉树中的结点个数； int Size(BTNode * p) { if (!p) return _____ ; else return Size(p->lchild)+______________+1; } int SizeofBT(BinaryTree Bt) { return ______________); } （3）交换一棵二叉树中每个结点的左、右子树。 void exchange ( BTNode * p) { if(!p) return; if ( p->lchild != NULL || p->rchild != NULL ) { temp = p->lchild; p->lchild = ____________; p->rchild = temp; exchange (___________ ); exchange ( p->rchild ); } } void exchange(BinaryTree *bt) { ____________________; }

以下哪项不是BPDI．J数据包中携带的实现生成树算法的相关信息?——

A．Root ID

B．IP

C．Root Path Cost．

D．Port ID

阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左

子树分支向下查找，直到某个结点不存在左子树时为止，该结点即为此二叉树的“最左下”结点。例如，下图所示的以 A为根的二叉树的“最

左下”结点为D，以C为根的子二叉树中的“最左下”结点为C。

二叉树的结点类型定义如下：

typedef stmct BSTNode{

int data；

struct BSTNode*lch,*rch；//结点的左、右子树指针

}*BSTree；

函数BSTree Find Del(BSTree root)的功能是：若root指向一棵二叉树的根结点，则找出该结点的右子树上的“最左下”结点*p，并从

树于删除以*p为根的子树，函数返回被删除子树的根结点指针；若该树根的右子树上不存在“最左下”结点，则返回空指针。

【函数】

BSTrce Find_Del(BSTreeroot)

{ BSTreep,pre；

if ( !root ) return NULL； /*root指向的二叉树为空树*/

(1)； /*令p指向根结点的右子树*/

if ( !p ) return NULL；

(2)； /*设置pre的初值*/

while(p-＞lch){ /*查找“最左下”结点*/

pre=p；p=(3)；

}

if ((4)==root) /*root的右子树根为“最左下”结点*/

pre-＞rch=NULL；

else

(5)=NULL； /*删除以“最左下”结点为根的子树*/

reurn p；

}