二叉树的遍历及各种操作

62 阅读 0 评论 41 点赞

我是靠谱客的博主爱笑小蚂蚁，最近开发中收集的这篇文章主要介绍二叉树的遍历及各种操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树是数据结构中极为重要的一章，同时难度也不小，笔者也学了好几遍才彻底明白。贯穿二叉树始终都是递归的思想，如果递归的基础没有打牢，可能学起来会有些吃力。三种遍历方式（先序，中序，后序）是需要着重掌握的地方，检验自己是否真正弄懂，可以用模拟栈来实现三种遍历方式。由于上文所提的栈，以及本章所含的二叉树层次遍历，用到了栈和队列，所以本节代码中用到了c++的STL模板。当然不知道的也没有关系，之前笔者也发过这两种数据结构的手写实现，大家调用即可。

#include<iostream>
using namespace std;
#include"stdio.h"
#include"stdlib.h"  //该文件中包含malloc和free()
#include<stack>
#include<queue>
#define MAXTSIZE 100
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char TElemType;

//二叉树的顺序存储结构（容易浪费内存)
typedef TElemType SqBiTree[MAXTSIZE];  //建一棵树 SqBiTree T;

//二叉树的链式存储结构(二叉链表)
typedef struct BiNode
{
	TElemType data;
	struct BiNode *lchild, *rchild;  //左右孩子指针
}BiNode,*BiTree;

//三叉链表(增加一个指向双亲的指针)
typedef struct TriNode
{
	TElemType data;
	struct TriNode *lchild, *rchild, *parent;
}TriNode,*TriTree;

//访问函数
void visit(BiTree T)
{
	//可以是打印结点或者其他操作
}

//二叉树的前序遍历
Status PreOrderTraverse(BiTree T)
{
	if (T == NULL) return OK;
	else
	{
		visit(T);  //访问根结点
		PreOrderTraverse(T->lchild);  //先遍历左子树
		PreOrderTraverse(T->rchild);   //再遍历右子树
	}
}   //中序遍历和后序遍历只需要改变上面三个函数位置即可，此处不在赘述
    //如果去除访问函数，其实可以发现三种遍历方法的路径是一样的，只是访问的时机不一样


//中序遍历非递归算法(模拟栈实现) 
stack<BiTree>stk;
Status InOrderTraverse(BiTree T)
{
	BiNode * p = T;
	BiNode *q=(BiNode *)malloc(sizeof(BiNode));
	while (p||!stk.empty())
	{
		if (p)
		{
			stk.push(p);
			p->lchild;
		}
		else
		{
			q=stk.top();
			stk.pop();
			printf("%c", q->data);
			p = q->rchild;
		}
	}
	return OK;
}


//二叉树层次遍历算法（树上的BFS算法）
queue<BiTree>Q;
void LevelOrder(BiNode *b)
{
	BiNode *p;
	Q.push(b);
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();   //出队结点p
		printf("%c", Q.front()->data);  //访问结点p
		if (p->lchild != NULL) Q.push(p->lchild);//左子树不空，将左子树加入队列
		if (p->rchild != NULL) Q.push(p->rchild);//右子树不空，将右子树加入队列
	}
}

//二叉树的先序建立
//由于给出一串序列可以按照一种遍历方式，建立出多种树,所以用#来表示空结点，来保证树的唯一性
Status CreateBiTree(BiTree &T)
{
	char ch;
	scanf("%c", &ch);
	if (ch == '#') T = NULL;
	else
	{
		if(!(T=(BiNode*)malloc(sizeof(BiNode))));
		{
			exit(OVERFLOW);
		}
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

//复制二叉树（与建立二叉树类似）
int Copy(BiTree T,BiTree &NewT)
{
	if (T == NULL)  //空子树，直接返回
	{
		NewT = T;
		return 0;
	}
	else
	{
		NewT = (BiNode *)malloc(sizeof(BiNode));
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
}

//计算二叉树的深度
int m, n; //m表示左子树的最大深度，n表示右子树的最大深度
int Depth(BiTree T)
{
	if (T == NULL) return 0;
	else
	{
		m = Depth(T->lchild);
		n = Depth(T->rchild);
		if (m > n) return m + 1;
		else return n + 1;
	}
}

//计算结点总个数
int NodeCount(BiTree T)
{
	if (T == NULL) return 0;  //如果是空树返回0
	else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

//计算二叉树叶子结点的总数
int LeafCount(BiTree T)
{
	if (T == NULL) return 0;
	if (T->lchild == NULL && T->rchild == NULL) return 1;  //如果是叶子结点返回1
	else
	{
		return LeafCount(T->lchild) + LeafCount(T->rchild);
	}
}

//线索二叉树 （根据二叉树遍历方式有不同的表示方式）
//利用空余的空指针，左空指针指向前驱，右空指针指向后继，会多余出来两个空指针
//于是在树之前加一个头结点，多余出来的两个空指针指向头结点
//头结点的左孩子域指向树的根结点，右孩子域指向最后一个结点
//元素数据类型定义
typedef struct BiThrNode
{
	int data;
	int ltag, rtag;  //ltag可以为0或1，如果为0表示左指针域指向前驱，如果为1表示其指向自己的左孩子结点，rtag同理
	struct BiThrNode *lchild, *rchild;
}BiThrNode,*BiThrTree;

int main()
{
	return 0;
}