树是一种很常用的数据结构，日后的学习中会经常碰到运用树的知识。
//构造二叉树
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
/*
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
*/
typedef struct node{
int data;
node *l;
node *r;
}*tree;
tree head,t; //head为头指针，同时为根节点，t为当前的节点
void dis(tree &p) //删除二叉树
{
if(p)
{
dis(p->l);
dis(p->r);
delete p;
}
}
void build(tree &p) //先读入根节点，再从左到右
{
int n;
cin>>n;
if(n != -)
{
p = new node;
p -> data = n;
build(p -> l);
build(p -> r);
}
else
p = NULL;
}
void frontvisit(tree p)
{
if(p)
{
cout<< p->data <<" ";
frontvisit(p->l);
frontvisit(p->r);
}
}
void midvisit(tree p)
{
if(p)
{
midvisit(p->l);
cout<<p->data<<" ";
midvisit(p->r);
}
}
void backvisit(tree p)
{
if(p)
{
backvisit(p->l);
backvisit(p->r);
cout<<p->data<<" ";
}
}
void in(tree &p,int n)
{
if(p)
{
if(n < p->data)
in(p->l,n);
if(n > p->data)
in(p->r,n);
}
else
{
p = new node;
p->data = n;
p->l = p->r =NULL;
}
}
int main()
{
int x;
build(t);
cin>>x;
in(t,x);
cout<<"frontvisit"<<endl;
frontvisit(t);
cout<<endl;
cout<<"midvisit"<<endl;
midvisit(t);
cout<<endl;
cout<<"backvisit"<<endl;
backvisit(t);
cout<<endl;
return ;
}
/*
5 3 2 1 -1 -1 -1 -1 6 -1 7 -1 -1
4
*/