二叉树的链式存储结构创建与遍历

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
 int data; // 存放数据域
 struct Tree *lchild; // 遍历左子树指针
 struct Tree *rchild; // 遍历右子树指针
}Tree,*BitTree;
BitTree CreateLink()
{
 int data;
 int temp;
 BitTree T;
 scanf("%d",&data); // 输入数据
 temp=getchar(); // 吸收空格
 if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建
 return NULL;
 }else{
 T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间
 T->data = data;  // 把当前输入的数据存入当前节点指针的数据域中
 printf("请输入%d的左子树: ",data); 
 T->lchild = CreateLink();  // 开始递归创建左子树
 printf("请输入%d的右子树: ",data); 
 T->rchild = CreateLink();  // 开始到上一级节点的右边递归创建左右子树
 return T;  // 返回根节点
 } 
}
// 先序遍历
void ShowXianXu(BitTree T) // 先序遍历二叉树
{
 if(T==NULL) // 递归中遇到NULL，返回上一层节点
 {
 return;
 }
 printf("%d ",T->data);
 ShowXianXu(T->lchild); // 递归遍历左子树
 ShowXianXu(T->rchild); // 递归遍历右子树
}
// 中序遍历
void ShowZhongXu(BitTree T) // 先序遍历二叉树
{
 if(T==NULL) // 递归中遇到NULL，返回上一层节点
 {
 return;
 }
 ShowZhongXu(T->lchild); // 递归遍历左子树
 printf("%d ",T->data);
 ShowZhongXu(T->rchild); // 递归遍历右子树
}
// 后序遍历
void ShowHouXu(BitTree T) // 后序遍历二叉树
{
 if(T==NULL) // 递归中遇到NULL，返回上一层节点
 {
 return;
 }
 ShowHouXu(T->lchild); // 递归遍历左子树
 ShowHouXu(T->rchild); // 递归遍历右子树
 printf("%d ",T->data);
}
int PostTreeHeight(BitTree T){
 //通过后序遍历实现求树的高度
 int h = 0, hl = 0, hr = 0;
 if (T==NULL){
 return 1;
 }else{
 hl = PostTreeHeight(T->lchild);//递归遍历左子树
 hr = PostTreeHeight(T->rchild);//递归遍历右子树
 h = (hr > hl)?hr:hl + 1;//三目运算符，很简单
 //如果hr大于hl，那么就取hr的值，然后hr+1赋值给h
 //如果hr不大于h1，那么就取hl得值，然后hl+1赋值给h
 return h;
 }
}
int main()
{
 BitTree S;
 printf("请输入第一个节点的数据:\n");
 S = CreateLink(); // 接受创建二叉树完成的根节点
 int a;
 printf("1.先序\n");
 printf("2.中序\n");
 printf("3.后序\n");
 printf("4.树高\n");
 for(;;){
 scanf("%d",&a);
 if(a==1){
 printf("\n先遍历结果: \n");
 ShowXianXu(S);  // 先序遍历二叉树
 printf("\n");
 }else if(a==2){
 printf("\n中序遍历结果: \n");
 ShowZhongXu(S);  // 中序遍历二叉树
 printf("\n");
 }else if(a==3){
 printf("\n后序遍历结果: \n");
 ShowHouXu(S); // 后序遍历二叉树
 printf("\n");
 }else if(a==4){
 printf("树高：%d\n",PostTreeHeight(S));
 printf("\n");
 }
 } 
 return 0; 
}  

// 中序遍历
void ShowZhongXu(BitTree T) // 先序遍历二叉树
{
 if(T==NULL) // 递归中遇到NULL，返回上一层节点
 {
 return;
 }
 ShowZhongXu(T->lchild); // 递归遍历左子树
 printf("%d ",T->data);
 ShowZhongXu(T->rchild); // 递归遍历右子树
}