广工数据结构anyview答案(8)

else q->rchild = p; } } }

int BiTreeDepth(BBSTree T) {

int dl,dr;

if(T==NULL) return 0; else {

dl = BiTreeDepth(T->lchild); dr = BiTreeDepth(T->rchild); return 1+(dl>dr? dl:dr); } }

int BiTree_bf(BBSTree T) {

int dl,dr;

if(T==NULL) return 0; else {

dl = BiTreeDepth(T->lchild); dr = BiTreeDepth(T->rchild); return dl-dr; } }

void SearchBST(BBSTree T) {

if(T==NULL) return ; else {

if(T->lchild!=NULL) {

T->bf = BiTree_bf(T); SearchBST(T->lchild); }

if(T->rchild!=NULL) {

T->bf = BiTree_bf(T);

SearchBST(T->rchild); } } }

/*****68***************************************** void PreOrder(BiTree T,Stack &S,TElemType x) {

InitStack(S); SElemType p,g; p.ptr = T;

while(p.ptr!=NULL){ if(p.ptr !=NULL) {

while(p.ptr != NULL) {

if(p.ptr->data == x) {

g.ptr = p.ptr; g.tag = 1; Push(S,g); return ; }

if(p.ptr->lchild !=NULL||p.ptr->rchild !=NULL) {

if(p.ptr->data == x) return ; if(p.ptr->data != x) {

g.ptr = p.ptr; g.tag = 1; Push(S,g); }

if(p.ptr->lchild !=NULL&&p.ptr->rchild !=NULL) //把不为空的右结点入栈

{

g.ptr = p.ptr->rchild; g.tag = 0; Push(S,g);

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

if(p.ptr->lchild ==NULL&&p.ptr->rchild !=NULL) {

g.ptr = p.ptr->rchild;

g.tag = 1; Push(S,g);

if(g.ptr->data == x) return ;//跳出 p.ptr = p.ptr->rchild; }

if(p.ptr->lchild !=NULL&&p.ptr->rchild ==NULL) {

g.ptr = p.ptr->lchild; g.tag = 1; Push(S,g);

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

}

else // if(p.tag==0) {

Pop(S, p);

while(StackEmpty(S) != TRUE&&p.tag==1)

Pop(S, p);

if(StackLength(S) == 0)

return ; //遍历到最后 }

} } } }

/**********

【题目】试编写算法，求二叉树T中结点a和b的最近共同祖先。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild,*rchild; } BiTNode, *BiTree;

可用栈类型Stack的相关定义： typedef struct {

BiTNode *ptr; // 二叉树结点的指针类型

int tag; // 0..1

} SElemType; // 栈的元素类型 Status InitStack(Stack &S); Status StackEmpty(Stack S); int StackLength(SqStack S);

Status Push(Stack &S, SElemType e); Status Pop(Stack &S, SElemType &e); Status GetTop(Stack S, SElemType &e); **********/

BiTree CommAncestor(BiTree T, TElemType a, TElemType b) /* 求二叉树T中结点a和b的最近共同祖先 */{ Stack S1,S2; SElemType la,lb; BiTree ib;

if(a<'A'||a>'Z') return NULL; if(b<'A'||b>'Z') return NULL;

if(T->data == a||T->data ==b) return NULL; if(a==b) return NULL;

if(T->lchild==NULL&&T->rchild==NULL) return NULL;

PreOrder(T, S1, a); PreOrder(T, S2, b);

if(StackEmpty(S1)==TRUE||StackEmpty(S2)==TRUE) return NULL; while(StackLength(S1)>StackLength(S2)) {

Pop(S1, la); }

while(StackLength(S1)

Pop(S2, lb); }

while(StackLength(S1)>0)

{ // StackEmpty(S1)!=TRUE最后栈空是la,lb还有就没办法比较，最后另外加一个判断

if(la.tag==1&&lb.tag==1&&la.ptr->data==lb.ptr->data) {

if(la.ptr->data==a||lb.ptr->data==b) {

Pop(S1, la); Pop(S2, lb); continue; }

if(la.ptr->data!=a&&lb.ptr->data!=b) return la.ptr;

} else {

Pop(S1, la); Pop(S2, lb); }

}

if(la.tag==1&&lb.tag==1&&la.ptr->data==lb.ptr->data) if(la.ptr->data!=a&&lb.ptr->data!=b) return la.ptr;

return NULL; }

/***75******************************* BBSTNode *Ranking_1(BBSTree T, int &k) {

BBSTree q = T;

if(q == NULL) return NULL; if(q->lsize > k) {

q = q->lchild;

return Ranking_1( q, k); } if(q->lsize == k) {

return q; } if(q->lsize < k) {

k = k- q->lsize; q = q->rchild; if(q->lsize == k) {

return q; }

return Ranking_1( q, k); } }

/**********

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库广工数据结构anyview答案(8)在线全文阅读。