二叉树基本操作的实现

实验项目五：二叉树基本操作的实现

课程名称：数据结构
实验项目名称：二叉树基本操作的实现
实验目的：
1．掌握树的基本操作—遍历。
实验要求：
1、 分别用递归和非递归的方法实现一棵树的三种遍历。
实验过程：
1、 创建一棵二叉树（二叉树如下图所示）；
2、 用递归算法实现对该树的三种遍历；
3、 用非递归算法实现对该树的三种遍历；
4、 输入选项：0或1，0为递归遍历，1为非递归遍历。
5、 根据输入的选项，分别调用递归或非递归算法输出先序、中序、后序遍历序列。
实验报告中给出先序和后序遍历的非递归实现算法代码。
实验结果：
1、输入：ABD##E##CF#G###（创建二叉树）
2、输入：0（递归算法）
3、输出： 先序遍历：ABDECFG
中序遍历：DBEAFGC
后序遍历：DEBGFCA
4、输入：1（非递归实现）
5、输出： 先序遍历：ABDECFG
中序遍历：DBEAFGC
后序遍历：DEBGFCA
实验分析：
1.分析递归与非递归实现的相同点及不同点；
2.列举调试运行过程中出现的错误并分析原因。
要求：
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
(4) 上传源程序到课堂派。顺序表的源程序保存为TraversalBTree.cpp。

这篇博客并没有对算法进行讲解，只有实现代码，算法讲解可以去MOOC上看下西安邮电大学的数据结构课程，根据题目的输入和输出，二叉树的创建必须用前序

贴下代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)
#define e exp(1.0)
#define pa pair<char,ll>
typedef long long ll;
const ll maxn=1e5+7;
ll B;
struct node
{
	char data;
	node *lch;
	node *rch;
};
struct treenode//后序非递归遍历用的着 
{
	node *pos;
	bool vis;//标记节点的左右子树是否已经被访问完了 
};
void Create(node *&root)//前序创建二叉树,注意指针是引用 
{
	char c;
	c=getchar();
	if(c=='\n')
	return ;
	if(c=='#')
	root=NULL;
	else
	{
		root=new node;
		root->data=c;
		Create(root->lch);
		Create(root->rch);
	}
}
void PreOrder(node *now)//前序递归 
{
	if(now!=NULL)
	{
		printf("%c",now->data);
		PreOrder(now->lch);
		PreOrder(now->rch);
	}
	return ;
}
void InOrder(node *now)//中序递归 
{
	if(now!=NULL)
	{
		InOrder(now->lch);
		printf("%c",now->data);
		InOrder(now->rch);
	}
	return ;
}
void PostOrder(node *now)//后序递归 
{
	if(now!=NULL)
	{
		PostOrder(now->lch);
		PostOrder(now->rch);
		printf("%c",now->data);
	}
	return ;
}
void PreStack(node *now)//非递归前序 
{
	stack<node>sta;
	while(now!=NULL||!sta.empty())
	{
		if(now!=NULL)//
		{
			printf("%c",now->data);
			sta.push(*now);
			now=now->lch;
		}
		else//空节点 
		{
			if(!sta.empty())
			{
				now=sta.top().rch;
				sta.pop();
			}
			else//节点为空并且栈也为空，就退出，这个必须有 
			break;
		}
	}
	return ;
}
void InStack(node *now)//中序非递归遍历 
{
	stack<node>sta;
	while(now!=NULL||!sta.empty())
	{
		if(now!=NULL)//非空 
		{
			sta.push(*now);
			now=now->lch;
		}
		else//空节点 
		{
			if(!sta.empty())
			{
				printf("%c",sta.top().data);
				now=sta.top().rch;
				sta.pop();
			}
			else
			break;
		}
	}
	return ;
}
void PostStack(node *now)//后序非递归遍历 
{
	stack<treenode>sta;//此时栈的类型和前序中序不一样了 
	while(now!=NULL||!sta.empty())
	{
		while(now!=NULL)
		{
			treenode tn;
			tn.pos=now;
			tn.vis=0;
			sta.push(tn);
			now=now->lch;
		}
		while(!sta.empty()&&sta.top().vis==1)
		{
			printf("%c",sta.top().pos->data);
			sta.pop();
		}
		if(!sta.empty())
		{
			sta.top().vis=1;
			now=sta.top().pos->rch;
		}
	}
	return ;
}
void Delete(node *root)//清空内存，这个也是必须的 ，后序清空 
{
	if(root!=NULL)
	{
		Delete(root->lch);
		Delete(root->rch);
		delete root;
	}
	return ;
}
int main()
{
// freopen(".../.txt","w",stdout);
// ios::sync_with_stdio(false);
	ll i,j;
	node *root=NULL;
	Create(root);
	scanf("%lld",&B);
	if(!B)//递归遍历 
	{
		 PreOrder(root);//前序遍历 
		 putchar('\n');
		 InOrder(root);//中序遍历 
		 putchar('\n');
		 PostOrder(root);//后序遍历 
		 putchar('\n');
	}	
	else//非递归遍历 
	{
		PreStack(root);
		putchar('\n');
		InStack(root);
		putchar('\n');
		PostStack(root);
		putchar('\n'); 
	}
	Delete(root);
	return 0;
}