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); } } /**********