C :

#include "stdio.h"
#include "string.h"


struct node
{
	 char key;
	 int left;
	 int right;
	 int father;
};


struct node tree[100000];
int head,sum;



void xianxu(int n)
{
	if (n==-1) return;
	if (n==0) return;
	if (n>0) printf("%c",tree[n].key);
	if (tree[n].left>=0) xianxu(tree[n].left);
	if (tree[n].right>=0) xianxu(tree[n].right);
}

void zhongxu(int n)
{
	if (n==-1) return;
	if (n==0) return;
	if (tree[n].left>=0) zhongxu(tree[n].left);
	if (n>0) printf("%c",tree[n].key);
	if (tree[n].right>=0) zhongxu(tree[n].right);
}


int insert(int n,char key)
{
	if (n==-1)
	{
		sum++;
	    head=sum;
		tree[head].father=0;
		tree[head].left=-1;
		tree[head].right=-1;
		tree[head].key=key;
		return(1);
	}
	if (tree[n].left==-1) 
	{
		if (key=='^') tree[n].left=0;			
		else
		{
	    	sum++;
			tree[n].left=sum;
	    	tree[sum].father=n;
	    	tree[sum].left=-1;
	    	tree[sum].right=-1;
	    	tree[sum].key=key;
		}
		return(1);
	}
	if ((tree[n].left>0) &&(insert(tree[n].left,key)==1)) return;
	if (tree[n].right==-1) 
	{
		if (key=='^') tree[n].right=0;			
		else
		{
	    	sum++;
			tree[n].right=sum;
	    	tree[sum].father=n;
	    	tree[sum].left=-1;
	    	tree[sum].right=-1;
	    	tree[sum].key=key;
		}
		return(1);
	}
	if ((tree[n].right>0) &&(insert(tree[n].right,key)==1)) return;
}


void main()
{
	int i;
	char str[100];
	gets(str);
	while (1)
	{
    	sum=0;
    	head=-1;
    	for (i=0;i<strlen(str);i++)
    	{
    		insert(head,str[i]);
    	}
    	xianxu(head);
		printf("\n");
    	zhongxu(head);
		printf("\n");
		gets(str);
		if ((str[0]=='^')&&(strlen(str)==1)) break;
	}

}

C++ :

#include <stdio.h> 
#include <malloc.h>
typedef struct BiTNode{
  char data;
  struct BiTNode *lchild,*rchild;
}BitNode, *BiTree;
BiTree CreateBiTree()
{
  char da;
  BiTree T;
  do{
  scanf("%c",&da);
  }while(da<=32);
  if(da == '^')T=NULL;
  else{
   T=(BiTree)malloc(sizeof(BiTNode));
    T->data=da;
    T->lchild=CreateBiTree();
    T->rchild=CreateBiTree();
   }
  return T;
}
void PreOrderTraverse(BiTree T){
  if(T){
       printf("%c",T->data);
       PreOrderTraverse(T->lchild);
       PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){
    if(T){
       InOrderTraverse(T->lchild);
       printf("%c",T->data);
       InOrderTraverse(T->rchild);
 }
}
int main(){
 BiTree btree;
  do{
    btree=CreateBiTree();
    if(btree!=NULL){
    PreOrderTraverse(btree);
 printf("\n");
 InOrderTraverse(btree);
 printf("\n");
    }
  }while(btree!=NULL);
  return 0;
}