（C语言）二叉树层序遍历求深度

（C语言）二叉树层序遍历求深度

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

#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 = ar->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) {//是否为空队

ar == 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;//根的层序1EnQueue(Q, T);//根指针入队while (!QueueEmpty(Q)) {DeQueue(Q, p);h = p->level;if (p->lchild) {p->lchild->level = h + 1;//左孩子层次加1EnQueue(Q, p->lchild);}if (p->rchild) {p->rchild->level = h + 1;//右孩子层次加1EnQueue(Q, p->rchild);}}}return h;

}

int main() {

TElemType e;cout << "tttt*ttttt*";cout << endl << "tttt*t计科1512-02210151232-杨少通t*" << endl;cout << "tttt*****************************************" << endl << endl;cout << "首先创建二叉树（若结点不存在请输入“#”）。" << endl << endl;//创建二叉树cout << "请输入根结点：";CreateBiTree(T);cout << endl << "二叉树的深度（层序遍历法）：";cout << LevelDepth(T);cout << endl;return 0;

}

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