输入
二叉树的先序遍历序列，用#代表空树或空子树。
输出
共五行
前三行依次输出先序、中序和后序遍历序列，
第四行输出二叉树的高度，
第五行依次输出二叉树总结点数目、叶子结点数目、度为1的结点数目。
样例输入
A B # D # # C E # # F # #
样例输出
PreOrder: A B D C E F
InOrder: B D A E C F
PostOrder: D B E F C A
3
6 3 1
题目很简单，基本的二叉树操作。需要注意的是输入结点之间有空格，而且输出结点时也有空格，行末不能有空格。
#include <cstdio>
typedef char TElemType;
typedef struct node {
TElemType data;
struct node *left_child;
struct node *right_child;
} BTNode, *BinTree;
int node_count = ;
int leaf_count = ;
int one_count = ;
void Create( BTNode*& t) {
char c;
char ch;
scanf( "%c", &c );
ch = getchar();
if( c =='#' )
t = NULL;
else {
t = new BTNode;
t->data = c;
Create( t->left_child );
Create( t->right_child );
}
}
void PreOrder( BTNode* t ) {
if( t != NULL ) {
printf( " %c", t->data );
PreOrder( t->left_child );
PreOrder( t->right_child );
}
}
void InOrder( BTNode *t ) {
if( t != NULL ) {
InOrder( t->left_child );
printf( " %c", t->data );
InOrder( t->right_child );
}
}
void PostOrder( BTNode *t ) {
if( t != NULL ) {
PostOrder( t->left_child );
PostOrder( t->right_child );
printf( " %c", t->data );
}
}
int Height( BTNode *t ) {
int i, j;
if( t == NULL ) return ;
else {
i = Height( t->left_child );
j = Height( t->right_child );
}
return ( i > j ) ? ( i + ) : ( j + );
}
void BTNode_Count( BTNode *t ) {
if( t == NULL ) return ;
else {
BTNode_Count( t->left_child );
BTNode_Count( t->right_child );
node_count++;
}
}
void BTNode_LeafCount( BTNode *t ) {
if( t == NULL ) return ;
else {
if( t->left_child == NULL && t->right_child == NULL ) {
leaf_count++;
}
else if( t->left_child == NULL && t->right_child != NULL || t->left_child != NULL && t->right_child == NULL ){
one_count++;
}
BTNode_LeafCount( t->left_child );
BTNode_LeafCount( t->right_child );
}
}
int main() {
BTNode T;
BinTree root = &T;
Create( root );
printf( "PreOrder:" );
PreOrder( root );
printf( "\n" );
printf( "InOrder:" );
InOrder( root );
printf( "\n" );
printf( "PostOrder:" );
PostOrder( root );
int height = Height( root );
BTNode_Count( root );
BTNode_LeafCount( root );
printf( "\n%d\n%d %d %d", height, node_count, leaf_count, one_count );
return ;
}