#include <iostream>
using namespace std;
//定义树的结构
typedef struct _binTree
{
char data;
_binTree *lNode,*rNode;
}binTree;
//创建二叉树
void createT(binTree *&rootNode,binTree *tempNode)
{
if(rootNode==NULL)
{
rootNode=tempNode; return;
}
else
{
if(rootNode->data > tempNode->data)
{
createT(rootNode->lNode,tempNode);
}
else if(rootNode->data < tempNode->data)
{
createT(rootNode->rNode,tempNode);
}
}
}
//打印已创建的数
void printT(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
printT(rootNode->lNode);
cout<<rootNode->data<<" ";
printT(rootNode->rNode);
}
}
//先序遍历二叉树
void preTraverse(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
cout<<rootNode->data<<" ";
printT(rootNode->lNode);
printT(rootNode->rNode);
}
}
//中序遍历二叉树
void midTraverse(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
printT(rootNode->lNode);
cout<<rootNode->data<<" ";
printT(rootNode->rNode);
}
}
//后序遍历二叉树
void lastTraverse(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
printT(rootNode->lNode);
printT(rootNode->rNode);
cout<<rootNode->data<<" ";
}
}
//计算结点的总个数
int nodeTotal(binTree *rootNode)
{
if(rootNode==NULL)return 0;
else
{
return 1+nodeTotal(rootNode->lNode)+nodeTotal(rootNode->rNode);
}
}
//计算二叉树的深度
int treeDepth(binTree *rootNode)
{
if(rootNode==NULL)return -1;
else
{
int lH=treeDepth(rootNode->lNode);
int rH=treeDepth(rootNode->rNode);
if(lH>rH)return lH+1;
return rH+1;
}
}
//计算叶子结点的个数
int leafTotal(binTree *rootNode)
{
if(rootNode==NULL)return 0;
else
{
if(rootNode->lNode==NULL && rootNode->rNode==NULL)return 1;
else
{
int lH=leafTotal(rootNode->lNode);
int rH=leafTotal(rootNode->rNode);
return rH+lH;
}
}
}
int main()
{
binTree *rootNode,*tNode;
rootNode=NULL; tNode=NULL;
char ch;
cout<<"按照下面给出的顺序进行输入构建二叉树："<<endl<<"F D B E A C J H K G I L"<<endl;
cin>>ch;
while(ch!='0')
{
tNode=new binTree;
tNode->data=ch; tNode->lNode=NULL; tNode->rNode=NULL;
createT(rootNode,tNode);
cin>>ch;
}
if(rootNode==NULL)
{
cout<<"Tree is NULL."<<endl;
}
else
{
cout<<"正常输出二叉树的各节点数据：";
printT(rootNode); cout<<endl;
cout<<"先序遍历二叉树的各节点数据：";
preTraverse(rootNode); cout<<endl;
cout<<"中序遍历二叉树的各节点数据：";
midTraverse(rootNode); cout<<endl;
cout<<"后序遍历二叉树的各节点数据：";
lastTraverse(rootNode); cout<<endl;
cout<<"二叉树的深度为："<<treeDepth(rootNode)<<endl;
cout<<"二叉树的结点的个数为："<<nodeTotal(rootNode)<<endl;
cout<<"二叉树的叶子结点的个数为："<<leafTotal(rootNode)<<endl;
}
return 0;
}
http://hi.baidu.com/mxiaozheng/item/8541b910c162c19899ce33bd