1.交换所有结点的左右子树
void Bitree_Revolute(Bitree T)
{
T->lchild<->T->rchild; //交换左右子树
if(T->lchild) Bitree_Revolute(T->lchild);
if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树
}//Bitree_Revolute
2.编写算法判别给定二叉树是否为完全二叉树。
int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0
{
InitQueue(Q);
flag=0;
EnQueue(Q,T); //建立工作队列
while(!QueueEmpty(Q))
{
{
DeQueue(Q,p);
if(!p) flag=1;
else if(flag) return 0;
else
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列
}
}//while
return 1;
}//IsFull_Bitree
分析:该问题可以通过层序遍历的方法来解决,不管当前结点
是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针
void Bitree_Revolute(Bitree T)
{
T->lchild<->T->rchild; //交换左右子树
if(T->lchild) Bitree_Revolute(T->lchild);
if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树
}//Bitree_Revolute
2.编写算法判别给定二叉树是否为完全二叉树。
int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0
{
InitQueue(Q);
flag=0;
EnQueue(Q,T); //建立工作队列
while(!QueueEmpty(Q))
{
{
DeQueue(Q,p);
if(!p) flag=1;
else if(flag) return 0;
else
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列
}
}//while
return 1;
}//IsFull_Bitree
分析:该问题可以通过层序遍历的方法来解决,不管当前结点
是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针