#include <iostream>
#include <cstdio>
#include <malloc.h> //在本程序中空==0
using namespace std;
#define FLASE 0
#define TRUE 1
#define ERROR 0
#define OK 1
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;
}*QueueRtr;
struct LinkQueue
{
QueueRtr ifront,irear;
};
void DestroyBiTree(BiTree &T);
void InitQueue(LinkQueue &Q)
{
Q.ifront=Q.irear=(QueueRtr)malloc(sizeof(QNode));//生成头结点
if(!Q.ifront)
exit(0);
Q.ifront->next=NULL;//头结点的next域为空
}
void DestroyQueue(LinkQueue &Q)
{
while(Q.ifront) //Q.ifront不为空
{
Q.irear=Q.ifront->next;//Q.rear指向Q.front的下一个结点
free(Q.ifront);//释放Q.front所指的结点
Q.ifront=Q.irear; //Q.front指向Q,front的下一个结点
}
}
Status QueueEmpty(LinkQueue Q)
{
if(Q.ifront->next==NULL)
return TRUE;
else
return FLASE;
}
int QueueLength(LinkQueue Q)
{
int i=0;
QueueRtr p=Q.ifront;//p指向头结点
while(Q.irear!=p) //p所指的不是尾结点
{
i++;
p=p->next; //p指向下一个结点
}
return i;
}
void EnQueue(LinkQueue &Q,QElemType e)
{//插入元素e为队列的新的队尾元素
QueueRtr p;
p=(QueueRtr)malloc(sizeof(QNode));
if(!p)
exit(0);
p->data=e; //将e赋值给新结点
p->next=NULL; //新结点的指针域为空
Q.irear->next=p; //原队尾结点的指针指向新结点
Q.irear=p; // 尾指针指向新结点
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{//若队列Q不空，删除Q的队头元素，用e返回其值
QueueRtr p;
if(Q.ifront==Q.irear)
return ERROR;
p=Q.ifront->next;//p指向队头
e=p->data; //赋值
Q.ifront->next=p->next;//头节点指向下一个结点
if(Q.irear==p) //s删除的是队尾结点
Q.irear=Q.ifront;
free(p);
return OK;
}
void QueueTraverse(LinkQueue &Q)
{
QueueRtr p=Q.ifront->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
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); //出队，队列元素赋值给a；
if(a->data==s) //a所指的结点的值为s
{
DestroyQueue(q);//销毁队列s
return a;
}
if(a->lchild) //有左孩子
EnQueue(q,a->lchild); //入队左孩子
if(a->rchild) //有右孩子
EnQueue(q,a->rchild); //入队右孩子
}
DestroyQueue(q); //销毁队列q;
}
return NULL; //二叉树中没有元素值为s的结点
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子，若e无左孩子，则返回空
BiTree a;
if(T) //非空树
{
a=Point(T,e); //a是指向结点e的指针;
if(a&&a->lchild) //T中存在结点e且e存在左孩子
return a->lchild->data; //返回e的左孩子的值
}
return 0;
}
TElemType RightChild(BiTree T,TElemType e)
{//返回e的右孩子，若e无右孩子，则返回空
BiTree a;
if(T) //非空树
{
a=Point(T,e); //a是指向结点e的指针;
if(a&&a->rchild) //T中存在结点e且e存在右孩子
return a->rchild->data; //返回e的右孩子的值
}
return 0;
}
Status DeleteChild(BiTree p,int LR)
{//根据LR为0或1,p删除T中所指结点的左右子树
if(p) //p不为空
{
if(LR==0)//删除左子树
DestroyBiTree(p->lchild); //清空p所指结点的左子树
else if(LR==1)//删除右子树
DestroyBiTree(p->rchild); //清空p所指结点的右子树
return OK;
}
return ERROR;
}
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)//先序递归遍历T
{
if(T)
{
printf("%d",T->data); //先访问根节点
PreOrderTraverse(T->lchild); //再先序遍历左子树
PreOrderTraverse(T->rchild); //最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T)//中序递归遍历T
{
if(T)
{
InOrderTraverse(T->lchild); //先遍历左子树
printf("%d",T->data); //在访问根节点
InOrderTraverse(T->rchild); //最后遍历右子树
}
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild); //先遍历左子树
PostOrderTraverse(T->rchild); //再遍历右子树
printf("%d",T->data); //在访问根节点
}
}
Status BiTreeEmpty(BiTree T)
{
if(T)
return FLASE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;//树的深度为0
i=BiTreeDepth(T->lchild); //i为左子树的深度
j=BiTreeDepth(T->rchild); //j为右子树的深度
return i>j?i+1:j+1; //T的深度为其左右子树的深度中的大者+1
}
TElemType Root(BiTree T)//返回T的根
{
if(BiTreeEmpty(T)) //二叉树为空
return 0;
else
return T->data;
}
TElemType Value(BiTree p) //二叉树T存在，p指向T中的某个结点，结果返回p所指的结点
{
return p->data;
}
void Assign(BiTree p,TElemType value)
{
p->data=value;
}
void CreateBiTree(BiTree &T) //按照先序次序输入二叉树中结点的值
{
TElemType ch;
scanf("%d",&ch);
if(ch==0) //当输入的值为0的时候结点的值为空
T=NULL;
else //结点值不为空
{
T=(BiTree)malloc(sizeof(BiTNode)); //生成根节点
if(!T)
exit(0);
T->data=ch;
CreateBiTree(T->lchild); //递归构造左子树
CreateBiTree(T->rchild); //递归构造右子树
}
}
void LeveOrderTraverse(BiTree T)
{//层序遍历T
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T); //根指针入队
while(!QueueEmpty(q)) //队列不空
{
DeQueue(q,a); //出队元素指针，赋给a
printf("%d",a->data);
if(a->lchild!=NULL) //a有左孩子
EnQueue(q,a->lchild); //入队a的左孩子
if(a->rchild!=NULL) //a有右孩子
EnQueue(q,a->rchild); //入队a的右孩子
}
printf("\n");
DestroyQueue(q);
}
}
TElemType Parent(BiTree T,TElemType e)
{//若e是T的非根节点，则返回他的双亲，否则返回空
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))
return a->data; //返回e的双亲的值
else//若未找到e,则入队其左右孩子指针(如果非空)
{
if(a->lchild) //a有左孩子
EnQueue(q,a->lchild); //入队左孩子指针
else if(a->rchild)
EnQueue(q,a->rchild);
}
}
}
return 0;
}
TElemType LeftSibling(BiTree T,TElemType e)
{//返回e的左兄弟，若e是T的左孩子或无左兄弟，返回空
TElemType a;
BiTree p;
if(T)
{
a=Parent(T,e); //a为e的双亲
if(a!=0) //找到e的双亲
{
p=Point(T,a);//p为指向结点a的指针
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子且右孩子是e
return p->lchild->data; //返回p的左孩子
}
}
return 0;
}
TElemType RightSibling(BiTree T,TElemType e)
{//返回e的右兄弟，若e是T的右孩子或无右兄弟，返回空
TElemType a;
BiTree p;
if(T)
{
a=Parent(T,e); //a为e的双亲
if(a!=0) //找到e的双亲
{
p=Point(T,a);//p为指向结点a的指针
if(p->lchild&&p->rchild&&p->lchild->data==e)//p存在左右孩子且右孩子是e
return p->rchild->data; //返回p的左孩子
}
}
return 0;
}
Status InsertChild(BiTree p,int LR,BiTree c)
{//LR为0或1，插入c为T中所指结点的左或右子树，p所指结点的原有左或右子树则成为C的右子树
if(p)
{
if(LR==0)//把二叉树c插为p所指向结点的左子树
{
c->rchild=p->lchild;//p所指向的原有左子树成为C的右子树
p->lchild=c;//二叉树c成为p的左子树
}
else//把二叉树c插为p所指结点的右子树
{
c->rchild=p->rchild;//p所指结点的原有右子树成为c的右子树
p->rchild=c;//二叉树c成为p的右子树
}
return OK;
}
return ERROR;
}
int main()
{
int i;
BiTree T;
TElemType e1;
InitBiTree(T); //初始化二叉树T
printf("构造二叉树后,树是否为空?%d(1:是 0:否) 树的深度%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
if(e1!=0)
printf("二叉树的根是%d\n",e1);
else
printf("无根\n");
CreateBiTree(T);
printf("建立二叉树后,树是否为空?%d(1:是 0:否) 树的深度\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
if(e1!=0)
printf("二叉树的根是%d\n",e1);
else
printf("无根\n");
printf("先序遍历递归二叉树:\n");
PreOrderTraverse(T); printf("\n");
printf("中序遍历递归二叉树:\n");
InOrderTraverse(T); printf("\n");
printf("后序遍历递归二叉树:\n");
PostOrderTraverse(T); printf("\n");
}
