#include<iostream>
//#include<malloc.h> //c malloc和free,C++ new和delete
#include<queue>
using namespace std;
//二叉链表方式，最常用
#define MAXSIZE 100
typedef char ElementType;
struct BTNode{
ElementType data;
BTNode *lchild;
BTNode *rchild;
};
//先序创建二叉树
BTNode * CreateTree(){
BTNode * T=new BTNode;//(BTNode *)malloc(sizeof(BTNode))
char ch;cin>>ch;//输入
if(ch=='#'){
return NULL;
}else{
T->data=ch;
T->lchild=CreateTree();
T->rchild=CreateTree();
}
return T;
}
//利用后序遍历求二叉树的深度，节点个数
int PostTree(BTNode * T){
if(!T) return 0;
int left,right,depth,nodenum;
left=PostTree(T->lchild);
right=PostTree(T->rchild);
depth=( left>right?left:right )+1; //深度=max(left,right)+1
nodenum=left+right+1;//节点个数=left+right+1
return depth; //return nodenum;求节点数
}
//求叶子节点个数
int Leaf(BTNode * T){
if(!T) return 0;
if( !(T->lchild) && !(T->rchild) ){
return 1;
}else
return ( Leaf(T->lchild)+Leaf(T->rchild) );
}
//求二叉树的宽度(同一层上的最大节点数)，利用队列
int MaxNode(BTNode * T){
if(!T) return 0;
int frontLevelWidth,curLevelWidth,maxLevelWidth;//上层的节点总数，本层的节点总数 ,节点数最大值
queue<BTNode *> que;
BTNode * p;
que.push(T);//根节点入队
frontLevelWidth=1; maxLevelWidth=1;//最少有一个根节点
while(!que.empty()){//保证队列不空
while(frontLevelWidth){
p=que.front();
que.pop();
if(p->lchild) que.push(p->lchild);
if(p->rchild) que.push(p->rchild);
frontLevelWidth--;
}
curLevelWidth=que.size();
if(curLevelWidth>maxLevelWidth) maxLevelWidth=curLevelWidth;
frontLevelWidth=curLevelWidth;
}
return maxLevelWidth;
}
int main(){
//freopen("input.txt","r",stdin);//ABD###CE##F##
BTNode * T;
T=CreateTree();
cout<<PostTree(T)<<endl;
cout<<MaxNode(T)<<endl;
return 0;
}
关于先序建树
