2016最新广工anyview数据结构答案

while(true) {

while(se.ptr!=NULL) { if(se.ptr->data==e) return ; Push(s,se);

se.ptr=se.ptr->lchild; }

while(!StackEmpty(s)) { Pop(s,se);

if(se.ptr->data==e)return ; if(se.ptr->rchild) { if(se.tag==0) { se.tag=1; Push(s,se); se.tag=0;

se.ptr=se.ptr->rchild;

break; } } }

if(StackEmpty(s))return ; } }

BiTree CommAncestor(BiTree T, TElemType a, TElemType b)

/* 求二叉树T中结点a和b的最近共同祖先 */ {

Stack sa,sb,s; SElemType ea,eb; BiTree ta,tb;

InitStack(sa);InitStack(sb);InitStack(s);

findElem(T,a,sa); findElem(T,b,sb); while(!StackEmpty(sa)){ Pop(sa,ea); ta=ea.ptr; s=sb;

while(!StackEmpty(s)){ Pop(s,eb); tb=eb.ptr;

if(ta->data==tb->data) return ta; } } } /**********

【题

目】在二叉排序树的每个结点中增设一个lsize域， 其值为该结点的左子树中的结点数加1。试编写时间复杂 度为O(logn)的算法，求树中第k小的结点的位置。 二叉排序树的类型BSTree定义如下： typedef char KeyType; typedef struct BSTNode { KeyType key;

struct BSTNode *lchild,*rchild;

int lsize; // 新增域，值为左子树的结点数+1 } BSTNode, *BSTree; **********/

BSTNode* Ranking(BSTree T, int k) /* 在含lsize域的二叉排序树T中，*/ /* 求指向T中第k小的结点的指针 */