本文共 2353 字，大约阅读时间需要 7 分钟。

注：本程序由Visual Studio 2015编写，与VC++6.0稍有区别，复制到VC++6.0注释掉“#include “stdafx.h””即可运行，复制到VS可直接运行。

#include

#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) {

// 构造一个空队列QQ.front = Q.rear = new QNode;Q.front->next = NULL;//或Q.rear->next=NULLreturn 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；否则返回ERRORif (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;

}

如有转载请注明来源： www.dreamload.cn/blog/?p=263&preview=true （洋葱先生）

转载地址：https://blog.csdn.net/Kindergarten_Sir/article/details/108587507 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！