/* 二叉树应用 */#include "stdio.h"
#include "stdlib.h"typedef char ElemType; /* 结点数据的类型 */
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode; /* 树结点类型 *//*栈的定义及基本操作*/
#define MaxSize 100
typedef BiTNode* SElemType; /* 栈和队列的结点类型，用于存放树结点 */
typedef struct {
SElemType elem[MaxSize];
int top;
}SqStack; /* 栈 */void InitStack(SqStack *pS) /* 初始化栈,开始时栈为空 */
{
pS->top=0; /* top指向栈顶的上一个元素 */
}int Push(SqStack *pS,SElemType e) /* 进栈 */
{
if (pS->top==MaxSize-1) /* 栈满 */
return 0; pS->elem[pS->top]=e;
pS->top=pS->top+1;
return 1;
}int Pop(SqStack *pS,SElemType *pe) /* 出栈 */
{
if (pS->top==0) /* 栈空 */
return 0; pS->top = pS->top - 1;
*pe = pS->elem[pS->top];
return 1;
}/*队列（循环队列）的定义及基本操作*/typedef struct {
SElemType elem[MaxSize];
int front,rear;
}SqQueue; /* 队列 */void InitQueue(SqQueue* pQ) /* 初始化队列,开始时队列为空 */
{
pQ->front=pQ->rear=0;
}int EnQueue(SqQueue* pQ,SElemType e) /* 进队 */
{
if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满 */
return 0;
pQ->elem[pQ->rear] = e;
pQ->rear = (pQ->rear+1)%MaxSize;
return 1;
}int DeQueue(SqQueue* pQ,SElemType* pe) /* 出队 */
{
if (pQ->rear == pQ->front) /* 队空 */
return 0;
*pe = pQ->elem[pQ->front];
pQ->front = (pQ->front+1)%MaxSize;
return 1;
}
/* 先根遍历 */
void preorder(BiTNode *bt)
{ if(bt!=NULL)
{ printf("%c ",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
} /* 中根遍历 */
void inorder(BiTNode *bt)
{ if(bt!=NULL)
{ inorder(bt->lchild);
printf("%c ",bt->data);
inorder(bt->rchild);
}
}
/* 后根遍历 */
void postorder(BiTNode *bt)
{ if(bt!=NULL)
{ postorder(bt->lchild);
postorder(bt->rchild);
printf("%c ",bt->data);
}
}/* 非递归算法的中根遍历（后进先出，用了栈的思想） */
void inorder_fdg(BiTNode *bt)
{
BiTNode *p;
SqStack s;
InitStack(&s);
p=bt;
do
{ while(p!=NULL)
{ Push(&s,p);
p=p->lchild;
}
if(s.top!=0)
{ Pop(&s,&p);
printf("%c ",p->data);
p=p->rchild;
}
}while(s.top!=0||p!=NULL);
}/* 用队列实现层次遍历 */
void lev_traverse(BiTNode* bt)
{
SqQueue q;
BiTNode *p;
p=bt;
InitQueue(&q);
EnQueue(&q,p);
while(!(q.rear==q.front)) { /* 当队列不空 */
DeQueue(&q,&p);
printf("%c ",p->data); if(p->lchild!=NULL)
EnQueue(&q,p->lchild); if(p->rchild!=NULL)
EnQueue(&q,p->rchild);
}
}
/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过函数返回,避免使用指针的指针 */
BiTNode *crt_bt_pre()
{ char ch;
BiTNode *bt;
scanf("%c",&ch); if(ch==' ') bt=NULL;
else
{ bt=(BiTNode *)malloc(sizeof(BiTNode));
bt->data=ch;
bt->lchild=crt_bt_pre();
bt->rchild=crt_bt_pre();
}
return(bt);
}/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过参数返回,注意和上述方法比较，想想还有什么办法？ */
void crt_bt_pre_2(BiTNode **bt)
{ char ch;
scanf("%c",&ch); if(ch==' ') (*bt)=NULL;
else
{ (*bt)=(BiTNode *)malloc(sizeof(BiTNode));
(*bt)->data=ch;
crt_bt_pre_2(&(*bt)->lchild);
crt_bt_pre_2(&(*bt)->rchild);
}
}
/* 求叶子数 */
int leaf(BiTNode *bt)
{
if (bt==NULL) return 0;
else {
if (bt->lchild==NULL&&bt->rchild==NULL) return 1;
else
return leaf(bt->lchild)+leaf(bt->rchild);
}}/* 求树的高度 */
int high(BiTNode *bt)
{
if (bt==NULL) return 0;
else {
return max(high(bt->lchild),high(bt->rchild))+1;
}}
/* 二叉树的释放*/
void freetree(BiTNode *bt)
{ if(bt!=NULL)
{ freetree(bt->lchild);
freetree(bt->rchild);
free(bt);
bt=NULL;
}
}main()
{
BiTNode *T,*temp[20]; /* 笨方法建立二叉树 */
/* temp[0]=(BiTNode*)malloc(sizeof(BiTNode));
temp[0]->data = '-'; temp[1]=(BiTNode*)malloc(sizeof(BiTNode));
temp[1]->data = '+';
temp[0]->lchild = temp[1]; temp[2]=(BiTNode*)malloc(sizeof(BiTNode));
temp[2]->data = '/';
temp[0]->rchild = temp[2]; temp[3]=(BiTNode*)malloc(sizeof(BiTNode));
temp[3]->data = 'a';
temp[3]->lchild=NULL; temp[3]->rchild=NULL;
temp[1]->lchild = temp[3]; temp[4]=(BiTNode*)malloc(sizeof(BiTNode));
temp[4]->data = '*';
temp[1]->rchild = temp[4]; temp[5]=(BiTNode*)malloc(sizeof(BiTNode));
temp[5]->data = 'e';
temp[5]->lchild=NULL; temp[5]->rchild=NULL;
temp[2]->lchild = temp[5]; temp[6]=(BiTNode*)malloc(sizeof(BiTNode));
temp[6]->data = 'f';
temp[6]->lchild=NULL; temp[6]->rchild=NULL;
temp[2]->rchild = temp[6]; temp[7]=(BiTNode*)malloc(sizeof(BiTNode));
temp[7]->data = 'b';
temp[7]->lchild=NULL; temp[7]->rchild=NULL;
temp[4]->lchild = temp[7]; temp[8]=(BiTNode*)malloc(sizeof(BiTNode));
temp[8]->data = '-';
temp[4]->rchild = temp[8]; temp[9]=(BiTNode*)malloc(sizeof(BiTNode));
temp[9]->data = 'c';
temp[9]->lchild=NULL; temp[9]->rchild=NULL;
temp[8]->lchild = temp[9]; temp[10]=(BiTNode*)malloc(sizeof(BiTNode));
temp[10]->data = 'd';
temp[10]->lchild=NULL; temp[10]->rchild=NULL;
temp[8]->rchild = temp[10]; T=temp[0]; */
/*输出树和各种遍历、叶子数、树的高度*/
/*printf("\ntree:\n");
printf(" -\n");
printf(" + /\n");
printf(" a * e f\n");
printf("0 0b - 0 00 0\n");
printf(" 0 0c d\n"); printf("\n\nPreOrder:\n");
preorder(T); printf("\nInOrder:\n");
inorder(T); printf("\nPostOrder:\n");
postorder(T); printf("\ninorder_fdg:\n");
inorder_fdg(T); printf("\nlev_traverse:\n");
lev_traverse(T);
printf("\nleaf num:%d",leaf(T));
printf("\nTree high:%d",high(T));
freetree(T); */ /* 按先序列建树，用空格表示空子树*/ printf("\n\nplease input inorder:such as 'abc de g f '\n");
/*T = crt_bt_pre();*/
crt_bt_pre_2(&T); printf("\n\nPreOrder:\n");
preorder(T); printf("\nInOrder:\n");
inorder(T); printf("\nPostOrder:\n");
postorder(T); printf("\ninorder_fdg:\n");
inorder_fdg(T); printf("\nlev_traverse:\n");
lev_traverse(T);
printf("\nleaf num:%d",leaf(T));
printf("\nTree high:%d",high(T));
freetree(T);
getch();
}
这。。。是教程中的作业吧，多看看书吧先
山炮这都不会啊
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024