实验三：二叉树
学时：2学时
实验目的：掌握树形结构的特点，二叉树的存储方式以及相应操作。

实验内容：
按先序遍历序列建立二叉树的二叉链表，已知先序序列为(F表示空格)：ABCFFDEFGFFFFFF。

并写一个函数treenodes()统计该二叉树的节点个数。

如果有可能，写一个输出函数treeprint()用树形结构打印出该二叉树。

提示：
1，统计结点数也是一种遍历操作，要首先理解遍历，递归程序。

2，由于printf打印是一行行按顺序的，要打印出树形结构，必须按层次遍历，并且利用空格。

关键是控制每一层次打印的空格的数量，以及子树为空的情形。

可参考如下代码：
树的遍历：ch6_traverse.c
/*
树的遍历
author: kk.h
date: 2006.10
*/
#include "stdio.h"
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode;
/* 先根遍历*/
void preorder(BiTNode *bt)
{ if(bt!=NULL)
{ printf("%c ",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
/* 中根遍历*/
void inorder(BiTNode *bt)
{ if(bt!=NULL)
{ inorder(bt->lchild);
printf("%c ",bt->data);
inorder(bt->rchild);
}
}
/* 后根遍历*/
void postorder(BiTNode *bt)
{ if(bt!=NULL)
{ postorder(bt->lchild);
postorder(bt->rchild);
printf("%c ",bt->data);
}
}
/* 非递归算法的中根遍历（后进先出，用了栈的思想）*/ void inorder_fdg(BiTNode *bt)
{ int i=0;
BiTNode *p,*s[20];
p=bt;
do
{ while(p!=NULL)
{ s[i++]=p;
p=p->lchild;
}
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
p=p->rchild;
}
}while(i>0||p!=NULL);
}
/* 用队列实现层次遍历*/
void lev_traverse(BiTNode* T)
{
BiTNode *q[100],*p;
int head,tail, i;
q[0]=T;head=0;tail=1;
while(head<tail) { /* 当队列不空*/
p=q[head++];
printf("%c ",p->data);
if(p->lchild!=NULL)
q[tail++]=p->lchild;
if(p->rchild!=NULL)
q[tail++]=p->rchild;
}
}
/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示*/ BiTNode *crt_bt_pre()
{ char ch;
BiTNode *bt;
scanf("%c",&ch);
if(ch==' ') bt=NULL;
else
{ bt=(BiTNode *)malloc(sizeof(BiTNode));
bt->data=ch;
bt->lchild=crt_bt_pre();
bt->rchild=crt_bt_pre();
}
return(bt);
}
/* 二叉树的释放*/
void freetree(BiTNode *bt)
{ if(bt!=NULL)
{ freetree(bt->lchild);
freetree(bt->rchild);
free(bt);
bt=NULL;
}
}
main()
{
BiTNode *T,*temp[20];
/* 笨方法建立二叉树*/
temp[0]=(BiTNode*)malloc(sizeof(BiTNode));
temp[0]->data = '-';
temp[1]=(BiTNode*)malloc(sizeof(BiTNode));
temp[1]->data = '+';
temp[0]->lchild = temp[1];
temp[2]=(BiTNode*)malloc(sizeof(BiTNode)); temp[2]->data = '/';
temp[0]->rchild = temp[2];
temp[3]=(BiTNode*)malloc(sizeof(BiTNode)); temp[3]->data = 'a';
temp[3]->lchild=NULL; temp[3]->rchild=NULL; temp[1]->lchild = temp[3];
temp[4]=(BiTNode*)malloc(sizeof(BiTNode)); temp[4]->data = '*';
temp[1]->rchild = temp[4];
temp[5]=(BiTNode*)malloc(sizeof(BiTNode)); temp[5]->data = 'e';
temp[5]->lchild=NULL; temp[5]->rchild=NULL; temp[2]->lchild = temp[5];
temp[6]=(BiTNode*)malloc(sizeof(BiTNode)); temp[6]->data = 'f';
temp[6]->lchild=NULL; temp[6]->rchild=NULL; temp[2]->rchild = temp[6];
temp[7]=(BiTNode*)malloc(sizeof(BiTNode)); temp[7]->data = 'b';
temp[7]->lchild=NULL; temp[7]->rchild=NULL; temp[4]->lchild = temp[7];
temp[8]=(BiTNode*)malloc(sizeof(BiTNode)); temp[8]->data = '-';
temp[4]->rchild = temp[8];
temp[9]=(BiTNode*)malloc(sizeof(BiTNode)); temp[9]->data = 'c';
temp[9]->lchild=NULL; temp[9]->rchild=NULL; temp[8]->lchild = temp[9];
temp[10]=(BiTNode*)malloc(sizeof(BiTNode)); temp[10]->data = 'd';
temp[10]->lchild=NULL; temp[10]->rchild=NULL; temp[8]->rchild = temp[10];
T=temp[0];
printf("\n\nPreOrder:\n");
preorder(T);
printf("\n\nInOrder:\n");
inorder(T);
printf("\n\nPostOrder:\n");
postorder(T);
printf("\n\ninorder_fdg:\n");
inorder_fdg(T);
printf("\n\nlev_traverse:\n");
lev_traverse(T);
freetree(T);
/*
printf("\n\nplease input inorder:such as 'abc de g f '\n"); T = crt_bt_pre();
printf("\n\nPreOrder:\n");
preorder(T);
printf("\n\nInOrder:\n");
inorder(T);
freetree(T);
*/
getch();
}。