对于二叉树通常约定以前序遍历方式输入，若输入不正确是不会有什么显示的，这点要注意
假设二叉树为
1
2 4
3 5
扩展后的二叉树
1
2 4
-1 3 -1 5
-1 -1 -1 -1代码内注释要要注意：按前序方式输入数据
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef struct Node{
struct Node *l_c,*r_c;
int data;
}*BitTree,NodeTree;
void CreateTree(BitTree &T){//注意这里是&T要清楚指针的逻辑关系*T &T *（*T）
int x;
cin>>x;
if(-1==x)
T=NULL;
else{
T= new NodeTree;
CreateTree(T->l_c);
T->data=x;
CreateTree(T->r_c);
}
}
//树的深度
int Depth(BitTree T){
if(NULL==T)
return 0;
int l_d=Depth(T->l_c);
int r_d=Depth(T->r_c);
return 1+max(l_d,r_d);
}
//层次遍历输出
void Level_print(BitTree T,int x){
if(T==NULL||x<1)
return;
if(x==1){
cout<<T->data<<" ";
return;
}
Level_print(T->l_c,x-1);
Level_print(T->r_c,x-1);
}
//层次遍历
void Level_traversal(BitTree T){
if(T==NULL)
return;
int h=Depth(T);
for(int i=1;i<=h;i++){
Level_print(T,i);
cout << endl;
}
}
//前序遍历
void pre_traversal(BitTree T){
if(T){
cout<<T->data<<" ";
pre_traversal(T->l_c);
pre_traversal(T->r_c);
}
}
//中序遍历
void mid_traversal(BitTree T){
if(T){
mid_traversal(T->l_c);
cout<<T->data<<" ";
mid_traversal(T->r_c);
}
}
//后序遍历
void after_traversal(BitTree T){
if(T){
after_traversal(T->l_c);
after_traversal(T->r_c);
cout<<T->data<<" ";
}
}
//主函数
int main(){
BitTree T;
cout<<"/** 输入说明 **/"<<endl;
cout<<"/** 按前序遍历方式输入数据 **/"<<endl;
cout<<"/** 首先要对二叉树进行扩展 **/"<<endl;
cout<<"/** 叶子结点下边要补俩-1 -1 **/"<<endl;
cout<<"/** 当每个叶子结点都是-1时数据就输入完了 **/"<<endl;
cout<<"/** 例如:1 2 -1 3 -1 -1 4 -1 5 -1 -1回车 **/"<<endl;
cout<<endl;
cout<<"请输入数据："<<endl;
CreateTree(T);
cout<<"树的高度"<<endl;
cout<<Depth(T)<<endl;
cout<<"层次遍历"<<endl;
Level_traversal(T);
cout<<endl;
cout<<"前序遍历"<<endl;
pre_traversal(T);
cout<<endl;
cout<<"中序遍历"<<endl;
mid_traversal(T);
cout<<endl;
cout<<"后序遍历"<<endl;
after_traversal(T);
cout<<endl;
return 0;
}