82.png

    1. /*
    2.     假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树的宽度（即具有节点数最多的那一层的节点个数）
    3.     分析：
    4.         这道题和求高度那道题大同小异。我们仍然可以采取层次遍历，统计每一层的节点个数，找到宽度最大的那一层。
    5. */
    6. struct biTree {
    7.     char data;
    8.     struct biTree *lchild;
    9.     struct biTree *rchild;
    11. };
    12. struct LinkQueue {//上次求高度采用的是顺序队列，这次采用链式队列，雨露均沾哈哈
    13.     struct Link *front, *rear;
    14. };
    16. #include <stdio.h>
    17. #include <stdlib.h>
    19. int getWidth(biTree *b, LinkQueue *lq) {
    20.     int oldNum = 0, curNum = 0, width = 0;;
    21.     bool enQueue(LinkQueue *lq, biTree *node);
    22.     bool deQueue(LinkQueue *lq, biTree **node);
    23.     bool isEmpty(LinkQueue *lq);
    24.     struct biTree *p = b;
    25.     struct biTree *r=(struct biTree*)malloc(sizeof(struct biTree));
    26.     if (p) {
    27.         enQueue(lq, p);//入队
    28.         oldNum++;
    29.         width = 1;
    30.         while (!isEmpty(lq)) {
    31.             while (oldNum--) {
    32.                 deQueue(lq, &r);//队首元素出队
    33.                 if (r->lchild) {//若有左孩子，将左孩子入队
    34.                     enQueue(lq, r->lchild);
    35.                     curNum++;//当前队列元素加1
    36.                 }
    37.                 if (r->rchild) {//若有右孩子，将右孩子入队
    38.                     enQueue(lq, r->rchild);
    39.                     curNum++;//当前队列元素加1
    40.                 }
    41.             }
    42.             curNum > width ? width = curNum : NULL;//如果当前队列元素多于之前的，宽度变更
    43.             oldNum = curNum;//继续进行操作
    44.             curNum = 0;
    46.         }
    48.     }
    49.     return width;
    50. }
    51. int main() {
    52.     struct biTree *b = (struct biTree*)malloc(sizeof(struct biTree));
    53.     struct LinkQueue *lq;
    55.     biTree *create(biTree *);
    56.     b = create(b);//创建一颗二叉树
    58.     LinkQueue *create();
    59.     lq = create();//创建链式队列
    61.     printf("该二叉树的宽度为：%d",getWidth(b, lq));
    62.     return 0;
    63. }