82.png

    1. /*
    2.     假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度
    3.     分析：
    4.         若要采用非递归的方式来求得二叉树的高度，我们采用层次遍历是最合适的，因为这一层一层的不就很好数吗哈哈。具体实现：
    5.         这里唯一的难点就在于我们如何得知高度该加一了；我们可以设置一个标志num用来记录每一层入栈的节点个数，当我们出栈数
    6.         达到该数值时也就意味着我们的高度该加一了
    7. */
    8. struct biTree {
    9.     char data;
    10.     struct biTree *lchild;
    11.     struct biTree *rchild;
    12. };
    13. struct Squeue {
    14.     biTree *arr;
    15.     int front, rear;
    16. };
    18. #include <stdio.h>
    19. #include <stdlib.h>
    21. int getHigh(biTree *T,Squeue *sq,int maxSize) {
    22.     int oldNum=0,curNum=0,high=0;//记录一层有多少节点
    23.     struct biTree *p = T;
    24.     struct biTree *r=(struct biTree *)malloc(sizeof(struct biTree));
    25.     bool enQueue(Squeue *, biTree *, int );
    26.     bool isEmpty(Squeue *);
    27.     bool deQueue(Squeue *, biTree **, int);
    29.     enQueue(sq,p,maxSize);//将根节点入队
    30.     oldNum++;//此时队列中只有一个节点
    32.     while (!isEmpty(sq)) {
    33.         deQueue(sq,&r,maxSize);//取出队首元素
    34.         if (r->lchild) {
    35.             curNum++;//下一层的节点数+1
    36.             enQueue(sq, r->lchild, maxSize);//将节点入队
    37.         }
    38.         if (r->rchild) {
    39.             curNum++;//下一层的节点数+1
    40.             enQueue(sq, r->rchild, maxSize);//将节点入队
    41.         }
    42.         if (!--oldNum) {//如果一层的元素已取完，高度+1
    43.             high++;
    44.             oldNum = curNum;//当oldNum=0时，将下一层的节点数赋给它
    45.             curNum = 0;//下一层节点归零
    46.         }
    48.     }
    49.     return high;
    50. }
    51. int main() {
    52.     int count=0;
    53.     //创建二叉树、队列
    54.     struct biTree *T=(struct biTree *)malloc(sizeof(struct biTree));
    55.     struct Squeue *sq;
    56.     biTree *create(biTree *);
    57.     void nodeNum(biTree *,int *);
    58.     Squeue *createQueue(int);
    59.     T = create(T);
    60.     nodeNum(T,&count);
    61.     sq = createQueue(count);//创建一个大小为树节点个数的队列
    63.     printf("该二叉树的高度为：%d",getHigh(T, sq, count));
    64.     return 0;
    65. }