二叉树的建立和遍历

题目描述已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,（其中逗号表示空节点）。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。输入输入一个长度小于50个字符的字符串。输出输出共有4行：第1行输出中序遍历序列；第2行输出后序遍历序列；第3行输出叶子节点个数；第4行输出二叉树深度。示例输入abc,,de,g,,f,,,示例输出cbegdfacgefdba35#include <iostream>
using namespace std;
typedef char Elem_Type;
typedef struct BiTNode
{
Elem_Type data;
BiTNode *lchild;
BiTNode *rchild;
}BiTNode;
void CreateBiTree（BiTNode **root）
{
Elem_Type temp;
cin>>temp;
if（temp == ","）
*root = NULL;
else
{
*root = new BiTNode;
（*root）->data = temp;
CreateBiTree（ &（*root）->lchild ）;
CreateBiTree（ &（*root）->rchild ）;
}
}
void InOrderTraverse（BiTNode *root）//中
{
if（ root ）
{
InOrderTraverse（ root->lchild）;
cout<<root->data;
InOrderTraverse（ root->rchild）;
}
}
void PostOrderTraverse（BiTNode *root）
{
if（ root ）
{
PostOrderTraverse（ root->lchild）;
PostOrderTraverse（ root->rchild）;
cout<<root->data;
}
}
int LeafNodes（ BiTNode *root）
{
static int count =0;
if（！root ）
return 0;
if（！root->lchild && ！root->rchild）
count++;
LeafNodes（root->lchild）;
LeafNodes（root->rchild）;
return count;
}
int BiTreeDepth（BiTNode *root）
{
if（！root ）
return 0;
return （BiTreeDepth（root->lchild） > BiTreeDepth（root->rchild）？
BiTreeDepth（root->lchild） : BiTreeDepth（root->rchild）） + 1;
}
int main（void）
{
BiTNode *root = NULL;
CreateBiTree（&root）;
InOrderTraverse（root）;
cout<<endl;
PostOrderTraverse（root）;
cout<<endl;
cout<<LeafNodes（ root）<<endl;
cout<<BiTreeDepth（root）<<endl;
return 0;
}
/**************************************
Problem id : SDUT OJ 2136
User name : 李俊
Result : Accepted
Take Memory : 456K
Take Time : 10MS
Submit Time : 2014-05-05 23:13:18
**************************************/二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-05/101606.htm