[问题描述]
建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
[测试数据]
如输入：ABC##DE#G##F###（其中#表示空格字符）则输出结果为：
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层序：ABCDEFG
----------------------------------------------------------------我是分割线--------------------------------------------------------------------------------
【二叉树定义】
二叉树是n(n>=0)个结点所构成的集合，n=0时为空树，n>0为非空树。对于非空树T：
1.有且仅有一个称为 根 的结点；
2.除根节点外其余结点分为两个互不相交的子集T1，T2，分别称为T的左子树，右子树
二叉树与树一样具有递归性质，二叉树每个结点至多两颗子树，子树有左右之分，次序不可颠倒。
【存储结构】
1.顺序存储结构
#define MAXSIZE 100 typedef TElemType SqBiTree[MAXSIZE];//0号单元存储根节点，TElemType可换成自己需要的类型如char SqBiTree bt;2.链式存储结构
typedef struct BiTNode { char data;//结点数据域 BiTNode *lchild, *rchild;//左右孩子指针 }BiTNode,*BiTree;顺序存储结构只适用完全二叉树，一般采用链式。
【先序创建二叉链表】
void CreateBiTree(BiTree&T)//先序遍历的顺序建立二叉表 { char ch; cin >> ch;//输入的字符串会进入缓冲区， if (ch == '#')//ch为字符型，（ch=="#")错误 T = NULL;//递归结束，创建空树 else//递归创建二叉树 { T = new BiTNode;//生成根节点 T->data = ch;//将ch赋值给数据域 CreateBiTree(T->lchild);//递归创建左子树 CreateBiTree(T->rchild);//递归创建右子树 } }【先序遍历】
void PreOrderTraverse(BiTree T)//先序遍历 { if (T)//若二叉树非空 { cout << T->data;//访问根节点 PreOrderTraverse(T->lchild);//先序遍历左子树 PreOrderTraverse(T->rchild);//先序遍历右子树 } }先中后序类似，先序是根左右，中序左根右，后序左右根，只要改变访问根节点顺序就行，具体代码在下面。
【层序遍历】
void SeqOrderTraverse(BiTree T)//层序遍历 { SqQueue q; InitQueue(q); EnQueue(q, T); while (q.rear!=q.front) { BiTree root = OutQueue(q); cout << root->data << " "; if (root->lchild) EnQueue(q, root->lchild); if (root->rchild) EnQueue(q, root->rchild); } cout << endl; }
层序遍历顺序：ABCDEFG
每个结点遍历都是 根-左-右 的顺序，
A入队后出队，出队时其左右孩子入队，判断左右孩子是否为空，如果非空，则入队。其他结点类似。
（可以参考https://blog.csdn.net/qq_29542611/article/details/79372678）
-------------------------------------------------------------------我是分割线----------------------------------------------------------------------------------
【代码】
#include<iostream> #define MAXSIZE 100 using namespace std; typedef struct BiTNode { char data; BiTNode *lchild, *rchild; }BiTNode,*BiTree; typedef struct SqQueue { BiTree*base;//存储空间的基地址 int front; int rear; }; void InitQueue(SqQueue&q)//构造空队列 { q.base = new BiTree[MAXSIZE]; if (!q.base) exit(OVERFLOW); q.front = q.rear = 0; } void EnQueue(SqQueue&q,BiTree&T)//入队 { q.base[q.rear] = T; q.rear++; } BiTree OutQueue(SqQueue&q) { BiTree T; T = q.base[q.front]; q.front++; return T; } void CreateBiTree(BiTree&T)//先序遍历的顺序建立二叉表 { char ch; cin >> ch;//输入的字符串会进入缓冲区， if (ch == '#')//ch为字符型，（ch=="#")错误 T = NULL;//递归结束，创建空树 else//递归创建二叉树 { T = new BiTNode;//生成根节点 T->data = ch;//将ch赋值给数据域 CreateBiTree(T->lchild);//递归创建左子树 CreateBiTree(T->rchild);//递归创建右子树 } } void PreOrderTraverse(BiTree T)//先序遍历 { if (T)//若二叉树非空 { cout << T->data << " ";//访问根节点 PreOrderTraverse(T->lchild);//先序遍历左子树 PreOrderTraverse(T->rchild);//先序遍历右子树 } } void InOrderTraverse(BiTree T)//中序遍历 { if (T) { InOrderTraverse(T->lchild); cout << T->data << " "; InOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T)//后序遍历 { if (T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout << T->data << " "; } } void SeqOrderTraverse(BiTree T)//层序遍历 { SqQueue q; InitQueue(q); EnQueue(q, T); while (q.rear!=q.front) { BiTree root = OutQueue(q); cout << root->data << " "; if (root->lchild) EnQueue(q, root->lchild); if (root->rchild) EnQueue(q, root->rchild); } cout << endl; } int main() { BiTree T; cout << "请输入字符串，#表空树" << endl; CreateBiTree(T); cout << "先序输出："; PreOrderTraverse(T); cout << endl; cout << "中序输出："; InOrderTraverse(T); cout << endl; cout << "后序输出：" ; PostOrderTraverse(T); cout << endl; cout << "层序输出："; SeqOrderTraverse(T); return 0; }【运行结果】
