PTA 6-4 二叉树创建及遍历 (10 分)

实现二叉树创建及遍历算法。

函数接口定义：
void CreateBiTree(BiTree &T);//根据输入的字符串，创建二叉树。
void PreOrder(BiTree T);//先序遍历二叉树
void InOrder(BiTree T);//中序遍历二叉树
void PostOrder(BiTree T);//后序遍历二叉树
void LevelOrder(BiTree T);//层次遍历二叉树
其中 T 表示二叉树类型。

裁判测试程序样例：

#include
using namespace std;
typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T);//根据输入的字符串，创建二叉树。 
void PreOrder(BiTree T);//先序遍历二叉树 
void InOrder(BiTree T);//中序遍历二叉树 
void PostOrder(BiTree T);//后序遍历二叉树 
void LevelOrder(BiTree T);//层次遍历二叉树  

int main(){
 BiTree T;
 CreateBiTree(T);
 cout<<"PreOrder:"; 
 PreOrder(T);
 cout< 
输入样例：
 
AB#C##D#EF###
 
输出样例：
 
输出拓扑序列。
 PreOrder:ABCDEF
 InOrder:BCADFE
 PostOrder:CBFEDA
 LevelOrder:ABDCEF
 
思路：按照递归的思想，创建函数可用二叉树的前序遍历稍作改变实现。将输出元素改为新建一个节点。其他步骤和前序遍历递归类似。前序后序中序三种函数按照根-左-右，左-右-根，左-根-右来写递归。
 实现层序遍历要借助队列先进先出的思想，可调用c++库函数来辅助操作。
 代码：
 
#include
void CreateBiTree(BiTree &T)//根据输入的字符串，创建二叉树。 
{
    char ch;
    cin>>ch;
    if(ch=='#') T = NULL;
    else{
        T =(BiTree)malloc(sizeof(BiTNode));
        if(!T) return;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void PreOrder(BiTree T)//先序遍历二叉树 
{
    if(T==NULL) return;
    cout<data;
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
void InOrder(BiTree T)//中序遍历二叉树 
{
    if(T==NULL) return;
    InOrder(T->lchild);
    cout<data;
    InOrder(T->rchild);
}
void PostOrder(BiTree T)//后序遍历二叉树 
{
    if(T==NULL) return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    cout<data;
}
void LevelOrder(BiTree T)//层次遍历二叉树
{
  queue q;
  if(T) q.push(T);
  while(!q.empty()){
    BiTree front = q.front();
    cout<data;
    q.pop();
    if(front->lchild){
      q.push(front->lchild);
    }
    if(front->rchild){
      q.push(front->rchild);
    }
  }
}