#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; }
已有 3073 位网友参与,快来吐槽:
人与人之间无非就是一份缘,
一份情,一份心,一份真。
擦肩而过的叫路人;
不离不弃的叫亲人;
时牵时挂的叫友人;
生死相随的叫近人;
默契能懂的叫爱人。
发表评论