#include<stdio.h>
#include<stdlib.h>
#include<string.h> #define num 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define FALSE 0
#define TRUE 1 typedef int Status;
typedef char DataType; typedef struct node
{
DataType data;
struct node *lchild,*rchild;
}BinTNode,*BinTree; typedef BinTNode* ElemType; #define QueueSize 100
//循环队列的存储结构
typedef struct
{
ElemType *base;
int front,rear;
}SeQueue; Status CreateBiTree(BinTree &bt)
{//按照先序遍历次序递归建立二叉树。
//ABC@@DE@G@@F@@
char ch;
scanf("%c",&ch);
if(ch == '@') bt = NULL;
else
{
bt = (BinTNode*)malloc(sizeof(BinTNode));
bt->data = ch; //生成根结点
CreateBiTree(bt->lchild); //构造左子树
CreateBiTree(bt->rchild); //构造右子树
}
return OK;
} Status Inorder(BinTree bt)
{//二叉树中序遍历非递归算法
BinTNode *stack[num]; //定义栈数组
int top = ; //初始化栈
stack[top] = bt;
do
{
while(NULL!=stack[top])
{//扫描根结点及其所有的左结点并入栈
top = top+;
stack[top] = stack[top-]->lchild;
}
top = top-; //退栈
if(top>=) //判断栈是否为空
{
printf("%c",stack[top]->data); //访问结点
stack[top] = stack[top]->rchild; //扫描右子树
}
}while(top>=);
return OK;
} void PostOrder(BinTree bt)
{//二叉树后序遍历递归算法
if(bt)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%c",bt->data);
} } int Size(BinTree bt)
{//统计二叉树中所有结点的个数
int num1,num2;
if(bt==NULL)
return ;
else if(bt->lchild==NULL && bt->rchild==NULL)
return ;
else
{
num1 = Size(bt->lchild);
num2 = Size(bt->rchild);
return (num1+num2+);
}
} int LeafCount(BinTree bt)
{//叶子结点总数为
int LeafNum;
if(bt==NULL)
LeafNum = ;
else if((bt->lchild==NULL) && (bt->rchild==NULL)) LeafNum = ;
else LeafNum = LeafCount(bt->lchild)+LeafCount(bt->rchild);
//叶子数为左右子树叶子数目之和
return LeafNum;
} int Depth(BinTree bt)
{//统计二叉树深度
int hl,hr,max;
if(bt!=NULL)
{
hl = Depth(bt->lchild); //求左子树的深度
hr = Depth(bt->rchild); //求右子树的深度
max = hl>hr?hl:hr;
return (max+); //返回树的深度
}
else
return ;
} void Exchange(BinTree bt)
{//交换左右二叉树
if(bt == NULL)
return;
BinTNode *temp;
temp = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = temp;
Exchange(bt->lchild);
Exchange(bt->rchild);
} //构造一个循环队列
Status InitQueue(SeQueue &Q)
{
Q.base = (ElemType *)malloc(QueueSize *sizeof(ElemType));
if(!Q.base) exit();
Q.front = Q.rear = ;
return OK;
}
//插入新的元素为队尾元素
Status EnQueue(SeQueue &Q,ElemType e)
{
if((Q.rear+)%QueueSize==Q.front)
{
printf("Queue overflow");
return ;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear+)%QueueSize;
return ;
} //删除队头元素
Status DeleteQ(SeQueue &Q,ElemType &e)
{
if(Q.front == Q.rear)
{
printf("Queue enpty");
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front+)%QueueSize;
return OK;
} //判空循环队列
Status IsEmptyQ(SeQueue Q)
{
if(Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
//层次遍历二叉树
void LevelOrderTraversal(BinTree bt)
{
SeQueue Q;
ElemType e;
//若是空树，则直接返回
InitQueue(Q); //创建并初始化队列
if(bt) EnQueue(Q,bt);
while(!IsEmptyQ(Q))
{
DeleteQ(Q,e);
printf("%4c",e->data);
if(e->lchild) EnQueue(Q,e->lchild);
if(e->rchild) EnQueue(Q,e->rchild);
}
} void main()
{
BinTree bt;
int xz = ;
int yz,sd;
while(xz)
{
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");
scanf("%d",&xz);
getchar();
switch(xz)
{//输入：ABC@@DE@G@@F@@@输出：CBEGDFA
case :
printf("输入二叉树的先序序列结点值：\n");
CreateBiTree(bt);
printf("二叉树的链式存储结构建立完成\n");
printf("\n");
break;
case :
printf("该二叉树的后序遍历序列是：");
PostOrder(bt);
printf("\n"); //输出CGEFDBA
printf("该二叉树的中序遍历序列是：");
Inorder(bt);
printf("\n"); //输出CBEGDFA
printf("该二叉树的结点的个树是：%d\n",Size(bt));
yz = LeafCount(bt);
printf("叶子结点个数是：%d\n",yz);
sd = Depth(bt);
printf("该二叉树的深度是：%d\n",sd);
printf("\n");
break;
case :
Exchange(bt);
printf("该二叉树已交换左右子树！\n");
printf("\n");
break;
case :
printf("该二叉树的层序遍历序列是：");
LevelOrderTraversal(bt);
printf("\n"); //输出ABCDEFG
break;
case :
break;
default:printf("请输入正确的选项：（0~4）：\n"); }
}
}