143-5

非递归求树高

current记录每次入队出队操作后队列中结点数，每一个结点出队时--，每一个结点入队时++

previous记录每层结点数，出队操作时--

当previous==0时，即队列中不存在该层结点且当前队列中是下一层结点。此时，high++。让previous=current，使得previous记录下一层结点数

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct TreeNode{
    int data;
    struct TreeNode *lchild,*rchild;
}TreeNode,*Tree;

typedef TreeNode* Elem;

typedef struct{
    Elem data[MaxSize];
    int front;
    int rear;
}Queue;

void InitQueue(Queue &Q)
{
    Q.front=Q.rear=0;
}

bool isEmpty(Queue Q)
{
    if(Q.front==Q.rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool isFull(Queue Q)
{
    if((Q.rear+1)%MaxSize==Q.front)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool EnQueue(Queue &Q,Elem p)
{
    if(isFull(Q))
    {
        return false;
    }
    Q.data[Q.rear]=p;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

bool DeQueue(Queue &Q,Elem &p)
{
    if(isEmpty(Q))
    {
        return false;
    } 
    p=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

//先序创建二叉树
void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(Tree)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点：",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点：",x);
        CreateTree(T->rchild);
    }
}

int High(Tree T)                    //递归实现求树高 
{
    int high=0;
    if(T!=NULL)
    {
        int lefthigh=High(T->lchild);
        int righthigh=High(T->rchild);
        high=lefthigh>=righthigh?lefthigh+1:righthigh+1;
    }
    return high;
}

int HighByQueue(Tree T)        //非递归遍历求树高 
{
    Queue Q;
    InitQueue(Q);
    TreeNode *p=T;
    EnQueue(Q,p);
    int current=1,previous=1;
    int high=0;
    while(!isEmpty(Q))
    {
        DeQueue(Q,p);
        previous--;
        current--;
        if(p->lchild)
        {
            EnQueue(Q,p->lchild);
            current++;
        }
        if(p->rchild)
        {
            EnQueue(Q,p->rchild);
            current++;
        }
        if(previous==0)
        {
            high++;
            previous=current;
        }    
    }
    return high;
} 

int main()
{
    Tree T;
    CreateTree(T);
    printf("%d\n",High(T));
    printf("%d\n",HighByQueue(T));
    return 0;    
}