#include "stdafx.h"

#include <iostream>

#define OK 1

#define ERROR 0

#define OVERFLOW -1

#define UNDERFLOW -2

using namespace std;

typedef char TElemType;

typedef int Status;

typedef struct BiTNode { // 结点结构

	TElemType         data;

	int level; //用于层序遍历求深度

	struct BiTNode  *lchild, *rchild; //左右孩子指针

}BiTNode, *BiTree;

BiTree T;

typedef BiTNode *ElemType;

typedef struct QNode {// 结点类型

	ElemType      data;  //数据域

	struct QNode    *next;  //指针域

}QNode, *QueuePtr;

typedef struct { // 链队列类型

	QueuePtr  front;  // 队头指针

	QueuePtr  rear;   // 队尾指针

}LinkQueue;

LinkQueue Q;

Status InitQueue(LinkQueue &Q) {

	// 构造一个空队列Q

	Q.front = Q.rear = new QNode;

	Q.front->next = NULL;//或Q.rear->next=NULL

	return OK;

}

Status EnQueue(LinkQueue &Q, ElemType  e) {

	// 插入元素e为Q的新的队尾元素

	QueuePtr s = new QNode;

	s->data = e;   s->next = NULL;

	Q.rear->next = s;    Q.rear = s;

	return OK;

}

Status DeQueue(LinkQueue &Q, ElemType  &e) {

	//若队列不空，则删除Q的队头元素，

	//用 e 返回其值，并返回OK；否则返回ERROR

	if (Q.front == Q.rear)    return ERROR;//空队列

	QueuePtr p = new QNode;

	p = Q.front->next;   e = p->data; //非空队列

	Q.front->next = p->next;

	if (p->next == NULL)  Q.rear = Q.front;

	//若删除前只有一个结点，则删除后成为空队列

	delete p;      return OK;

}

Status QueueEmpty(LinkQueue Q) {//是否为空队

	return Q.rear == Q.front;

}

void CreateBiTree(BiTree &T) {

	char c;

	cin >> c;

	if (c == '#')

		T = NULL;

	else

	{

		T = new BiTNode;

		T->data = c;

		cout << "请输入" << c << "的左孩子：";

		CreateBiTree(T->lchild);

		cout << "请输入" << c << "的右孩子：";

		CreateBiTree(T->rchild);

	}

}

//层序遍历求二叉树深度

int LevelDepth(BiTree T) {

	int h;//暂存当前访问到的层次

	if (!T)

		h = 0;//空树

	else {

		LinkQueue Q;

		ElemType p;

		InitQueue(Q);//初始化队列

		T->level = 1;//根的层序1

		EnQueue(Q, T);//根指针入队

		while (!QueueEmpty(Q)) {

			DeQueue(Q, p);

			h = p->level;

			if (p->lchild) {

				p->lchild->level = h + 1;//左孩子层次加1

				EnQueue(Q, p->lchild);

			}

			if (p->rchild) {

				p->rchild->level = h + 1;//右孩子层次加1

				EnQueue(Q, p->rchild);

			}

		}

	}

	return h;

}

int main() {

	TElemType e;

	cout << "\t\t\t\t*\t\t\t\t\t*";

	cout << endl << "\t\t\t\t*\t计科1512-02210151232-杨少通\t*" << endl;

	cout << "\t\t\t\t*****************************************" << endl << endl;

	cout << "首先创建二叉树（若结点不存在请输入“#”）。" << endl << endl;

	//创建二叉树

	cout << "请输入根结点：";

	CreateBiTree(T);

	cout << endl << "二叉树的深度（层序遍历法）：";

	cout << LevelDepth(T);

	cout << endl;

	return 0;

}