[数据结构与算法]二叉树高度，宽度

二叉树采用二叉链表存储：

1. 编写计算二叉树高度的算法(二叉树的高度也叫二叉树的深度)。
2. 编写计算二叉树的最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。

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

二叉树高度

int high(Tree *t){
    Tree *p = t;
    int HL;   //左子树高度
    int HR;   //右子树高度
    if(!p)
        return 0;
    HL = high(p->lchild);
    HR = high(p->rchild);
    return HL>HR?HL+1:HR+1;
}

二叉树宽度

typedef struct{
     Node *data[SIZE];
     int front, rear;
 }Queue;

void init(Queue *q){
    q->front = 0;
    q->rear = -1;
}

void push(Queue *q, Node *node){
    if(q->rear > SIZE)
        printf("满\n");
    q->data[++q->rear] = node;
}

Node* pop(Queue *q){
    if(q->front-1 == q->rear)
        printf("空\n");
    
    Node *m = q->data[q->front];
    q->front++;
    return m;
}

int empty(Queue *q){
    if(q->rear + 1 == q->front)
        return 1;
    else return 0;
}


int width(Tree *T)
{
	int last, max = 0;   
	//last 表示一层中最后一个元素的位置
	
    Queue q;
    init(&q);    //队列初始化

	Node *p = T;
	
	push(&q,p);    //入队
	last = q.rear;
    int temp = 0;
	while (!empty(&q))
	{
		p = pop(&q);   //出队
        temp++;
		if (p->lchild)
			push(&q, p->lchild);
		if (p->rchild)
			push(&q, p->rchild);
		if (q.front > last)
		{
			last = q.rear;
            max = max>temp?max:temp;
            temp = 0;
		}
	}
	return max;
}