阅读以下说明和C函数,填补代码中的空缺(1)~(6)。
二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter[], counter[i]存放第i层上的结点数,并按照层次顺序来遍历二又树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。
按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BTNode{
TElemType data;
struct BTNode *left, *right;
}BTNode, *BiTree;
队列元素的类型定义如下:
typedef struct{
BTNode *ptr;
int LevelNumber;
}QElemType;
Get Width()函数中用到的函数原型如下所述,队列的类型名为 QUEUE:
InitQueue(QUEUE *Q):初始化一个空队列,成功时返回值为1,否则返回值0
isEmpty(QUEUE Q):判断队列是否为空,是空则为1,否则为0
EnQueue( QUEUE*Q, QElemType a):将元素a加入队列,成功返回值为1,否则返回值0
DeQueue(QUEUE *Q, QElemType *):删除队头元素,并通过参数带回其值,成功则返回值1,否则返回值0
GetHeight (BiTree root):返回值为二叉树的高度(即层次数,空二叉树的高度为0)
int Getwidth(BiTree root){
QUEUE Q;
QElemType a, b;
int width,height= GetHeight(root);
int i, *counter =(int *)calloc(height+1, sizeof (int));
if(__(1)__) return -1;/*申请空间失败*/
if(! root) return 0;/*空树的宽度为0*/
if(__(2)__) return -1;/*初始化队列失败时返回*/
a.ptr= root;
a.LevelNumber=1;
if(! EnQueue(&Q,a)) return -1;/*元素入队列操作失败时返回*/
while (! isEmpty(Q)){
if(__(3)__)return -1;/*出队列操作失败时返回*/
counter[b. LevelNumber]++;/*对层号为b. LevelNumber的结点计数*/
if(b.ptr->left){/*若左子树存在,则左子树根结点及其层次号入队*/
a.ptr= b.ptr->left;
a.LevelNumber=__(4)__;
if(!EnQueue(&Q,a)) return -1;
}
if(b.ptr-> right){/*若右子树存在,则右子树根结点及其层次号入队*/
a.ptr= b.ptr->right;
a. LevelNumber=__(5)__;
if(! EnQueue(&Q,a)) return -1;
}
}
width= counter[1];
for(i=1; i< height +1; 1++)/*求 counter[]中的最大值*/
if(__(6)__)width= counter [i];
free(counter);
return width;
}