#include<iostream>
using namespace std;
typedef int elemtype;
typedef struct binode
{
elemtype data;
struct binode *lchild,*rchlid;
}binode,*pbinode;
class bitree
{
//所有的函数功能默认为先序遍历和建立
pbinode elem;
int count;//结点个数
void create(pbinode &elem);//递归调用建立二叉树
void bianli(pbinode elem);//递归遍历
void createtree();//层序建表
int depth(pbinode);//递归求二叉树的深度
public:
bitree();
bitree(int);//非递归调用建立二叉树
void traverse();//二叉树遍历函数
void traverse(int);//非递归遍历二叉树
void traversetree();//层序遍历
void traversetree(int);//分层显示的层序遍历
int bitree_depth();//二叉树的深度
int bitree_width();//二叉树的宽度
void depths();
void yezi_shuliang();//叶子结点的个数
void jiediangeshu();//结点个数
//中序遍历
};
bitree::bitree()
{
create(elem);
//createtree();
}
void bitree::create(pbinode &elem)
{
//先序建立
int a;
cin>>a;
if(a==0)elem=NULL;
else
{elem=new binode;
elem->data=a;
create(elem->lchild);
create(elem->rchlid);
}
}
bitree::bitree(int a)
{
pbinode s[30];
int top=-1;
pbinode p,r;
elemtype e;
cin>>e;
if(e==0)elem=NULL;
else {elem=new binode;
elem->data=e;
elem->lchild=NULL;
elem->rchlid=NULL;
p=elem;
top++;
s[top]=p;
cin>>e;
do
{
while(e)
{
pbinode q=new binode;
q->data=e;
q->lchild=NULL;
q->rchlid=NULL;
top++;
s[top]=q;
if(p){p->lchild=q;p=q;}
else {r->rchlid=q;p=q;}
cin>>e;
}
r=p=s[top];
top--;
p=p->rchlid;
cin>>e;}while(top!=-1||e);}
}
void bitree::bianli(pbinode elem)
{
if(elem)
{
cout<<elem->data<<" ";
bianli(elem->lchild);
bianli(elem->rchlid);
}
}
void bitree::traverse()
{
bianli(elem);
}
void bitree::traverse(int a)
{
pbinode s[20];
pbinode p=elem;
int top=-1;
do
{
while(p)
{cout<<p->data<<" ";
top++;
s[top]=p;
p=p->lchild;
}
p=s[top];
top--;
p=p->rchlid;
}while(top!=-1||p);
}
void bitree::createtree()
{
pbinode s[20];
elemtype e;
int i;
cout<<"输入值和序号"<<endl;
cin>>e>>i;
if(e==0||i==0)elem=NULL;
else while(e!=0&&i!=0)
{
pbinode p=new binode;
p->data=e;
p->lchild=NULL;
p->rchlid=NULL;
s[i]=p;
if(i==1)elem=p;
else
{int j=i/2;
if(i%2==0)s[j]->lchild=p;
else s[j]->rchlid=p;}
cin>>e>>i;
}
}
void bitree::traversetree()
{
pbinode b[30];
pbinode p=elem;
int front,rear;
front=rear=0;
if(p)
{rear++;b[rear]=p;}
while(front!=rear)
{
//出队
front++;
p=b[front];
cout<<p->data;
//入队
if(p->lchild){rear++;b[rear]=p->lchild;}
if(p->rchlid){rear++;b[rear]=p->rchlid;}
}
}
void bitree::traversetree(int a)
{
pbinode b[30];
pbinode p=elem;
int front,rear,m;
front=rear=0;
if(p)
{rear++;b[rear]=p;m=1;}
while(front!=rear)
{
//出队
int c=0;
for(int i=0;i<m;i++)
{front++;
p=b[front];
cout<<p->data;
//入队
if(p->lchild){rear++;b[rear]=p->lchild;c++;}
if(p->rchlid){rear++;b[rear]=p->rchlid;c++;}
}
m=c;
cout<<endl;
}
}
int bitree::bitree_depth()
{
pbinode b[30];
pbinode p=elem;
int front,rear,m,j=0;
front=rear=0;
if(p)
{rear++;b[rear]=p;m=1;}
while(front!=rear)
{
int c=0;
for(int i=0;i<m;i++)
{
//出队
front++;
p=b[front];
//入队
if(p->lchild){rear++;b[rear]=p->lchild;c++;}
if(p->rchlid){rear++;b[rear]=p->rchlid;c++;}
}
m=c;
j++;
}
return j;
}
int bitree::bitree_width()
{
pbinode b[30];
pbinode p=elem;
int front,rear,m,d;
front=rear=0;
if(p)
{rear++;b[rear]=p;d=m=1;}
while(front!=rear)
{
int c=0;
for(int i=0;i<m;i++)
{
//出队
front++;
p=b[front];
//入队
if(p->lchild){rear++;b[rear]=p->lchild;c++;}
if(p->rchlid){rear++;b[rear]=p->rchlid;c++;}
}
m=c;
if(m>d)d=m;
}
return d;
}
int bitree::depth(pbinode t)
{
int hl,hr;
if(!t)return 0;
else
{
hl=depth(t->lchild);
hr=depth(t->rchlid);
if(hl>hr)return hl+1;
else return hr+1;
}
}
void bitree::depths()
{
int i=depth(elem);
cout<<i;
}
void bitree::yezi_shuliang()
{
pbinode s[20];
int rear=0;
int front=0;
int count=0;
pbinode p=elem;
if(p){s[rear]=p;rear++;}
while(front!=rear)
{
//出队
p=s[front];
front++;
if(!p->lchild&&!p->rchlid)count++;
//入队
if(p->lchild){s[rear]=p->lchild;rear++;}
if(p->rchlid){s[rear]=p->rchlid;rear++;}
}
cout<<"叶子接点个数为："<<count<<endl;
}
void bitree::jiediangeshu()
{
pbinode s[20];
int rear=0;
int front=0;
int count=0;
pbinode p=elem;
if(p){s[rear]=p;rear++;}
while(front!=rear)
{
//出队
p=s[front];
front++;
count++;
//入队
if(p->lchild){s[rear]=p->lchild;rear++;}
if(p->rchlid){s[rear]=p->rchlid;rear++;}
}
cout<<"结点个数为："<<count<<endl;
}
自己写的 ，还没有整理好，你先看看，有不清楚的再说。
