华中科技大学：《C语言程序设计》作业解答-树

大点 20023

数据结构作业 2002 年 第六章 树

643编写递归算法,将二叉树中所有结点的左右子树相互交换。 void change( Bitree*T)/根据先根遍历 i BiTree "p if(T p=T->lchild T->lchild= T->rchild T->rchild=p change(T->lchild) change(T->rchild)

6.43 编写递归算法，将二叉树中所有结点的左右子树相互交换。 void change(BiTree *T) //根据先根遍历 { BiTree *p; if (T) { p=T->lchild; T->lchild= T->rchild; T->rchild=p; change(T->lchild); change(T->rchild); }

643编写递归算法,将二叉树中所有结点的左右子树相互交换。 void change( BITree*T)∥根据中根遍历 i BiTree "p if(T 错误算法,导致不能访问右 子树的结点 change(T->lchild) p=T->lchild T->lchild= T->rchild T->rchild=p change(T->rchild)

6.43 编写递归算法，将二叉树中所有结点的左右子树相互交换。 void change(BiTree *T) //根据中根遍历 { BiTree *p; if (T) { change(T->lchild); p=T->lchild; T->lchild= T->rchild; T->rchild=p; change(T->rchild); } 错误算法，导致不能访问右 子树的结点

643编写递归算法,将二叉树中所有结点的左右子树相互交换。 void change( BiTree*T)/根据后根遍历 i BiTree "p if(T change(T->lchild) change(T->rchild) p=T->lchild T->lchild= T->rchild T->rchild=p

6.43 编写递归算法，将二叉树中所有结点的左右子树相互交换。 void change(BiTree *T) //根据后根遍历 { BiTree *p; if (T) { change(T->lchild); change(T->rchild); p=T->lchild; T->lchild= T->rchild; T->rchild=p; }

644编写递归算法,求三叉树中以元素值为x的结点为根的子树的 深度。 int dep( BiTree*r; Elem Type x,int*h)∥根据后根遍历 i int h1, h2 if( T) f hl=dep(t->lchild, x, h); h2=dep(t->rchild, x, h) if (T->data==)*h=h1h2? h1+1: h2+ return hI>h2? h1+1: h2+1 main i hight=0: de lep(root, x, &hight

6.44 编写递归算法，求二叉树中以元素值为x的结点为根的子树的 深度。 int dep(BiTree *T,ElemType x, int *h) //根据后根遍历 { int h1,h2; if (T) { h1=dep(T->lchild , x , h); h2=dep(T->rchild ,x , h); if (T->data==x) *h=h1>h2? h1+1 :h2+1; return h1>h2? h1+1 :h2+1; } main() { hight=0; dep(root,x,&hight);

649编写算法,到断一义树是否为全树之 int com(BiTree * T) i int flag=l; Init Queue(Q); EnQueue(Q,T) while ( empty Queue(Q)) i DeQueue(Q,p) if(p->lchild)if (flag) EnQueue(Q,p >lchild) else return No flag=0 if(p->rchild) if (flag) EnQueue(Q, p >rchild) else return NO else flag=0 return YES; I

6.49 编写算法，判断二叉树是否为完全二叉树。 int com(BiTree *T) { int flag=1; InitQueue(Q); EnQueue(Q,T); while (! emptyQueue(Q)) { DeQueue(Q,p); if (p->lchild ) if (flag) EnQueue(Q,p_>lchild); else return NO; else flag=0; if (p->rchild) if (flag) EnQueue(Q,p_>rchild); else return NO; else flag=0; } return YES;}

1递归算害、根据后根遍历 ∥返回值:1完全二叉树、2满二叉树、0其他 int com(BiTree *T, int *h) f int h1, h2, k1, k2 if(T)i *h=0; return 2; 1 kI=com(T->lchild, &hl) k2-=com(T->rchild, &h2) *h=h1>h2?h1+1:h2+1 if (hl==h2) ∥右子树高度相等 if(k1=2&&k2=1) return1;∥左满二叉树,右完全二叉树 else if(k1=2&&k2=2) return2;∥左、右满二叉树,且等高度 else return O

//递归算法，根据后根遍历 //返回值：1 完全二叉树、2 满二叉树、0 其他 int com(BiTree *T, int *h) { int h1,h2,k1,k2; if (!T) { *h=0; return 2; } k1=com(T->lchild , &h1); k2=com(T->rchild , &h2); *h=h1>h2? h1+1 :h2+1; if (h1==h2 ) //左右子树高度相等 if(k1==2 && k2==1) return 1; //左满二叉树，右完全二叉树 else if(k1==2 &&k2==2) return 2; //左、右满二叉树，且等高度 else return 0;

∥左子树高度=右子树高度+1 else if(h=h+1&&(k1==1‖kl=2)&&k2=2) return 1 return o maino f int hight printf ("%s, com(root, &hight)>0?YES: NO

//左子树高度=右子树高度+1 else if (h1==h2+1 && (k1= =1 || k1==2) && k2== 2) return 1; else return 0; } main() { int hight; printf ( “%s”, com(root, &hight)>0 ? “YES”: “NO” };