数据结构考研分类复习真题 第六章 答案 (五)[19]

int Level(BiTree bt) //层次遍历二叉树并统计度为的结点的个数

{int num=; //num统计度为的结点的个数

if(bt){QueueInit(Q); QueueIn(Qbt)//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q); printf(p>data); //出队访问结点

if(p>lchild && !p>rchild ||!p>lchild && p>rchild)num++;//度为的结点

if(p>lchild) QueueIn(Qp>lchild); //非空左子女入队

if(p>rchild) QueueIn(Qp>rchild); //非空右子女入队

} }//if(bt)

return(num); }//返回度为的结点的个数

void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换

{if(bt){BiTree s

s=bt>lchild; bt>lchild=bt>rchild; bt>rchild=s; //左右子女交换

exchange(bt>lchild); //交换左子树上所有结点的左右子树

exchange(bt>rchild); //交换右子树上所有结点的左右子树

} }

[算法讨论]将上述算法中两个递归调用语句放在前面将交换语句放在最后则是以后序遍历方式交换所有结点的左右子树中序遍历不适合本题下面是本题（）要求的非递归算法

（）void exchange(BiTree t) //交换二叉树中各结点的左右孩子的非递归算法

{int top=; BiTree s[]p; //s是二叉树的结点指针的栈容量足够大

if(bt)

{s[++top]=t;

while(top>)

{t=s[top];

if(t>lchild||t>rchild){p=t>lchild;t>lchild=t>rchild;t>rchild=p;}//交换左右

if(t>lchild) s[++top]=t>lchild; //左子女入栈

if(t>rchild) s[++top]=t>rchild; //右子女入栈

}//while(top>)

}//if(bt) }// 结束exchange

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []