来自大佬群主的第二题

所谓层次遍历，是将二叉树中的元素从根节点按照节点层数一层层的输出。

代码如下：

int GetDepth(bitreenode *root)
{
    int depth=0;
    bitreenode *p=root;
    queue<bitreenode*> q;
    q.push(p);  //根指针入队
    while(!q.empty())
    {
        depth++;  //高度加一
        int width=q.size();  //获取当前层次宽度
        for(int i=0;i<width;i++)
        {
            p=q.front();  //获取队顶元素
            q.pop();  //弹出队顶元素
            if(p->leftchild!=NULL)  //左孩子入队
                q.push(p->leftchild);
            if(p->rightchild!=NULL)  //右孩子入队
                q.push(p->rightchild);
        }

    }
    cout<<depth<<endl;
}

int Btdepth(Bitreee T){
    if(!T)
        return 0;                           //如果是空树，则高度为1；
    int front =-1,rear=-1;                  //定义顺序队列，队列元素是二叉树结点指针，用于层序访问链式二叉树；
    BiTree Q[MaxSize];

    int last=0,level=0;                     //last表示当前层的最右节点在队列中的序号。level用于计算数地高度。
    Q[++rear]=T;                            //根节点进队
    BiTree p;
    while(front<rear){                      //队不空
        p=Q[++front];                       //出队
        if(p->lchild)                       //左右孩子入队
            Q[++rear]=p->lchild;
        if(p->rchild)
            Q[++rear]=p->rchild;
        if(front==last){                    //当出队到最右节点时，当前层次遍历完成，高度+1。更新新的最右节点的位置
            level++;
            last=rear;
        }
    }
    return level;
}

思路：

二叉树的高度等于层数，要求层数，只需找到每层最右节点的个数。

当队头指针=最右节点时，更新最右节点。因为此时队列中正好刚刚将下一层的所有结点都遍历了，此时的队尾结点就是要更新的最右节点。

循环结束条件同层序遍历结束条件，队空时跳出循环

递归和非递归方法（层次遍历）计算二叉树高度

1.递归方式计算二叉树高度

int Btdepth(BiTree T){
    if(!T) return 0;
    ldep=Btdepth(T->lchild);
    rdep=Btdepth(T->rchild);
    return ldep>rdep? ldep+1:rdep+1;
}

2.层次遍历方法计算二叉树高度：
算法思想：last指向每层最右结点，level为高度。从头节点开始，
边入队，然后再出队进行层次遍历，并将孩子结点入队，此时rear
指向下一层最右结点。而我们在出队遍历时，遍历完当前层front
指向的也是最右结点。所以在代码中，front==last作为判断遍历完
当前层的条件。rear指向的是下层的最右结点，故将last赋值为rear。

int Btdepth(BiTree T){
    if(!T) return 0;
    int last=0, level=0;
    int front=-1, rear=-1;
    BiTree Q[MaxSize];//设置队列Q，元素为二叉树的结点指针，且容量足够
    Q[++rear]=T;//根节点入队
    BiTree p;
    while(front<rear){//队不空则循环
        p=Q[++front];//队列元素出队，即正在访问的结点
        if(p->lchild) Q[++rear]=p->lchild;//左孩子入队
        if(p->rchild) Q[++rear]=r->rchild;//有孩子入队
        if(front==last){//处理该层的最右结点
            level++;//层数加1
            last=rear;//last指向下层
        }
    }
}