树和二叉树树和二叉树
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
int i=0,j=0;
#define TElemType char //二叉链表结点类型
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree(BiTree T) {
TE...
树和二叉树
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
int i=0,j=0;
#define TElemType char //二叉链表结点类型
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree(BiTree T) {
TElemType ch;
if ((ch=getchar())==' ')
T=NULL;
else
{
if (!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return T;
}
void InOrderTraverse(BiTree T) //中序递归遍历二叉树 {
if(T)
{
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
//非递归中序遍历
typedef struct //顺序栈类型定义 {
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S) //栈初始化 {
S.base=(BiTree *)malloc(sizeof(BiTree));
if(S.base==NULL)
exit(0);
S.top=S.base;
S.stacksize=100;
}
int PushStack(SqStack &S,BiTree p) //入栈 {
*S.top++=p;
return 1;
}
BiTree PopStack(SqStack &S,BiTree &p) //出栈 {
if(S.top==S.base)
return p;
p=*--S.top;
return p;
}
void InOrderTraverse2(BiTree T) //中序非递归遍历
{
SqStack S;
InitStack(S);
BiTree P=T;
while(P||(S.base!=S.top))
{
if(P)
{
PushStack(S,P);
P=P->lchild;
}
else
{
PopStack(S,P);
printf("%c",P->data);
P=P->rchild;
}
}
}
//-----------------------------层次遍历-----------------------------
typedef struct QNode {
BiTree data;
struct QNode *next; }QNode,*QueuePtr; typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit(0);
Q.front->next=NULL; }
BiTree EnQueue(LinkQueue &Q,BiTree e) //入队
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return e;
}
BiTree DeQueue(LinkQueue &Q) //出队
{
QueuePtr p;
BiTree e;
p=(QueuePtr)malloc(sizeof(QNode));
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return e;
}
void LevelOrderTraverse(BiTree p) //层次遍历 {
LinkQueue q;
q.rear=q.front=(QueuePtr)malloc(sizeof(QNode));
InitQueue(q);
EnQueue(q,p);
BiTree T;
while(q.front!=q.rear)
{
T=DeQueue(q);
printf("%c",T->data);
if(T->lchild)
EnQueue(q,T->lchild);
if(T->rchild)
EnQueue(q,T->rchild);
}
printf("\n");
}
//------------------------------------------------------------------
int Depth(BiTree T) //求二叉树高度 {
if(T==NULL)
return 0;
else
{
int deep1=Depth(T->lchild);
int deep2=Depth(T->rchild);
if(deep1>=deep2)
return deep1+1;
else
return deep2+1;
}
}
void Node(BiTree T) //求结点个数 {
if(T)
{
i++;
Node(T->lchild);
Node(T->rchild);
}
}
void Leaf(BiTree T) //求叶子个数 {
if(T)
{
if(T->lchild==NULL&&T->rchild==NULL)
j++;
Leaf(T->lchild);
Leaf(T->rchild);
}
}
void Exchange(BiTree T) //交换左右子树
{
BiTree temp;
if(T)
{
Exchange(T->lchild);
Exchange(T->rchild);
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
}
}
void main()
{
int c;
BiTree T;
T=NULL;
for(;;)
{
printf("\n主菜单:\n");
printf("1:建立一棵二叉树\n");
printf("2:中序递归遍历二叉树\n");
printf("3:中序非递归遍历二叉树\n");
printf("4:层次遍历二叉树\n");
printf("5:求二叉树的高度\n");
printf("6:求二叉树的结点个数\n");
printf("7:求二叉树的叶子个数\n");
printf("8:交换二叉树每个结点的左子树和右子树\n");
printf("请选择相应的操作:\n");
scanf("%d",&c);
getchar();
switch(c)
{
case 1:printf("请输入字符数据:\n");
T=CreateBiTree(T);printf("二叉树建立完毕\n");break;
case 2:printf("中序递归遍历:\n");
InOrderTraverse(T);
printf("\n");break;
case 3:printf("中序非递归遍历:\n");
InOrderTraverse2(T);
printf("\n");
break;
case 4:printf("层次遍历:\n");
LevelOrderTraverse(T);break;
case 5:Depth(T);
printf("二叉树的高度为:%d",Depth(T));
printf("\n");break;
case 6:Node(T);
printf("二叉树的结点个数为:%d",i);
printf("\n");break;
case 7:Leaf(T);
printf("二叉树的叶子个数为%d",j);
printf("\n");break;
case 8:Exchange(T);
printf("交换完毕\n");break;
}
}
}
本文档为【树和二叉树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483