可能编译时会有些语法小错误（比如分号，->，等），很容易就自己纠正了哦，思路绝对是完全正确的，所以用的话就自己试着改改吧，直接复制粘贴，就正确，岂不是太没写代码体验了，自己改改才印象更加深刻的呢(▽)~~~~；
//中序遍历的递归与非递归算法
#include<iostream>
using namespace std;
#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct BiNode{ //二叉链表定义
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
/************************************* 队列 ***************************************/
typedef BiTree QElemType;
typedef struct{
QElemType *base;//初始化时动态分配存储空间
int front;//头指针
int rear;//尾指针
int last;
}SqQueue;
//算法3.13 循环队列的初始化
Status InitQueue(SqQueue &Q)
{ // 构造一个空队列Q
Q.base = new QElemType[MAXQSIZE];
if(!Q.base)
{
return OVERFLOW; // 存储分配失败
}
Q.front = 0;
Q.rear = 0;
return OK;
}
//算法3.14 求循环队列的长度
int QueueLength(SqQueue Q)
{// 返回Q的元素个数，即队列的长度
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
int QueueEmpty(SqQueue &Q)
{
if (Q.front==Q.rear) return OK;
else return ERROR;
}
//算法3.15 循环队列的入队
Status EnQueue(SqQueue &Q,QElemType e)
{// 插入元素e为Q的新的队尾元素
if((Q.rear+1)%MAXQSIZE == Q.front)
{
return ERROR;//尾指针在循环意义上加1后等于头指针，表明队满
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
//算法3.16 循环队列的出队
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.rear == Q.front)
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front+1)%MAXQSIZE;
return OK;
}
BiTree GetHead(SqQueue Q)
{//返回Q的队列元素，不修改队头指针
if(Q.front!=Q.rear) //队列非空
return Q.base[Q.front]; //返回队头元素的值，队头指针不变
}
/************************************************************************************/
//用算法5.3 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T){
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
cin >> ch;
if(ch=='#') T=NULL; //递归结束，建空树
else{
T=new BiTNode;
T->data=ch; //生成根结点
CreateBiTree(T->lchild); //递归创建左子树
CreateBiTree(T->rchild); //递归创建右子树
} //else
} //CreateBiTree
void InOrderTraverse(BiTree T){
//中序遍历二叉树T的递归算法
if(T){
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
}
}
//实现按层遍历二叉树的非递归算法（队列）
void HierarchyTraverse(BiTree T)
{
BiTree bt = T;
SqQueue Q;
InitQueue(Q);
if(!bt){
return;
}
EnQueue(Q,bt);
while(Q.rear!=Q.front){
DeQueue(Q,bt);
cout<<bt->data;
if(bt->lchild!=NULL){
EnQueue(Q,bt->lchild);
}
if(bt->rchild!=NULL){
EnQueue(Q,bt->rchild);
}
}
}
//统计二叉树中的叶子结点个数
int LeafNodeCount(BiTree T){
if(T==NULL) return 0;
else if(T->lchild==NULL&&T->rchild==NULL)
return 1;
else
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
}
//-------------------
int Depth(BiTree T)
{
int m,n;
if(T == NULL ) return 0; //如果是空树，深度为0，递归结束
else
{
m=Depth(T->lchild); //递归计算左子树的深度记为m
n=Depth(T->rchild); //递归计算右子树的深度记为n
if(m>n) return(m+1); //二叉树的深度为m 与n的较大者加1
else return (n+1);
}
}
int LevelWidth(BiTree root,int level)//find the width of a level(amounts of nodes in the level).
{
if(!root)return 0;
else
{
if(level==1)return 1;
level=LevelWidth(root->lchild,level-1)+LevelWidth(root->rchild,level-1);
}
return level;
}
int Width(BiTree root)//find the maximum width of the btree.
{
int width,i;
int w[20];
for(i=0;i<20;i++)w[i]=0;
if(!root)width=0;
else
{
for(i=0;i<=Depth(root);i++)w[i]=LevelWidth(root,i+1);
}
i=0;
while(w[i])
{
if(w[i]>width)width=w[i];
i++;
}
return width;
}
// // -------------------
nt main(){
BiTree tree;
cout<<"请输入建立二叉链表的序列：
";
CreateBiTree(tree);
cout<<"中序遍历的结果为：
";
InOrderTraverse(tree);
cout<<endl;
//按层遍历二叉树
cout<<"按层遍历的结果为：
";
HierarchyTraverse(tree);
cout<<endl;
cout<<"二叉树的宽度为"<<Width(tree)<<endl;
//统计叶子结点树
cout<<"叶子结点数为"<<LeafNodeCount(tree);
cout<<"
";
return 0;
}