#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define Status int
#define TElemType int
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define QElemType BiTree
/***********二叉树的二叉链表存储方式***********/
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
//左右孩子指针
}BiTNode, *BiTree;
/**********队列结构体定义***********/
typedef struct QNode
{
QElemType data;
struct QNode * next;
}QNode, *QueuePrt;
typedef struct
{
QueuePrt front;
QueuePrt rear;
}LinkQueue;
/***********************************/
void Menu();
void Select(BiTree &T);
Status CreateBiTree(BiTree &T);
Status DestroyBiTree(BiTree &T);
Status Visit(TElemType e);
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
Status LevelOrderTraverse(BiTNode T, Status(*Visit)(TElemType e));
Status LeafNumberCount(BiTree T);
Status BiTreeDepth(BiTree T);
Status PreBiTree(BiTree T);
Status InBiTree(BiTree T);
Status InitQueue(LinkQueue *Q);
//创建队列
Status DestroyQueue(LinkQueue *Q);
//销毁队列
Status QueueEmpty(LinkQueue *Q);
//判断队列空
Status EnQueue(LinkQueue *Q, QElemType e);
//入队
Status DeQueue(LinkQueue *Q, QElemType e);
//出队
void main()
{
BiTree T;
T = NULL;
while (1)
{
Menu();
Select(T);
}
}
void Menu()
{
system("color 02");
system("cls");
printf("\n");
printf("\t ※※※※※※※※※※※※※※※※※※※※※※※※※※※※\n");
printf("\t ※ ※\n");
printf("\t ※****************二**叉**树**的**操**作**************※\n");
printf("\t ※ ※\n");
printf("\t ※ 1: 先序创建二叉树 2: 销毁二叉树 ※\n");
printf("\t ※ ※\n");
printf("\t ※ 3: 先序遍历二叉树 4: 中序遍历二叉树 ※\n");
printf("\t ※ ※\n");
printf("\t ※ 5: 后序遍历二叉树 6: 层序遍历二叉树 ※\n");
printf("\t ※ ※\n");
printf("\t ※ 7: 叶子结点的数目 8: 测量二叉树深度 ※\n");
printf("\t ※ ※\n");
printf("\t ※ 0: 退出 ※\n");
printf("\t ※ ※\n");
printf("\t ※※※※※※※※※※※ B U G ※※※※※※※※※※※※※\n");
printf("\n\n\t\t 请选择操作:");
}
void Select(BiTree &T)
{
int a,i = 0;
while (1)
//输入检测
{
scanf("%d", &a);
getchar();
if (a >= 0 && a <= 8)
break;
else
printf("\t\t 非法数据，请重新输入:");
}
switch (a)
{
case 1:
printf("请按先序顺序输入二叉树：\n");
CreateBiTree(T);
printf("\n输入成功！\n请按任意键返回菜单...");
getch();
system("cls");
break;
case 2:
i = DestroyBiTree(T);
T = NULL;
if (i == OK)
printf("\n销毁成功！\n\n按任意键返回菜单...");
else
printf("二叉树不存在！");
getch();
system("cls");
break;
case 3:
if (T == NULL)
printf("二叉树不存在！");
else
{
printf("先序遍历二叉树为：\n\t\t");
PreBiTree(T);
}
//PreOrderTraverse(T, Visit);
printf("\n\n按任意键返回菜单...");
getch();
system("cls");
break;
case 4:
if (T == NULL)
printf("二叉树不存在！");
else
{
printf("中序遍历二叉树为：\n\t\t");
InBiTree(T);
}
//InOrderTraverse(T, Visit);
printf("\n\n按任意键返回菜单...");
getch();
system("cls");
break;
case 5:
if (T == NULL)
printf("二叉树不存在！");
else
{
printf("后序遍历二叉树为：\n\t\t");
PostOrderTraverse(T, Visit);
}
printf("\n\n按任意键返回菜单...");
getch();
system("cls");
break;
case 6:
if (T == NULL)
printf("二叉树不存在！");
else
{
printf("层序遍历二叉树为：\n\t\t");
LevelOrderTraverse(*T, Visit);
}
printf("\n\n按任意键返回菜单...");
getch();
system("cls");
break;
case 7:
i = LeafNumberCount(T);
if (i == 0)
printf("二叉树不存在！");
else
printf("二叉树中叶子结点的数目为：%d\n",i);
printf("\n\n按任意键返回菜单...");
getch();
system("cls");
break;
case 8:
i = BiTreeDepth(T);
if (i == 0)
printf("二叉树不存在！");
else
printf("二叉树的深度为：%d\n",i);
printf("\n\n按任意键返回菜单...");
getch();
system("cls");
break;
case 0:
exit(0);
//退出系统
}
}
/***********先序次序创建二叉树***********/
Status CreateBiTree(BiTree &T)
{
//按先序次序输入二叉树中节点的值（一个字符），空格字符表示空树
//构造二叉链表表示的二叉树T。
char ch;
scanf("%c", &ch);
if (ch == ' ')
T = NULL;
else
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = ch;
//生成根节点
CreateBiTree(T->lchild);
//构造左子树
CreateBiTree(T->rchild);
//构造右子树
}
return OK;
}
/*************销毁二叉树*************/
Status DestroyBiTree(BiTree &T)
{
if (T == NULL)
{
return ERROR;
}
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
free(T);
return OK;
}
/*
Status DestroyBiTree(BiTree &T)
//销毁二叉树
{
if (T != NULL && T->lchild != NULL)
DestroyBiTree(T->lchild);
//利用递归
if (T != NULL && T->rchild != NULL)
DestroyBiTree(T->rchild);
free(T);
return OK;
}
*/
Status Visit(TElemType e)
{
printf("%c", e);
return OK;
}
/*************先序遍历二叉树*************/
Status PreBiTree(BiTree T) //先序遍历二叉树
{
if (T)
{
printf("%c", T->data);
PreBiTree(T->lchild);
PreBiTree(T->rchild);
}
return OK;
}
/*
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
if (T)
{
if (Visit(T->data))
if (PreOrderTraverse(T->lchild, Visit))
if (PreOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}
*/
/*************中序遍历二叉树*************/
Status InBiTree(BiTree T) //中序遍历二叉树
{
if (T)
{
InBiTree(T->lchild);
printf("%c", T->data);
InBiTree(T->rchild);
}
return OK;
}
/*
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
if (T)
{
if (InOrderTraverse(T->lchild, Visit))
if (Visit(T->data))
if (InOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}
*/
/*************后序遍历二叉树*************/
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
if (T)
{
if (PostOrderTraverse(T->lchild, Visit))
if (PostOrderTraverse(T->rchild, Visit))
if (Visit(T->data))
return OK;
return ERROR;
}
else
return OK;
}
/*************层序遍历二叉树*************/
Status LevelOrderTraverse(BiTNode T, Status(*Visit)(TElemType e))
{
BiTree p;
LinkQueue Q;
Q.front = Q.rear = NULL;
p = &T;
if (p)
{
InitQueue(&Q);
EnQueue(&Q, p);
while (!QueueEmpty(&Q))
{
DeQueue(&Q, p);
Visit(p->data);
if (p->lchild != NULL)
EnQueue(&Q, p->lchild);
if (p->rchild != NULL)
EnQueue(&Q, p->rchild);
}
}
DestroyQueue(&Q);
return OK;
}
/***********统计二叉树中叶子结点的数目***********/
Status LeafNumberCount(BiTree T)
{
int count = 0;
if (T == NULL)
return 0;
if (T->lchild == NULL && T->rchild == NULL)
return 1;
if (T->lchild != NULL)
count += LeafNumberCount(T->lchild);
if (T->rchild != NULL)
count += LeafNumberCount(T->rchild);
return count;
}
/***********测量二叉树的深度***********/
Status BiTreeDepth(BiTree T)
{
int ldepth, rdepth;
ldepth = rdepth = 0;
if (T == NULL)
return 0;
ldepth =1 + BiTreeDepth(T->lchild);
rdepth =1 + BiTreeDepth(T->rchild);
return ldepth > rdepth ? ldepth : rdepth;
}
/***************创建队列***************/
Status InitQueue(LinkQueue *Q)
{
Q->front = Q->rear = (QueuePrt)malloc(sizeof(QNode));
if (!Q->front)
exit(OVERFLOW);
Q->front->next = NULL;
return OK;
}
/***************销毁队列***************/
Status DestroyQueue(LinkQueue *Q)
{
while (Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
/**************判断队列空**************/
Status QueueEmpty(LinkQueue *Q)
{
if (Q->front == Q->rear)
{
return TRUE;
}
else
{
return FALSE;
}
}
/****************入队****************/
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePrt p;
p = (QueuePrt)malloc(sizeof(QNode));
if (!p)
exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
return OK;
}
/***************出队***************/
Status DeQueue(LinkQueue *Q, QElemType e)
{
QueuePrt p;
if (Q->front == Q->rear)
return ERROR;
p = Q->front->next;
*e = *p->data;
Q->front->next = p->next;
if (Q->rear == p)
Q->rear = Q->front;
free(p);
return OK;
}