您好,欢迎访问本站!登录后台查看权限

转:二叉树层序遍历求深度

笔记 俎天润 2017-04-18 3073 次浏览 2个评论
#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;

}

cjia3.png



已有 3073 位网友参与,快来吐槽:

1#qq  2017-10-12 12:22:38 回复该评论
在这个世界上,
人与人之间无非就是一份缘,
一份情,一份心,一份真。
擦肩而过的叫路人;
不离不弃的叫亲人;
时牵时挂的叫友人;
生死相随的叫近人;
默契能懂的叫爱人。
1#俎天润  2017-10-16 18:57:02 回复该评论
可以可以~

发表评论