递归法创建二叉树，并在该树上实现先序、中序、后序遍历

typedef struct BTNode *Position;
typedef struct BTNode
{
    int data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;//结构体的创建

 1 void CreateBTree(Position &bt)//递归法创建二叉树，为先序顺序创建
 2 {
 3     int data;
 4     cin>>data;//输入需要加入的数字
 5     bt=new BTNode;//创建一个结点
 6     if(data!=-1)//当输入数字为-1时，表示为空结点
 7     {
 8         
 9         bt->data=data;//令输入数字为该结点
10         bt->lchild=NULL;
11         bt->rchild=NULL; //令指向的左右孩子为空结点
12         CreateBTree(bt->lchild);
13         CreateBTree(bt->rchild);//递归创建左右孩子，先左后右
14     }
15     else 
16     {
17         bt=NULL;
18         return;//停止该结点以下结点的创建
19     }
20 }

 1 void PreOrder(BTNode *bt)//先序遍历
 2 {
 3     if(bt!=NULL)
 4     {
 5         cout<<bt->data<<‘ ‘;
 6         PreOrder(bt->lchild);
 7         PreOrder(bt->rchild);
 8     }
 9 }
10 void InOrder(BTNode *bt)//中序遍历
11 {
12     if(bt!=NULL)
13     {
14         InOrder(bt->lchild);
15         cout<<bt->data<<‘ ‘;
16         InOrder(bt->rchild);
17     }
18 }
19 void PostOrder(BTNode *bt)//后序遍历
20 {
21     if(bt!=NULL)
22     {
23         PostOrder(bt->lchild);
24         PostOrder(bt->rchild);
25         cout<<bt->data<<‘ ‘;
26     }
27 }

 1 int main()
 2 {
 3     Position tree;
 4     CreateBTree(tree);//创建二叉树
 5     cout<<"先序遍历顺序为："<<endl;
 6     PreOrder(tree);//先序遍历
 7     cout<<endl; 
 8     cout<<"中序遍历顺序为："<<endl;
 9     InOrder(tree);//中序遍历
10     cout<<endl;
11     cout<<"后序遍历顺序为："<<endl;
12     PostOrder(tree);//后序遍历
13     return 0;
14 }