{
int data
struct node *pleft
struct node *pright
}
如上,树是由很多个这样的节点构成的,每个节点两个指针,指向下面的左右子树
根节点,下左右2个子节点,然后下面2个子节点之下又是各自的两个子节点,这样就把树构建起来了,
当然并不是一定有2个子节点
#include<iostream>using namespace std
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#define maxsize 20//最大结点个数
//#define N 14 //必须输入结点个数(包含虚结点)
#define M 10 //最大深度
typedef struct node{
char data
int m//结点的深度
struct node*lchild,*rchild
}Bitree
Bitree*Q[maxsize]
Bitree*creatree()
{
char ch
int front,rear
// int i=1
Bitree *T,*s
T=NULL
front=1
rear=0
cout<<"请输入数据"<<endl
cin>>ch
while(ch!='#')
{
// cin>>ch
s=NULL
if(ch!='@')
{
s=(Bitree*)malloc(sizeof(Bitree))
s->data =ch
s->lchild =s->rchild =NULL
}
rear++
Q[rear]=s
if(rear==1)
{
T=s
T->m=1 //父结点深度为一
}
else{
if(s!=NULL&&Q[front]!=NULL)
if(rear%2==0)
{
Q[front]->lchild =s
Q[front]->lchild ->m =Q[front]->m+1
}
else
{
Q[front]->rchild =s
Q[front]->rchild ->m =Q[front]->m+1
}
if(rear%2==1)
front++
}
//i++
cin>>ch
}
return T
}
int countleaf(Bitree* T)
{
if(T==NULL)
return (0)
else if((T->lchild==NULL)&&(T->rchild==NULL))
return (1)
else
return (countleaf(T->lchild)+countleaf(T->rchild))
}
int treedepth(Bitree *T)
{
if(T==NULL)
return (0)
else
{
if(treedepth(T->lchild )>treedepth(T->rchild ))
return(treedepth(T->lchild )+1)
else
return (treedepth(T->rchild )+1)
}
}
void output(Bitree*T) //输出打印二叉数
{
int i
if(T!=NULL)
{
output(T->rchild ) //右根左遍历二叉数,结果从上到下显示
for(i=1i<=Mi++)
{
if(i!=T->m)
cout<<" "
else
cout<<T->data
}
cout<<endl
//cout<<T->data
output(T->lchild )
}
}
int menu_select( )
{
int sn
printf(" 打印二叉树问题\n")
printf("==================\n")
printf(" 1 二叉树的建立\n")
printf(" 2 打印二叉树\n")
printf(" 3 求二叉树叶子结点个数\n")
printf(" 4 求二叉树的深度\n")
printf(" 0 退出系统\n")
printf("==================\n")
printf(" 请 选 择0-4:\n")
for( )
{
scanf( "%d", &sn)
if( sn <0||sn>4)
printf("\n\t输入错误,重选0-4:\n")
else
break
}
return sn
}
int main( )
{
Bitree*T
for()
{
switch(menu_select())
{
case 1: T=creatree()
printf("\n")
break
case 2: cout<<"打印结果:"<<endl
output(T)
printf("\n")
break
case 3: int i
i=countleaf(T)
cout<<"所求二叉树叶子结点为"<<i
cout<<endl
break
case 4: int j
j=treedepth(T)
cout<<"所求二叉树深度为"<<j
cout<<endl
break
case 0:printf("再见")
exit(0)
break
}
}
return 0
}
/*void main()
{
Bitree*T
T=creatree()
cout<<"打印结果:"<<endl
output(T)
}*/