【数据结构】树相关例题（C/C++含注释）

一、二叉树的创建及遍历

【问题描述】

​ 给出一个按照先序遍历得出的字符串，’#’ 代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并分别采用“递归”和“非递归”的先序、中序、后序遍历的算法分别输出每一个非空节点。

【输入形式】

​ 输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。

【输出形式】

​ 共有6行，每一行包含一串字符，表示分别按递归和非递归的先序、中序、后序遍历得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。

【样例输入】

ABC##DE#G##F###

【样例输出】

A B C D E G F

C B E G D F A

C G E F D B A

A B C D E G F

C B E G D F A

C G E F D B A

【完整代码】

#include
#include
#include
using namespace std;
//构建二叉树
typedef struct BiNode
{
	char date;
	BiNode* LChild;
	BiNode* RChild;
}*Bitree;
//递归创建树
void CreateBitree(Bitree &bt)
{
	char ch = getchar();
	if (ch == '#') bt = NULL;
	else
	{
		bt = new BiNode;
		bt->date = ch;
		CreateBitree(bt->LChild);
		CreateBitree(bt->RChild);
	}
}
//前序递归遍历
void PreOrder(Bitree root)
{
	if (root != NULL)
	{
		coutLChild);
		cout LChild;
		}
		else if (!s.empty())
		{
			while (!s.empty())
			{
				cur = s.top();
				cout RChild);
		cout RChild != r)
			{
				p = p->RChild;
			}
			else
			{
				s.pop();
				cout