// test12.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
typedef struct BiThrNode{
char data;
struct BiThrNode *lchild, *rchild;
}BiThrNode, *BiThrTree;
/**
createBiTree(t)
cin>>ch
if(ch=='@')
t=NULL
else
t->data=ch
createBiTree(t->lchild)
createBiTree(t->rchild)
*/
void createBiTree(BiThrTree& t){//先序生成二叉樹
char ch;
cin>>ch;
if(ch=='@') t=NULL;
else {
t=(BiThrNode*)malloc(sizeof(BiThrNode));
t->data=ch;
createBiTree(t->lchild);
createBiTree(t->rchild);
}
}
/**
PreOrderTraverse(t, visit)
if(t)
visit(t->data)
PreOrderTraverse(t->lchild, visit)
PreOrderTraverse(t->rchild, visit)
*/
void PreOrderTraverse(BiThrTree t, void(*visit)(char)){//先序遍歷，打印成廣義表的格式
if(t){
visit(t->data);
if(t->lchild){
cout<<"(";
PreOrderTraverse(t->lchild,visit);
cout<<",";
}
if(t->rchild){
if(!(t->lchild)) cout<<"(,";
PreOrderTraverse(t->rchild,visit);
cout<<")";
}
if(t->lchild && !(t->rchild)) cout<<")";
}
}
/**
InOrderTraverse(t, visit)
if(t)
InOrderTraverse(t->lchild,visit)
visit(t->data)
InOrderTraverse(t->rchild,visit)
*/
void InOrderTraverse(BiThrTree t, void(*visit)(char)){ //中序遍歷，帶括號(hào)
if(t){
if(t->lchild){
cout<<"(";
InOrderTraverse(t->lchild, visit);
cout<<")";
}
visit(t->data);
if(t->rchild){
cout<<"(";
InOrderTraverse(t->rchild,visit);
cout<<")";
}
}
}
void printElement(char d){cout<<d;}
int main()
{
BiThrTree t;
createBiTree(t);
//InOrderTraverse(t, printElement);
PreOrderTraverse(t,printElement);
system("pause");
}