实现二叉树的二叉链表存储结构； 递归实现先序、中序和后序遍历二叉树； 非递归实现先序、中序、后序、层

Question

如题所述

Answer 1

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define NULL 0
#define FALSE 0
#define ERROR 0
#define WRONG 0
#define OK 1
#define OVERFLOW 0
typedef int TElemType;
typedef int Status;
//二叉树结构体
typedef struct BiTNode
{
TElemType data;//结点的值
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//队列结构体
typedef BiTree QElemType;
typedef struct QNode
{
QElemType data;
QNode *next;
}*QueuePtr;
struct LinkQueue
{
QueuePtr front,rear;//队头，队尾指针
};
//队列操作
void InitQueue(LinkQueue &Q)
{//初始化一个队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)//生成头结点失败
exit(OVERFLOW);
Q.front->next=NULL;
}
Status QueueEmpty(LinkQueue Q)
{ //判断队列是否为空
if(Q.front->next==NULL)
return TRUE;
else return FALSE;
}
void EnQueue(LinkQueue &Q,QElemType e)
{ //插入元素e为队列Q的新的队尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
//动态生成新结点
if(!p)
exit(OVERFLOW);
p->data=e;//将e的值赋给新结点
p->next=NULL;//新结点的指针为空
Q.rear->next=p;//原队尾结点的指针域为指向新结点
Q.rear=p;//尾指针指向新结点
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ //若队列不为空，删除Q的队头元素，用e返回其值
QueuePtr p;
if(Q.front==Q.rear)//队列为空
return ERROR;
p=Q.front->next;//p指向队头结点
e=p->data;//队头元素赋给e
Q.front->next=p->next;//头结点指向下一个结点
if(Q.rear==p)//如果删除的队尾结点
Q.rear=Q.front;//修改队尾指针指向头结点
free(p);
return OK;
}
//#define ClearBiTree DestoryBiTree//清空二叉树的操作和销毁二叉树的操作一样
void InitBiTree(BiTree &T)
{ T=NULL;
}
void DestroyBiTree(BiTree &T)
{ //销毁二叉树
if(T)
{
DestroyBiTree(T->lchild);//销毁左子树
DestroyBiTree(T->rchild);//销毁右子树
free(T);
T=NULL;
}
}
void PreOrderTraverse(BiTree T,void(*visit)(TElemType))
{//先序遍历二叉树
if(T)
{
visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
}
void InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍历二叉树
if(T)
{ InOrderTraverse(T->lchild,visit);
visit(T->data);
InOrderTraverse(T->rchild,visit);
}
}
void PostOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //后序遍历二叉树
if(T)
{ PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
}
}
Status BiTreeEmpty(BiTree T)
{ //判断二叉树是否为空
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)//返回T的深度
{ int i,j;
if(!T)
return 0;
i=BiTreeDepth(T->lchild);//i为左孩子的深度
j=BiTreeDepth(T->rchild);//j为右孩子的深度
return i>j?i+1:j+1;
}
TElemType Root(BiTree T)
{ //返回二叉树的根结点
if(BiTreeEmpty(T))
return NULL;
else
return T->data;
}
TElemType Value(BiTree p)
{//返回P所指结点的值
return p->data;
}
void Assign(BiTree p,TElemType value)
{ //给P的结点赋新值
p->data=value;
}
BiTree Point(BiTree T,TElemType s)//返回二叉树T中指向元素值为S的结点指针
{ LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化队列
EnQueue(q,T);//根指针入队
while(!QueueEmpty(q))//队不空
{ DeQueue(q,a);//出队，队列元素赋给e
if(a->data==s)//a所指结点为的值为s
return a;
if(a->lchild)//有左孩子
EnQueue(q,a->lchild);//入队左孩子
if(a->rchild)//有右孩子
EnQueue(q,a->rchild);//入队右孩子
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{ a=Point(T,e);//a是指向结点e的指针
if(a&&a->lchild)
return a->lchild->data;
}
return NULL;
}
TElemType RightChild(BiTree T,TElemType e)
{ BiTree a;
if(T)
{ a=Point(T,e);//a是指向结点e的指针
if(a&&a->rchild)//T中存在结点e并且e存在右孩子
return a->rchild->data;
}
return NULL;
}
Status DeleteChild(BiTree p,int LR)
{ if(p)
{ if(LR==0)
DestroyBiTree(p->lchild);
else
DestroyBiTree(p->rchild);
return OK;
}
return ERROR;
}
void visit(TElemType e)
{ printf("%d",e);
}
void LevelOrderTraverse(BiTree T,void(*visit)(TElemType))
{//层序遍历
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化队列
EnQueue(q,T);//根指针入队
while(!QueueEmpty(q))
{ DeQueue(q,a);//出队元素，赋给a
visit(a->data);//访问a所指结点
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
}
}
void CreateBiTree(BiTree &T)
{ TElemType ch;
scanf("%d",&ch);//输入结点的值
if(ch==0)//结点为空
T=NULL;
else
{T=(BiTree)malloc(sizeof(BiTNode));
//生成根结点
if(!T)
exit(OVERFLOW);
T->data=ch;//将值赋给T所指结点
CreateBiTree(T->lchild);//递归构造左子树
CreateBiTree(T->rchild);
}
}

TElemType Parent(BiTree T,TElemType e)
{//返回双亲
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);
EnQueue(q,T);//树根入队列
while(!QueueEmpty(q))//队不空
{DeQueue(q,a);//出队，队列元素赋给a
if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)//找到e
return a->data;
else
{ if(a->lchild)
EnQueue(q,a->lchild);//入队列左孩子
if(a->rchild)
EnQueue(q,a->rchild);//入队列右孩子
}
}
}
return NULL;
}
TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{ p=Point(T,a);//p指向结点a的指针
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e
return p->lchild->data;
}
}
return NULL;
}
TElemType RightSibling(BiTree T,TElemType e)
{ //返回右孩子
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{ p=Point(T,a);//p为指向结点的a的指针
if(p->lchild&&p->rchild&&p->lchild->data==e)
return p->lchild->data;
}
}
return NULL;
}
Status InsertChild(BiTree p,int LR,BiTree c)
{ //根据LR为0或1，插入C为T中P所指结点的左或右子树，P所结点的原有左或右子树则成为C的右子树
if(p)
{ if(LR==0)//把二叉树C插入P所指结点的子树
{ c->rchild=p->lchild;//p所结点的原有左子树成为C的右子树
p->lchild=c;//二叉树成为P的左子树
}
else{ c->rchild=p->rchild;//p指结点的原有右子树成为C的右子树
p->rchild=c;
}
return OK;
}
return ERROR;
}
//主函数文件
void main()
{ int i,j;
BiTree T,p,c;
TElemType e0,e1,e2,e3,e4;
InitBiTree(T);//初始化二叉树
printf("构造二叉树后，树空否?%d(1,是,0否).树的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
CreateBiTree(T);//建立二叉树T
printf("构造二叉树后，树空否?%d(1,是,0否).树的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);//e1为二叉树T的根结点的值
if(e1!=NULL)
printf("二叉树的根为%d",e1);
else
printf("树空，无根");
e2=LeftChild(T,e1);
printf("左孩子:%d",e2);
e3=RightChild(T,e1);
printf("右孩子:%d",e3);
printf("\n");
printf("先序递归遍历:\n");
PreOrderTraverse(T,visit);
printf("\n");
printf("后序递归遍历:\n");
PostOrderTraverse(T,visit);
printf("\n");
printf("中序递归遍历:\n");
InOrderTraverse(T,visit);
printf("\n");
printf("输入一个结点的值:");
scanf("%d",&e1);
p=Point(T,e1);//p指向为e的指针
printf("结点的值为%d\n",Value(p));

e0=Parent(T,e1);//返回e1的双亲
printf("结点%d的双亲为%d",e1,e0);
printf("\n");
e0=LeftChild(T,e1);//返回e1的左孩子
if(e0==NULL)
printf("没有孩子");
else
printf("左孩子为%d",e0);
printf("\n");
e0=RightChild(T,e1);//返回e1的右孩子
if(e0==NULL)
printf("没有右孩子");
else
printf("右孩子为%d",e0);
printf("\n");

e0=RightSibling(T,e1);//返回e1的右兄弟
if(e0!=NULL)
printf("右兄弟为%d",e0);
else
printf("没有右兄弟");
printf("\n");
e0=LeftSibling(T,e1);//返回e1的左兄弟
if(e0!=NULL)
printf("左兄弟为%d",e0);
else
printf("没有左兄弟");
printf("\n");
printf("要改变结点%d的值，请输入新值:",e1);
scanf("%d",&e2);
Assign(p,e2);//将e2的值赋给p所指结点，代替e1
printf("层序遍历二叉树:\n");
LevelOrderTraverse(T,visit);
printf("\n");
printf("创建一棵根结点右子树为空的新树:");
CreateBiTree(c);//创建二叉树
printf("先序递归遍历二叉树c:\n");
PreOrderTraverse(c,visit);
printf("将树C插入树T中，请输入树T中树C的双亲结点C为左（0）或右（1）子树:");
scanf("%d,%d",&e1,&i);
p=Point(T,e1);//p指向二叉树T中将T中作为二叉树C的双亲结点的e1
InsertChild(p,i,c);//将树C插入到二叉树T中作为结点的左或右子树
printf("构造二叉树后，树空否?%d(1,是,0否).树的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visit);
}