您好,欢迎访问本站!登录后台查看权限
  • CuteDNS项目重启,提供去广告DNS服务
  • 本站服务器已加入SETI@home志愿计算
  • 部分文章转自网络,侵权请告知删除

二叉树的基本操作(遍历,求深度,求结点数,求子结点)

笔记 俎天润 2017-05-04 373 次浏览 0个评论
#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;

#define  STACK_INIT_SIZE      80 //初始分配量

#define  STACKINCREMENT   10  //分配增量

typedef struct {//注意与顺序表定义的区别

	ElemType  *base;//栈底指针   

	ElemType  *top;//栈顶指针,指向栈顶的下一个位置 

	int  stacksize;      //当前已分配的存储容量    

}SqStack;

SqStack  S;

int flag = 2;//用于求某结点的子结点

Status InitQueue(LinkQueue &Q) {

	// 构造一个空队列Q

	Q.front = Q.rear = new QNode;

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

	return OK;

}

Status InitStack(SqStack &S) {//构造一个空栈S    

	S.base = (ElemType*)malloc(

		STACK_INIT_SIZE * sizeof(ElemType));

	//S.base = new ElemType[STACK_INIT_SIZE];

	if (!S.base) exit(OVERFLOW); //存储分配失败

	S.top = S.base;   //空栈

	S.stacksize = STACK_INIT_SIZE;

	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 Push(SqStack &S, ElemType e) {//入栈

	if (S.top-S.base == S.stacksize) {//栈满,追加存储空间

		S.base = (ElemType *)realloc(S.base,

			(S.stacksize + STACKINCREMENT) *

			sizeof(ElemType));

		if (!S.base) exit(OVERFLOW); //存储分配失败

		S.top = S.base + S.stacksize; //新栈顶

		S.stacksize += STACKINCREMENT;

	}

	*S.top++ = e;     //e先入栈,再移动指针

	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 Pop(SqStack &S, ElemType &e) {//出栈

									 // 若栈不空,则删除S的栈顶元素,

									 // 用e返回其值,并返回OK;

									 // 否则返回ERROR

	if (S.top == S.base)   exit(UNDERFLOW);

	e = *(S.top=S.top-1);   //先移动指针,再取数据元素

	return OK;

}

Status StackEmpty(SqStack S) {//是否为空栈

	return S.base == S.top;

}

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);

	}

}

// 先序遍历二叉树的递归算法 

void Preorder(BiTree T) {

	if (T) {//非空二叉树

		cout << T->data;

		Preorder(T->lchild); // 递归遍历左子树

		Preorder(T->rchild);// 递归遍历右子树

	}

}

//先序遍历非递归

void preorder(BiTree T) {

	InitStack(S);

	BiTree P = T;

	do {

		while (P) {

			cout << P->data;

			Push(S, P);

			P = P->lchild;

		}

		if (!StackEmpty(S)) {

			Pop(S, P);

			P = P->rchild;

		}

	} while (!StackEmpty(S) || P);

}

// 中序遍历二叉树的递归算法 

void Inorder(BiTree T) {

	if (T) {//非空二叉树

		Inorder(T->lchild); // 递归遍历左子树

		cout << T->data;

		Inorder(T->rchild);// 递归遍历右子树

	}

}

//中序遍历非递归

void inorder(BiTree T) {

	InitStack(S);//初始化栈

	BiTree p = T;//p指向根结点 

	do {

		while (p)//p不是空二叉树

		{

			Push(S, p);//指针p入栈

			p = p->lchild;//沿左分支向下走

		}

		if (!StackEmpty(S)) {//栈不空才能出栈访问结点

			Pop(S, p);//指针出栈

			cout << p->data;//访问p所指向结点

			p = p->rchild; //访问右子树

		}

	} while (!StackEmpty(S) || p);//栈空且p为空时结束

}

// 后序遍历二叉树的递归算法 

void Postorder(BiTree T) {

	if (T) {//非空二叉树

		Postorder(T->lchild); // 递归遍历左子树

		Postorder(T->rchild);// 递归遍历右子树

		cout << T->data;

	}

}

//层序遍历

void LevelTraverse(BiTree T) {

	if (T) {

		LinkQueue Q;

		ElemType p;

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

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

		while (!QueueEmpty(Q)) {

			DeQueue(Q, p);

			cout << p->data;

			if (p->lchild)

				EnQueue(Q, p->lchild);

			if (p->rchild)

				EnQueue(Q, p->rchild);

		}

	}

}

//二叉树中叶子结点的个数

void CountLeaf(BiTree T, int & count) {

	if (T) {

		if ((!T->lchild) && (!T->rchild))

			count++;

		CountLeaf(T->lchild, count);

		CountLeaf(T->rchild, count);

	}

}

//统计结点个数

void CountNode(BiTree T, int &count) {

	if (T) {

		count++;

		CountNode(T->lchild, count);

		CountNode(T->rchild, count);

	}

}

// 后序遍历求二叉树的深度

int PostorderDepth(BiTree T) {

	if (!T)    return  0;

	int a, b;

	a = PostorderDepth(T->lchild);

	b = PostorderDepth(T->rchild);

	return  ((a > b) ? a : b) + 1;

}

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

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;

}

//输出二叉树中某结点(先序遍历+后序遍历)

void Descendents(BiTree T, TElemType e) {

	if (flag == 0) return;

	if (T) {

		if (e == T->data) flag = 1;

		if (flag == 1)

			cout << T->data;//先序

		Descendents(T->lchild, e);

		Descendents(T->rchild, e);

		if (e == T->data)

			flag = 0;//后序

	}

}

// 输出度为2的节点

void CoundNode2(BiTree T, int &count) {

	if (T) {

		if (T->lchild&&T->rchild)count++;

		CoundNode2(T->lchild, count);

		CoundNode2(T->rchild, count);

	}

}

int main() {

	int leafNum = 0, nodeNum = 0, count = 0;

	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 << "先序遍历为(递归法):";

	Preorder(T);

	cout << endl << "先序遍历为(非递归法):";

	preorder(T);

	cout << endl << endl << "中序遍历为(递归法):";

	Inorder(T);

	cout << endl << "中序遍历为(非递归法):";

	inorder(T);

	cout << endl << endl << "后序遍历为(递归法):";

	Postorder(T);

	cout << endl << endl << "层序遍历为(递归法):";

	LevelTraverse(T);

	cout << endl << endl << "二叉树中叶子结点的个数:";

	CountLeaf(T, leafNum);

	cout << leafNum << "个";

	cout << endl << endl << "二叉树中结点的个数:";

	CountNode(T, nodeNum);

	cout << nodeNum << "个";

        cout << endl << endl << "请输入要求度为2的结点的个数:";

	CoundNode2(T, count);

	cout << count << "个";

	cout << endl << endl << "二叉树的深度(后序遍历法):";

	cout << PostorderDepth(T);

	cout << endl << "二叉树的深度(层序遍历法):";

	cout << LevelDepth(T);

	cout << endl << endl << "请输入要求子结点的结点:";

	cin >> e;

	cout << e << "的子结点为(包括自身):";

	Descendents(T, e);

	cout << endl << endl;

	return 0;

}

二叉树的基本操作(遍历,求深度,求结点数,求子结点) 笔记 第1张


修改DNS,屏蔽网页广告,使用本站提供的净网DNS -> 

二叉树的基本操作(遍历,求深度,求结点数,求子结点) 笔记 第2张


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

发表评论