华中科技大学：数据结构：作业解答_树

数据结构作业
2002 年第六章 树
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);
}
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);
}
错误算法，导致不能访问右子树的结点
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;
}
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);
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 完全二叉树,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 (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”
};