if(T->Child)Get Sub Depth(T->lchild, x) if(T-> achild) Get Sub Depth(T-> Achild,x),∥在左右子树中继续寻找 i//Get Sub Depth int Get Depth( Bitree T∥求子树深度的递归算法 if(!T) return 0 else m=Get Depth(T->lchild) n=Get Depth(T->rchild return(m>n?m n)+1 1//Get Depth 645 void del sub x( Bitree T, int x)删除所有以元素ⅹ为根的子树 if(T->data=x) Del sub(D),/删除该子树 if(T->lchild)Del Sub x(T->lchild, x); f(-> achild) Del sub x(T-> rchild,x,∥在左右子树中继续查找 i//else i//Del Sub X void Del sub( Bitree T删除子树T if(T->lchild) Del Sub(T->lchild ) if(T->rchild)Del Sub(T->rchild ); freeT) i//Del Sub void Bitree Copy Nonrecursive( Bitree T, Bitree&U∥非递归复制二叉树 Init Stack(S 1), Init Stack (S2) push(S1,D,∥根指针进栈 U=(BTNode*)malloc(sizeof(BTNode)) U->data=T->data
else { if(T->lchild) Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 } }//Get_Sub_Depth int Get_Depth(Bitree T)//求子树深度的递归算法 { if(!T) return 0; else { m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; } }//Get_Depth 6.45 void Del_Sub_x(Bitree T,int x)//删除所有以元素 x 为根的子树 { if(T->data==x) Del_Sub(T); //删除该子树 else { if(T->lchild) Del_Sub_x(T->lchild,x); if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找 }//else }//Del_Sub_x void Del_Sub(Bitree T)//删除子树 T { if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); }//Del_Sub 6.46 void Bitree_Copy_Nonrecursive(Bitree T,Bitree &U)//非递归复制二叉树 { InitStack(S1);InitStack(S2); push(S1,T); //根指针进栈 U=(BTNode*)malloc(sizeof(BTNode)); U->data=T->data;
q=U: push(S2, 0); while(!Stack Empty(s) while(Gettop(Sl, p)&&p) q->lchild=(BTNode*)malloc(sizeof(BTNode)); q->lchild; ->data=p->data; bush(sl, p->lchild) bush(s2, 9) }/向左走到尽头 pop(Sl, P); pop(S2, 9); if(!Stack Empty(S1) pop(Sl, p): pop(S2, 9); ->rchild=(BTNode*)malloc(sizeof(B TNode)); q=q->rchild; q->data=p->data; push(S1,p> rchild),∥向右一步 push(S2, q) i //while 3//BiTree Copy_ Nonrecursive 分析本题的算法系从6.37改写而来 6.47 void LayerOrder(Bitree T)层序遍历二又树 InitQueue(Q),∥建立工作队列 EnQueue(Q, T) while(!QueueEmpty(Q)) DeQueue(Q,p); isit(p); if(p->lchild) En Queue(Q p->lchild) (p->rchild) EnQueue(Q, p->rchild ) g//LayerOrder int found=FAlSE Btee* Find Near Ancient( Bitree T, Bitree p, Bitree q)∥求二叉树T中结点p和q的 最近共同祖先
q=U;push(S2,U); while(!StackEmpty(S)) { while(Gettop(S1,p)&&p) { q->lchild=(BTNode*)malloc(sizeof(BTNode)); q=q->lchild;q->data=p->data; push(S1,p->lchild); push(S2,q); } //向左走到尽头 pop(S1,p); pop(S2,q); if(!StackEmpty(S1)) { pop(S1,p);pop(S2,q); q->rchild=(BTNode*)malloc(sizeof(BTNode)); q=q->rchild;q->data=p->data; push(S1,p->rchild); //向右一步 push(S2,q); } }//while }//BiTree_Copy_Nonrecursive 分析:本题的算法系从 6.37 改写而来. 6.47 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 6.48 int found=FALSE; Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q)//求二叉树 T 中结点 p 和 q 的 最近共同祖先