源程序：
//
// main.cpp
// bitree_c
//
// Created by duanqibo on 2019/7/12.
// Copyright © 2019年 duanqibo. All rights reserved.
//
#include <iostream>
#include <stack>
using namespace std;
typedef struct bitreenode
{
char data;
struct bitreenode *lchild,*rchild;
}*Bitree;
//创建二叉树
void createbitree(Bitree &T)
{
char data;
data=getchar();
if(data=='#')
{
T=NULL;
}
else
{
T=new bitreenode;
T->data=data;
createbitree(T->lchild);
createbitree(T->rchild);
}
};
//递归的先序遍历二叉树
void preordertraverse(Bitree T)
{
if(T)
{
cout<<T->data<<" ";//输出根结点
preordertraverse(T->lchild);
preordertraverse(T->rchild);
}
}
//递归的中序遍历二叉树
void inordertraverse(Bitree T)
{
if(T)
{
inordertraverse(T->lchild);
cout<<T->data<<" ";//输出根结点
inordertraverse(T->rchild);
}
}
//递归的后序遍历二叉树
void postordertraverse(Bitree T)
{
if(T)
{
postordertraverse(T->lchild);
postordertraverse(T->rchild);
cout<<T->data<<" ";//输出根结点
}
}
//求二叉树的深度
int depthofbitree(Bitree T)
{
int ldepth;
int rdepth;
if(T==NULL) //空树
{
return 0;
}
ldepth=depthofbitree(T->lchild);
rdepth=depthofbitree(T->rchild);
if(ldepth>rdepth)
return ldepth+1;
else
return rdepth+1;
}
//求二叉树的叶子结点
int leafcount(Bitree T)
{
if(T==NULL)
{
return 0;
}
else if(T->lchild==NULL && T->rchild==NULL)
{
return 1;
}
else
{
int n=leafcount(T->lchild);//求左子树叶子的数目
int m=leafcount(T->rchild);//求右子树叶子的数目
return n+m;
}
}
//求二叉树T中度为1的结点的数量
int onesoncount(Bitree T)
{
if(T==NULL)
{
return 0;
}
else if((T->lchild==NULL && T->rchild!=NULL) ||
(T->lchild!=NULL && T->rchild==NULL))
{
cout<<"度为1的结点的字母为："<<T->data<<endl;
return (onesoncount(T->lchild) +onesoncount(T->rchild) +1);
}
else
{
return (onesoncount(T->lchild) +onesoncount(T->rchild));
}
}
//求非叶子结点的数目
int notleafcount(Bitree T)
{
if(T==NULL)
{
return 0;
}
else if(T->lchild == NULL && T->rchild == NULL)
return 0;
else
{
cout<<T->data; //输出非终端结点的值
int n=notleafcount(T->lchild); //左子树非终端结点的数目
int m=notleafcount(T->rchild); //右子树非终端结点的数目
return (m+n+1);
}
}
//求二叉树的全部结点数目
int node_num(Bitree T)
{
if(T==NULL)
return 0;
else
return node_num(T->lchild)+node_num(T->rchild)+1;
}
///////////////主函数///////////////
int main(int argc, const char * argv[])
{
Bitree t=NULL;
printf("请按以下两种序列输入二叉树的结点： ");
printf("AB#D##CE### 或 ABD##E##C#F## ");
createbitree(t);
cout<<"先序遍历：";
preordertraverse(t);
cout<<endl;
cout<<"中序遍历：";
inordertraverse(t);
cout<<endl;
cout<<"后序遍历：";
postordertraverse(t);
cout<<endl;
cout<<"二叉树的深度为："<<depthofbitree(t)<<endl;
int leaf=0; //叶子结点数目,初始化为0
leaf=leafcount(t);
cout<<"叶子结点数为："<<leaf<<endl;
int oneson=0; //度为1的结点数目
oneson=onesoncount(t);
cout<<"度为1的结点的数量为："<<oneson<<endl;
int notleafcount_=0; //非叶子结点的数目,初始化为0
cout<<"非叶子结点为：";/////////////
notleafcount_=notleafcount(t);//////////////????????
cout<<endl;
cout<<"非叶子结点的数量为："<<notleafcount_<<endl;
int node_number=0; //初始化全部结点的数目为0
node_number=node_num(t);
cout<<"二叉树全部结点的数量为："<<node_number<<endl;
return 1;
}
运行结果：
