#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define ElemType BiTNode*
typedef char TElemType;
typedef int Status;
//二叉链表结点类型、二叉链表类型
typedef struct BiTNode
{
TElemType data; //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
//--------------------------相关操作--------------------------------
typedef struct LinkQueueNode
{
BiTree data;
struct LinkQueueNode *next;
}LKQueNode;
typedef struct LKQueue
{
LKQueNode *front,*rear;
}LKQue;
//初始化队列
void InitQueue(LKQue *LQ)
{
LKQueNode *p;
p = (LKQueNode*)malloc(sizeof(LKQueNode));
LQ->front = p;
LQ->rear = p;
LQ->front->next = NULL;
}
//判断队列是否为空
int EmptyQueue(LKQue *LQ)
{
if(LQ->front == LQ->rear)
return 1;
else
return 0;
}
//入队列
void EnQueue(LKQue &LQ,ElemType x)
{
LKQueNode* p;
p = (LKQueNode*)malloc(sizeof(LKQueNode));
p->data = x;
p->next = NULL;
LQ.rear->next = p;
LQ.rear = p;
}
//出队列
int OutQueue(LKQue *LQ)
{
LKQueNode *s;
if ( EmptyQueue(LQ))
{
exit(0);
return 0;
}
else
{
s = LQ->front->next;
LQ->front->next = s->next;
if(s->next == NULL)
LQ->rear = LQ->front;
free(s);
return 1;
}
}
//1:创建二叉树
Status CreatBiTree(BiTree &T) {
TElemType ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {//创建结点
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch; // 生成根结点
CreatBiTree(T->lchild); // 构造左子树
CreatBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreatBiTree
//访问结点
void visit(BiTNode* T) {
printf("%c", T->data);
}
//2: 先序遍历
void PreOrderTraverse(BiTree T)
{
if(T)
{
visit(T); //“访问”根结点:输出打印根结点
PreOrderTraverse(T->lchild);//先序遍历左子树
PreOrderTraverse(T->rchild);//先序遍历右子树
}
}
//3:中序遍历
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);//中序遍历左子树
visit(T); //“访问”根结点:输出打印根结点
InOrderTraverse(T->rchild);//中序遍历右子树
}
}
//4:后序遍历
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);//后序遍历左子树
PostOrderTraverse(T->rchild);//后序遍历右子树
visit(T); //“访问”根结点:输出打印根结点
}
}
//5:层次遍历
void LevelOrder(BiTree bt)
{
LKQue Q;
BiTree p;
InitQueue(&Q);
//if(bt != NULL)
//{
// EnQueue(Q,bt);
//}
while(!EmptyQueue(&Q))
{
//p = GetHead(Q);
OutQueue(&Q);
visit(p);
if(p->lchild != NULL)
EnQueue(Q,p->lchild);
if(p->rchild != NULL)
EnQueue(Q,p->rchild);
}
}
/* 计算度为0的结点*/
int n = 0;
void LeafCount(BiTree T)
{
if(T)
{
if(T->lchild == NULL && T->rchild == NULL)
{
visit(T);
n++;
}
LeafCount(T->lchild);
LeafCount(T->rchild);
}
}
/*求二叉树高度*/
int PostHeight(BiTree T)
{
int high = 0;
int l,r;
if(T)
{
l=PostHeight(T->lchild);
r=PostHeight(T->rchild);
if(l>r)
{
high = l+1;
}
else{
high = r+1;
}
}
return high;
}
/*求二叉树结点总数*/
int PostAllcount(BiTree T){
int a ,b;
if(T ==NULL)
return 0;
else
{
a =PostAllcount(T->lchild);
b =PostAllcount(T->rchild);
return a+b+1;
}
}
//主函数
int main()
{
BiTree T;
printf("创建一个二叉树:\n");
CreatBiTree(T);
printf("\n先序遍历结果:\n");
PreOrderTraverse(T);
printf("\n中序遍历结果:\n");
InOrderTraverse(T);
printf("\n后序遍历结果:\n");
PostOrderTraverse(T);
printf("\n层次遍历的结果:\n");
LevelOrder(T);
printf("\n叶子结点是:\n");
LeafCount(T);
printf("\n叶子结点总数是:\n");
printf("%d\n",n);
printf("二叉树高度是:%d\n",PostHeight(T));
printf("二叉树结点总数:%d\n",PostAllcount(T));
return 0;
}
你题目的解答代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define ElemType BiTNode*
typedef char TElemType;
typedef int Status;
//二叉链表结点类型、二叉链表类型
typedef struct BiTNode
{
TElemType data; //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
//--------------------------相关操作--------------------------------
typedef struct LinkQueueNode
{
BiTree data;
struct LinkQueueNode *next;
}LKQueNode;
typedef struct LKQueue
{
LKQueNode *front,*rear;
}LKQue;
//初始化队列
void InitQueue(LKQue *LQ)
{
LKQueNode *p;
p = (LKQueNode*)malloc(sizeof(LKQueNode));
LQ->front = p;
LQ->rear = p;
LQ->front->next = NULL;
}
//判断队列是否为空
int EmptyQueue(LKQue *LQ)
{
if(LQ->front == LQ->rear)
return 1;
else
return 0;
}
//入队列
void EnQueue(LKQue &LQ,BiTree x)
{
LKQueNode* p;
p = (LKQueNode*)malloc(sizeof(LKQueNode));
p->data = x;
p->next = NULL;
LQ.rear->next = p;
LQ.rear = p;
}
//出队列
int OutQueue(LKQue *LQ ,BiTree *p)
{
LKQueNode *s;
if ( EmptyQueue(LQ))
{
exit(0);
return 0;
}
else
{
s = LQ->front->next;
LQ->front->next = s->next;
if(s->next == NULL)
LQ->rear = LQ->front;
*p = s->data;
free(s);
return 1;
}
}
//1:创建二叉树
Status CreatBiTree(BiTree &T) {
TElemType ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {//创建结点
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch; // 生成根结点
CreatBiTree(T->lchild); // 构造左子树
CreatBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreatBiTree
//访问结点
void visit(BiTNode* T) {
printf("%c", T->data);
}
//2: 先序遍历
void PreOrderTraverse(BiTree T)
{
if(T)
{
visit(T); //“访问”根结点:输出打印根结点
PreOrderTraverse(T->lchild);//先序遍历左子树
PreOrderTraverse(T->rchild);//先序遍历右子树
}
}
//3:中序遍历
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);//中序遍历左子树
visit(T); //“访问”根结点:输出打印根结点
InOrderTraverse(T->rchild);//中序遍历右子树
}
}
//4:后序遍历
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);//后序遍历左子树
PostOrderTraverse(T->rchild);//后序遍历右子树
visit(T); //“访问”根结点:输出打印根结点
}
}
//5:层次遍历
void LevelOrder(BiTree bt)
{
LKQue Q;
BiTree p;
InitQueue(&Q);
EnQueue(Q,bt);
//if(bt != NULL)
//{
// EnQueue(Q,bt);
//}
while(!EmptyQueue(&Q))
{
OutQueue(&Q,&p);
visit(p);
if(p->lchild != NULL)
EnQueue(Q,p->lchild);
if(p->rchild != NULL)
EnQueue(Q,p->rchild);
}
}
/* 计算度为0的结点*/
int n = 0;
void LeafCount(BiTree T)
{
if(T)
{
if(T->lchild == NULL && T->rchild == NULL)
{
visit(T);
n++;
}
LeafCount(T->lchild);
LeafCount(T->rchild);
}
}
/*求二叉树高度*/
int PostHeight(BiTree T)
{
int high = 0;
int l,r;
if(T)
{
l=PostHeight(T->lchild);
r=PostHeight(T->rchild);
if(l>r)
{
high = l+1;
}
else{
high = r+1;
}
}
return high;
}
/*求二叉树结点总数*/
int PostAllcount(BiTree T){
int a ,b;
if(T ==NULL)
return 0;
else
{
a =PostAllcount(T->lchild);
b =PostAllcount(T->rchild);
return a+b+1;
}
}
//主函数
int main()
{
BiTree T;
printf("创建一个二叉树:\n");
CreatBiTree(T);
printf("\n先序遍历结果:\n");
PreOrderTraverse(T);
printf("\n中序遍历结果:\n");
InOrderTraverse(T);
printf("\n后序遍历结果:\n");
PostOrderTraverse(T);
printf("\n层次遍历的结果:\n");
LevelOrder(T);
printf("\n叶子结点是:\n");
LeafCount(T);
printf("\n叶子结点总数是:\n");
printf("%d\n",n);
printf("二叉树高度是:%d\n",PostHeight(T));
printf("二叉树结点总数:%d\n",PostAllcount(T));
return 0;
}
如有帮助,望采纳!谢谢!