数据结构算法设计题目详解

数据结构算法设计题目详解

木来 木来

五、算法题

166交换二叉树每个结点的左孩子和右孩子。

void ChangeLR(BiTree &T)
{
        BiTreetemp;
        if(T->lchild==NULL&&T->rchild==NULL)
                 return;
        else
        {
                 temp= T->lchild;
                 T->lchild= T->rchild;
                 T->rchild= temp;
        }//交换左右孩子
        ChangeLR(T->lchild);  //递归交换左子树
        ChangeLR(T->rchild);  //递归交换右子树
}

 

167用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。

int Level(BiTree bt) //层次遍历二叉树,并统计度为1的结点的个数
{int num=0; //num统计度为1的结点的个数
 if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列
while(!QueueEmpty(Q))
{p=QueueOut(Q);cout<<p->data;     //出队,访问结点
if(p->lchild && !p->rchild||!p->lchild && p->rchild)num++;
//度为1的结点
if(p->lchild) QueueIn(Q,p->lchild);//非空左子女入队
if(p->rchild) QueueIn(Q,p->rchild);//非空右子女入队
} // while(!QueueEmpty(Q))
}//if(bt)         
return(num); 
}//返回度为1的结点的个数

 

168设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写出进行非递归的前序遍历算法。

voidPreOrder(ElemType bt,int n)//对以顺序结构存储的完全二叉树bt进行前序遍历
{inttop=0,s[];  //top是栈s的栈顶指针,栈容量足够大
while(i<=n||top>0)
  {while(i<=n)
{ printf(bt[i]);                   //访问根结点;
      if(2*i+1<=n) s[++top]=2*i+1;    //右子女的下标位置进栈
      i=2*i; }                         //沿左子女向下
      if(top>0) i=s[top--]; }           //取出栈顶元素
}
}//结束PreOrder

169要求二叉树按二叉链表形式存储,写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为:深度为K,具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。

^^[题目分析]二叉树是递归定义的,以递归方式建立最简单。判定是否是完全二叉树,可以使用队列,在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。

intJudgeComplete(BiTree bt)  //判断二叉树是否是完全二叉树,如是,返回1,否则,返回0
{inttag=0; BiTree p=bt, Q[]; // Q是队列,元素是二叉树结点指针,容量足够大
if(p==null)  return (1);
QueueInit(Q);QueueIn(Q,p);  //初始化队列,根结点指针入队
while(!QueueEmpty(Q))
{p=QueueOut(Q);                           //出队
 if (p->lchild && !tag)   QueueIn(Q,p->lchild);  //左子女入队
 else {if (p->lchild)   return 0;                //前边已有结点为空,本结点不空
     else tag=1;                             //首次出现结点为空
 if (p->rchild && !tag)QueueIn(Q,p->rchild);  //右子女入队
 else if (p->rchild) return 0; 
else tag=1; 
} //while
return 1;  } //JudgeComplete
0 条评论