此程序功能比课程设计要求的要多，可作为复习资料，测试用原始二叉树如左图，共有两次运行结果截图，每次所删除的子树不同，务必自行分析各步结果得到的过程.注意最初输入时含有的空格数(abc空d空空空ef空空g空h空空),附录中含有源码，务必认真阅读！
//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE -2
#define NULL 0
typedef int Status;
//以下为二叉树的类型定义及创建、销毁、遍历、求树深、求结点数、叶结点数、复制、左右互换、查找、定位双亲、删除、凹式输出等操作实现--------
//树中元素类型定义与二叉链表存储结构定义
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T){//先序创建二叉树各结点，注意输入时空指针不要丢
TElemType e;
scanf("%c",&e);
if(e==' ')T=NULL;
else{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)exit(OVERFLOW);
T->data=e;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status DestroyBiTree(BiTree &T)//销毁以T为根结点的树，注意T各子孙结点也要释放
{
if(T){
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
free(T);
T=NULL;
}
return OK;
}
int TreeDepth(BiTree T){
int d,d1,d2;
if(T==NULL)d=0;
else
{
d1=TreeDepth(T->lchild);
d2=TreeDepth(T->rchild);
d=d1>=d2?d1+1:d2+1;
}
return d;
}
int NodeCount(BiTree T){
//递归法统计所有结点的个数
int n;
if(T==NULL)n=0;
else n=1+NodeCount(T->lchild)+NodeCount(T->rchild);
return n;
}
int LeafCount(BiTree T){
//递归法统计叶子结点的个数
int n;
if(T==NULL)n=0;
else if(T->lchild==NULL&&T->rchild==NULL)n=1;
else n=LeafCount(T->lchild)+LeafCount(T->rchild);
return n;
}
Status PrintTElem(TElemType e){
printf("%c",e);
return OK;
}
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType))
{
if(T){
(*visit)(T->data);
PreOrderTraverse(T->lchild,(*visit));
PreOrderTraverse(T->rchild,(*visit));
}
return OK;
}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{
if(T){
InOrderTraverse(T->lchild,(*visit));
(*visit)(T->data);
InOrderTraverse(T->rchild,(*visit));
}
return OK;
}
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType))
{
if(T){
PostOrderTraverse(T->lchild,(*visit));
PostOrderTraverse(T->rchild,(*visit));
(*visit)(T->data);
}
return OK;
}
int PreOrder_LeafCount(BiTree T,int &count){
//基于先序遍历求叶结点数，count用作计数器,初值为。函数返回值为叶结点数。实际将先序遍历过程中的visit函数变为判断当前结点是否为叶子节点、是则加的操作即可
if(!T)return count;
else{
if(!T->lchild&&!T->rchild)++count;
PreOrder_LeafCount(T->lchild,count);
PreOrder_LeafCount(T->rchild,count);
return count;
}
}
Status CopyBiTree(BiTree T,BiTree &X){//复制树T得到树X，T保持不变
if(!T)X=NULL;
else{
X=(BiTree)malloc(sizeof(BiTNode));
if(!X)exit(OVERFLOW);
X->data=T->data;
CopyBiTree(T->lchild,X->lchild);
CopyBiTree(T->rchild,X->rchild);
}
return OK;
}
Status ExchangeBiTree(BiTree &T){//将树T各结点的左右孩子互换
BiTree temp;
if(T){
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
ExchangeBiTree(T->lchild);
ExchangeBiTree(T->rchild);
}
return OK;
}
Status LocateNode(BiTree T,TElemType x,BiTree &p){
//在树T中查找(按先序)第一个结点值等于x的结点，若找到则函数返回ＴＲＵＥ,p带回该结点的地址;若找不到则函数返回ＦＡＬＳＥ ，p赋值为NULL
if(!T){ p=NULL;return FALSE;}//树T为空则p赋空且返回FALSE
else if(T->data==x){p=T;return TRUE;}
else {
if(LocateNode(T->lchild,x,p))return TRUE;//搜索左子树
else if(LocateNode(T->rchild,x,p))return TRUE;//左子树中找不到再搜索右子树
else {p=NULL;return FALSE; }
}
}
Status LocateParent(BiTree T,TElemType x,BiTree &parent_p,int &LR){
//已知树T中存在某结点值等于x，定位到该结点的双亲结点,若双亲存在（说明x结点非根结点）则parent_p带回双亲位置，flag为代表是双亲的左孩子，为代表是双亲的右孩子，同时函数返回ＴＲＵＥ；否则函数返回FALSE
if(T->data==x){parent_p=NULL;return FALSE;}//值等于x的结点是根结点，无双亲
else{
if(T->lchild!=NULL&&T->lchild->data==x){parent_p=T;LR=0;return TRUE;}
else if(T->rchild!=NULL&&T->rchild->data==x){parent_p=T;LR=1;return TRUE;}
else{
if(T->lchild!=NULL&&LocateParent(T->lchild,x,parent_p,LR))return TRUE;
else if(T->rchild!=NULL&&LocateParent(T->rchild,x,parent_p,LR))return TRUE;
else {parent_p=NULL;return FALSE;}
}
}
}
Status DeleteChild(BiTree &T,TElemType x){
//删除树T中以x为根结点的子树,若存在x结点则删除成功后返回OK，若不存在x结点返回ERROR;
BiTNode *p,*parent_p;
int LR;
if(LocateNode(T,x,p)){//若树中存在结点x
if(LocateParent(T,x,parent_p,LR)){//若存在双亲，即x非根结点
if(LR==0)DestroyBiTree(parent_p->lchild);
else if(LR==1)DestroyBiTree(parent_p->rchild);
}
else DestroyBiTree(T);//若x为根结点，不存在双亲,则删除整颗树，不可直接写T=NULL，为何？
return OK;
}
else
return ERROR;
}
//-------------------以下为孩子兄弟表示法存储的树或森林的类型定义及树的相关操作实现-------------------------------------
typedef struct CSNode{
TElemType data;
struct CSNode *firstchild;
struct CSNode *nextsibling;
}CSNode,*CSTree;
Status BiTreetoTreeorForest(BiTree BiT,CSTree &T){
//根据已经存在的二叉树BiT转换得到孩子兄弟法表示的树或者森林T，原二叉树BiT保持不变。注意思考何时得到树，何时得到森林
if(BiT==NULL)T=NULL;
else{
T=(CSTree)malloc(sizeof(CSNode));
if(!T)exit(OVERFLOW);
T->data=BiT->data;
BiTreetoTreeorForest(BiT->lchild,T->firstchild);
BiTreetoTreeorForest(BiT->rchild,T->nextsibling);
}
return OK;
}
Status PostRootTraverse(CSTree T,Status (*visit)(TElemType)){
//后根序遍历树T(对森林则是中序遍历），相当于中序遍历二叉链表存储结构
if(T){
PostRootTraverse(T->firstchild,(*visit));
(*visit)(T->data);
PostRootTraverse(T->nextsibling,(*visit));
}
return OK;
}
int TreeorForestDepth(CSTree T){//求树或森林的深度
int d,d1,d2;
if(!T)d=0;
else{
d1=TreeorForestDepth(T->firstchild);
d2=TreeorForestDepth(T->nextsibling);
d=(d1+1)>d2?d1+1:d2;
}
return d;
}
void PrintBiTree(BiTree T,int level){
//仿照题集题凹式打印树的形式打印二叉树
//注意是逐行打印,采用先序,凹入深度由结点所在层次控制,根结点位于第层，故最初level为
if(T){
//先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(level-1)*4个空格
for(int i=1;i<=level-1;++i)printf(" ");
printf("%c\n",T->data);
PrintBiTree(T->lchild,level+1);
PrintBiTree(T->rchild,level+1);
}
}
void PrintTree(CSTree T,int level){
//按题集题凹式打印树
//注意是逐行打印,采用先根序,凹入深度由结点所在层次控制,根结点位于第层，故最初level为
if(T){
//先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(level-1)*4个空格
for(int i=1;i<=level-1;++i)printf(" ");
printf("%c\n",T->data);
PrintTree(T->firstchild,level+1);
PrintTree(T->nextsibling,level);
}
}
//以下非课程设计要求部分，可作复习用//
//------非递归实现树的遍历时需用到栈，故此处将顺序栈的定义及实现复制过来，不过栈元素类型需改变为指向树的结点的指针类型BiTree---
//元素类型与顺序栈类型声明
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef BiTree ElemType;//BiTree等同于BiTNode*，说明栈中的元素类型为指向树中结点的指针类型
typedef struct{
ElemType * base;
ElemType * top;
int stacksize;
}SqStack;
//顺序栈基本操作及其实现
Status InitStack(SqStack &S){
//初始化一个顺序栈用S带回
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack &S){
//销毁一个顺序栈
free(S.base);
S.base=NULL;
S.top=NULL;
S.stacksize=0;
return OK;
}
Status ClearStack(SqStack &S){
//将一个顺序栈置空
S.top=S.base;
return OK;
}
Status Push(SqStack &S,ElemType e){
//向栈顶压入一个新元素
if((S.top-S.base)==S.stacksize){ //当前栈满则重新为栈分配空间
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e){
//栈顶元素出栈并用e带回其值
if(S.top==S.base)return ERROR;
e=*(S.top-1);
--S.top;
return OK;
}
Status SetTopElem(SqStack &S,ElemType e){
//将栈顶元素的值修改为e，书中未设此操作，可根据需要新设
if(S.top==S.base)return ERROR;
*(S.top-1)=e;
return OK;
}
Status StackEmpty(SqStack S){
//栈空则返回TRUE,否则返回FALSE
if(S.top==S.base)return TRUE;
else return FALSE;
}
int StackLength(SqStack S){
//返回栈中元素的个数
return(S.top-S.base);
}
Status GetTop(SqStack S,ElemType &e){
//用e带回栈顶元素的值
if(S.top==S.base)return ERROR;
e=*(S.top-1);
return OK;
}
Status PrintElem(ElemType e){
//用于输出一个元素，根据元素类型的不同，此函数需适时改变
printf("%c",e->data);
return OK;
}
Status StackTraverse(SqStack S,Status (*visit)(ElemType)){
//从栈底元素到栈顶元素依次执行visit函数，通常用于输出栈中元素
ElemType *p=S.base;
if(S.base==S.top)printf("空栈\n");
else
while(p<S.top){(*visit)(*p);++p;}
return OK;
}
Status InOrderTraverse_NonRecur_1(BiTree T,Status (*visit)(ElemType)){
//本问题共两种求解思路,此为第一种
//何时递归:根结点不空时递归访问左子树(因还要回来访问根结点，故根结点入栈,左孩子成为新根结点)
//何时不递归:左子树空时栈顶根结点出栈访问，并将右孩子入栈
//结束：当前访问结点为空且栈中无元素时遍历毕
SqStack S; InitStack(S); BiTNode* p=T;
while(p||!StackEmpty(S)){
while(p){
Push(S,p);
p=p->lchild;
}
Pop(S,p);
(*visit)(p);
p=p->rchild;
}
return OK;
}
Status InOrderTraverse_NonRecur_2(BiTree T,Status (*visit)(ElemType)){
//非递归中序遍历二叉树T
//何时递归:根结点不空时将左孩子入栈作新根结点,
//何时不递归:根结点为空时不递归，此后当前空根结点出栈，访问下一个栈顶元素并将其右孩子结点入栈
//当栈中不含元素时整个树遍历完毕
SqStack S;
InitStack(S);
BiTNode* p; //实际BiTree与BiTNode*等价，具体根据上下文含义确定用谁，如根结点可声明为BiTree类型，指向结点的指针可声明为BiTNode*类型
if(!T){printf("空树");return ERROR;}
else{
Push(S,T);
while(!StackEmpty(S)){
while( GetTop(S,p)&&p)Push(S,p->lchild);//p的左孩子入栈，直到入栈元素为空指针，此循环后栈顶元素为NULL，相当于走到左子树外
Pop(S,p);//左子树是空树，对应的空指针出栈，下一步将访问根结点
if(!StackEmpty(S)){ //若栈中尚有元素代表未遍历完,下面访问栈顶根结点，之后栈顶跟结点的右孩子入栈
Pop(S,p);
(*visit)(p);
Push(S,p->rchild);
}
}
return OK;
}
}
void main()
{
BiTree BiT;
CreateBiTree(BiT);
printf("二叉树BiT的先序输出序列为：");
PreOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("二叉树BiT的中序输出为：");
InOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("二叉树BiT后序输出为：");
PostOrderTraverse(BiT,PrintTElem);
printf("\n\n");
printf("二叉树BiT树深：%d\n",TreeDepth(BiT));
printf("二叉树BiT结点总数：%d\n",NodeCount(BiT));
printf("递归求得二叉树BiT叶子结点数为：%d\n",LeafCount(BiT));
int count=0;
printf("基于先序遍历求二叉树BiT叶子结点数为:%d\n\n",PreOrder_LeafCount(BiT,count));
TElemType x;
BiTree p,parent_p; //BiTree等价于BiTNode *
int LR;
printf("输入要查找的元素,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
if(LocateNode(BiT,x,p)==TRUE){
printf("元素%c在BiT中，",p->data);
if(LocateParent(BiT,x,parent_p,LR)){
printf("%c结点的双亲结点为%c，",x,parent_p->data);
if(LR==0)printf("是双亲的左孩子\n");
else printf("是双亲的右孩子\n");
}
else printf("%c结点是树的根结点，不存在双亲结点\n");
}
else {printf("元素%c不在BiT中\n",x);}
printf("\n");
printf("下面重新读入x并删除以x为根的子树\n");
printf("输入x,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
if(DeleteChild(BiT,x)==ERROR)printf("x不存在\n");
printf("删除BiT中以x为根的子树后BiT的先序输出序列为：");
PreOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("删除BiT中以x为根的子树后BiT的中序输出序列为：");
InOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("删除BiT中以x为根的子树后BiT的后序输出序列为：");
PostOrderTraverse(BiT,PrintTElem);
printf("\n\n");
CSTree T;
printf("以下根据二叉树BiT构造相应的孩子兄弟法存储的树或森林T.\n");
printf("源二叉树凹式输出为：\n");
PrintBiTree(BiT,1);
BiTreetoTreeorForest(BiT,T);
printf("由源二叉树转换得到的树或森林为：\n");
PrintTree(T,1);
printf("构造好的树的后跟输出序列或森林的中序输出序列为:");
PostRootTraverse(T,PrintTElem);
printf("\n");
printf("构造好的树的深度为:%d\n\n",TreeorForestDepth(T));
BiTree X;
printf("以下先复制BiT得到X，后将树X的各结点的左右孩子互换:\n");
CopyBiTree(BiT,X);
ExchangeBiTree(X);
printf("互换完毕，以下进行结果测试：\n");
printf("X先序输出为：");
PreOrderTraverse(X,PrintTElem);
printf("\n");
printf("X中序输出为：");
InOrderTraverse(X,PrintTElem);
printf("\n");
printf("X后序输出为：");
PostOrderTraverse(X,PrintTElem);
printf("\n");
printf("X树深：%d\n",TreeDepth(X));
printf("X结点总数：%d\n",NodeCount(X));
printf("递归求得X叶子结点数为：%d\n",LeafCount(X));
printf("非递归第一种方法中序遍历树BiT得:");
InOrderTraverse_NonRecur_1(BiT,PrintElem);
printf("\n");
printf("非递归第二种方法中序遍历树BiT得:");
InOrderTraverse_NonRecur_2(BiT,PrintElem);
printf("\n\n");
DestroyBiTree(BiT);
printf("销毁后的树先序输出为：\n");
PreOrderTraverse(BiT,PrintTElem);
printf("销毁后树深%d\n",TreeDepth(BiT));
printf("递归求结点总数：%d\n",NodeCount(BiT));
count=0;
printf("基于先序遍历求二叉树BiT叶子结点数为:%d\n\n",PreOrder_LeafCount(BiT,count));
printf("销毁后叶结点数%d\n",LeafCount(BiT));
}
//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE -2
#define NULL 0
typedef int Status;
//以下为二叉树的类型定义及创建、销毁、遍历、求树深、求结点数、叶结点数、复制、左右互换、查找、定位双亲、删除、凹式输出等操作实现--------
//树中元素类型定义与二叉链表存储结构定义
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T){//先序创建二叉树各结点，注意输入时空指针不要丢
TElemType e;
scanf("%c",&e);
if(e==' ')T=NULL;
else{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)exit(OVERFLOW);
T->data=e;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status DestroyBiTree(BiTree &T)//销毁以T为根结点的树，注意T各子孙结点也要释放
{
if(T){
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
free(T);
T=NULL;
}
return OK;
}
int TreeDepth(BiTree T){
int d,d1,d2;
if(T==NULL)d=0;
else
{
d1=TreeDepth(T->lchild);
d2=TreeDepth(T->rchild);
d=d1>=d2?d1+1:d2+1;
}
return d;
}
int NodeCount(BiTree T){
//递归法统计所有结点的个数
int n;
if(T==NULL)n=0;
else n=1+NodeCount(T->lchild)+NodeCount(T->rchild);
return n;
}
int LeafCount(BiTree T){
//递归法统计叶子结点的个数
int n;
if(T==NULL)n=0;
else if(T->lchild==NULL&&T->rchild==NULL)n=1;
else n=LeafCount(T->lchild)+LeafCount(T->rchild);
return n;
}
Status PrintTElem(TElemType e){
printf("%c",e);
return OK;
}
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType))
{
if(T){
(*visit)(T->data);
PreOrderTraverse(T->lchild,(*visit));
PreOrderTraverse(T->rchild,(*visit));
}
return OK;
}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{
if(T){
InOrderTraverse(T->lchild,(*visit));
(*visit)(T->data);
InOrderTraverse(T->rchild,(*visit));
}
return OK;
}
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType))
{
if(T){
PostOrderTraverse(T->lchild,(*visit));
PostOrderTraverse(T->rchild,(*visit));
(*visit)(T->data);
}
return OK;
}
int PreOrder_LeafCount(BiTree T,int &count){
//基于先序遍历求叶结点数，count用作计数器,初值为。函数返回值为叶结点数。实际将先序遍历过程中的visit函数变为判断当前结点是否为叶子节点、是则加的操作即可
if(!T)return count;
else{
if(!T->lchild&&!T->rchild)++count;
PreOrder_LeafCount(T->lchild,count);
PreOrder_LeafCount(T->rchild,count);
return count;
}
}
Status CopyBiTree(BiTree T,BiTree &X){//复制树T得到树X，T保持不变
if(!T)X=NULL;
else{
X=(BiTree)malloc(sizeof(BiTNode));
if(!X)exit(OVERFLOW);
X->data=T->data;
CopyBiTree(T->lchild,X->lchild);
CopyBiTree(T->rchild,X->rchild);
}
return OK;
}
Status ExchangeBiTree(BiTree &T){//将树T各结点的左右孩子互换
BiTree temp;
if(T){
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
ExchangeBiTree(T->lchild);
ExchangeBiTree(T->rchild);
}
return OK;
}
Status LocateNode(BiTree T,TElemType x,BiTree &p){
//在树T中查找(按先序)第一个结点值等于x的结点，若找到则函数返回ＴＲＵＥ,p带回该结点的地址;若找不到则函数返回ＦＡＬＳＥ ，p赋值为NULL
if(!T){ p=NULL;return FALSE;}//树T为空则p赋空且返回FALSE
else if(T->data==x){p=T;return TRUE;}
else {
if(LocateNode(T->lchild,x,p))return TRUE;//搜索左子树
else if(LocateNode(T->rchild,x,p))return TRUE;//左子树中找不到再搜索右子树
else {p=NULL;return FALSE; }
}
}
Status LocateParent(BiTree T,TElemType x,BiTree &parent_p,int &LR){
//已知树T中存在某结点值等于x，定位到该结点的双亲结点,若双亲存在（说明x结点非根结点）则parent_p带回双亲位置，flag为代表是双亲的左孩子，为代表是双亲的右孩子，同时函数返回ＴＲＵＥ；否则函数返回FALSE
if(T->data==x){parent_p=NULL;return FALSE;}//值等于x的结点是根结点，无双亲
else{
if(T->lchild!=NULL&&T->lchild->data==x){parent_p=T;LR=0;return TRUE;}
else if(T->rchild!=NULL&&T->rchild->data==x){parent_p=T;LR=1;return TRUE;}
else{
if(T->lchild!=NULL&&LocateParent(T->lchild,x,parent_p,LR))return TRUE;
else if(T->rchild!=NULL&&LocateParent(T->rchild,x,parent_p,LR))return TRUE;
else {parent_p=NULL;return FALSE;}
}
}
}
Status DeleteChild(BiTree &T,TElemType x){
//删除树T中以x为根结点的子树,若存在x结点则删除成功后返回OK，若不存在x结点返回ERROR;
BiTNode *p,*parent_p;
int LR;
if(LocateNode(T,x,p)){//若树中存在结点x
if(LocateParent(T,x,parent_p,LR)){//若存在双亲，即x非根结点
if(LR==0)DestroyBiTree(parent_p->lchild);
else if(LR==1)DestroyBiTree(parent_p->rchild);
}
else DestroyBiTree(T);//若x为根结点，不存在双亲,则删除整颗树，不可直接写T=NULL，为何？
return OK;
}
else
return ERROR;
}
//-------------------以下为孩子兄弟表示法存储的树或森林的类型定义及树的相关操作实现-------------------------------------
typedef struct CSNode{
TElemType data;
struct CSNode *firstchild;
struct CSNode *nextsibling;
}CSNode,*CSTree;
Status BiTreetoTreeorForest(BiTree BiT,CSTree &T){
//根据已经存在的二叉树BiT转换得到孩子兄弟法表示的树或者森林T，原二叉树BiT保持不变。注意思考何时得到树，何时得到森林
if(BiT==NULL)T=NULL;
else{
T=(CSTree)malloc(sizeof(CSNode));
if(!T)exit(OVERFLOW);
T->data=BiT->data;
BiTreetoTreeorForest(BiT->lchild,T->firstchild);
BiTreetoTreeorForest(BiT->rchild,T->nextsibling);
}
return OK;
}
Status PostRootTraverse(CSTree T,Status (*visit)(TElemType)){
//后根序遍历树T(对森林则是中序遍历），相当于中序遍历二叉链表存储结构
if(T){
PostRootTraverse(T->firstchild,(*visit));
(*visit)(T->data);
PostRootTraverse(T->nextsibling,(*visit));
}
return OK;
}
int TreeorForestDepth(CSTree T){//求树或森林的深度
int d,d1,d2;
if(!T)d=0;
else{
d1=TreeorForestDepth(T->firstchild);
d2=TreeorForestDepth(T->nextsibling);
d=(d1+1)>d2?d1+1:d2;
}
return d;
}
void PrintBiTree(BiTree T,int level){
//仿照题集题凹式打印树的形式打印二叉树
//注意是逐行打印,采用先序,凹入深度由结点所在层次控制,根结点位于第层，故最初level为
if(T){
//先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(level-1)*4个空格
for(int i=1;i<=level-1;++i)printf(" ");
printf("%c\n",T->data);
PrintBiTree(T->lchild,level+1);
PrintBiTree(T->rchild,level+1);
}
}
void PrintTree(CSTree T,int level){
//按题集题凹式打印树
//注意是逐行打印,采用先根序,凹入深度由结点所在层次控制,根结点位于第层，故最初level为
if(T){
//先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(level-1)*4个空格
for(int i=1;i<=level-1;++i)printf(" ");
printf("%c\n",T->data);
PrintTree(T->firstchild,level+1);
PrintTree(T->nextsibling,level);
}
}
//以下非课程设计要求部分，可作复习用//
//------非递归实现树的遍历时需用到栈，故此处将顺序栈的定义及实现复制过来，不过栈元素类型需改变为指向树的结点的指针类型BiTree---
//元素类型与顺序栈类型声明
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef BiTree ElemType;//BiTree等同于BiTNode*，说明栈中的元素类型为指向树中结点的指针类型
typedef struct{
ElemType * base;
ElemType * top;
int stacksize;
}SqStack;
//顺序栈基本操作及其实现
Status InitStack(SqStack &S){
//初始化一个顺序栈用S带回
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack &S){
//销毁一个顺序栈
free(S.base);
S.base=NULL;
S.top=NULL;
S.stacksize=0;
return OK;
}
Status ClearStack(SqStack &S){
//将一个顺序栈置空
S.top=S.base;
return OK;
}
Status Push(SqStack &S,ElemType e){
//向栈顶压入一个新元素
if((S.top-S.base)==S.stacksize){ //当前栈满则重新为栈分配空间
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e){
//栈顶元素出栈并用e带回其值
if(S.top==S.base)return ERROR;
e=*(S.top-1);
--S.top;
return OK;
}
Status SetTopElem(SqStack &S,ElemType e){
//将栈顶元素的值修改为e，书中未设此操作，可根据需要新设
if(S.top==S.base)return ERROR;
*(S.top-1)=e;
return OK;
}
Status StackEmpty(SqStack S){
//栈空则返回TRUE,否则返回FALSE
if(S.top==S.base)return TRUE;
else return FALSE;
}
int StackLength(SqStack S){
//返回栈中元素的个数
return(S.top-S.base);
}
Status GetTop(SqStack S,ElemType &e){
//用e带回栈顶元素的值
if(S.top==S.base)return ERROR;
e=*(S.top-1);
return OK;
}
Status PrintElem(ElemType e){
//用于输出一个元素，根据元素类型的不同，此函数需适时改变
printf("%c",e->data);
return OK;
}
Status StackTraverse(SqStack S,Status (*visit)(ElemType)){
//从栈底元素到栈顶元素依次执行visit函数，通常用于输出栈中元素
ElemType *p=S.base;
if(S.base==S.top)printf("空栈\n");
else
while(p<S.top){(*visit)(*p);++p;}
return OK;
}
Status InOrderTraverse_NonRecur_1(BiTree T,Status (*visit)(ElemType)){
//本问题共两种求解思路,此为第一种
//何时递归:根结点不空时递归访问左子树(因还要回来访问根结点，故根结点入栈,左孩子成为新根结点)
//何时不递归:左子树空时栈顶根结点出栈访问，并将右孩子入栈
//结束：当前访问结点为空且栈中无元素时遍历毕
SqStack S; InitStack(S); BiTNode* p=T;
while(p||!StackEmpty(S)){
while(p){
Push(S,p);
p=p->lchild;
}
Pop(S,p);
(*visit)(p);
p=p->rchild;
}
return OK;
}
Status InOrderTraverse_NonRecur_2(BiTree T,Status (*visit)(ElemType)){
//非递归中序遍历二叉树T
//何时递归:根结点不空时将左孩子入栈作新根结点,
//何时不递归:根结点为空时不递归，此后当前空根结点出栈，访问下一个栈顶元素并将其右孩子结点入栈
//当栈中不含元素时整个树遍历完毕
SqStack S;
InitStack(S);
BiTNode* p; //实际BiTree与BiTNode*等价，具体根据上下文含义确定用谁，如根结点可声明为BiTree类型，指向结点的指针可声明为BiTNode*类型
if(!T){printf("空树");return ERROR;}
else{
Push(S,T);
while(!StackEmpty(S)){
while( GetTop(S,p)&&p)Push(S,p->lchild);//p的左孩子入栈，直到入栈元素为空指针，此循环后栈顶元素为NULL，相当于走到左子树外
Pop(S,p);//左子树是空树，对应的空指针出栈，下一步将访问根结点
if(!StackEmpty(S)){ //若栈中尚有元素代表未遍历完,下面访问栈顶根结点，之后栈顶跟结点的右孩子入栈
Pop(S,p);
(*visit)(p);
Push(S,p->rchild);
}
}
return OK;
}
}
void main()
{
BiTree BiT;
CreateBiTree(BiT);
printf("二叉树BiT的先序输出序列为：");
PreOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("二叉树BiT的中序输出为：");
InOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("二叉树BiT后序输出为：");
PostOrderTraverse(BiT,PrintTElem);
printf("\n\n");
printf("二叉树BiT树深：%d\n",TreeDepth(BiT));
printf("二叉树BiT结点总数：%d\n",NodeCount(BiT));
printf("递归求得二叉树BiT叶子结点数为：%d\n",LeafCount(BiT));
int count=0;
printf("基于先序遍历求二叉树BiT叶子结点数为:%d\n\n",PreOrder_LeafCount(BiT,count));
TElemType x;
BiTree p,parent_p; //BiTree等价于BiTNode *
int LR;
printf("输入要查找的元素,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
if(LocateNode(BiT,x,p)==TRUE){
printf("元素%c在BiT中，",p->data);
if(LocateParent(BiT,x,parent_p,LR)){
printf("%c结点的双亲结点为%c，",x,parent_p->data);
if(LR==0)printf("是双亲的左孩子\n");
else printf("是双亲的右孩子\n");
}
else printf("%c结点是树的根结点，不存在双亲结点\n");
}
else {printf("元素%c不在BiT中\n",x);}
printf("\n");
printf("下面重新读入x并删除以x为根的子树\n");
printf("输入x,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题
if(DeleteChild(BiT,x)==ERROR)printf("x不存在\n");
printf("删除BiT中以x为根的子树后BiT的先序输出序列为：");
PreOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("删除BiT中以x为根的子树后BiT的中序输出序列为：");
InOrderTraverse(BiT,PrintTElem);
printf("\n");
printf("删除BiT中以x为根的子树后BiT的后序输出序列为：");
PostOrderTraverse(BiT,PrintTElem);
printf("\n\n");
CSTree T;
printf("以下根据二叉树BiT构造相应的孩子兄弟法存储的树或森林T.\n");
printf("源二叉树凹式输出为：\n");
PrintBiTree(BiT,1);
BiTreetoTreeorForest(BiT,T);
printf("由源二叉树转换得到的树或森林为：\n");
PrintTree(T,1);
printf("构造好的树的后跟输出序列或森林的中序输出序列为:");
PostRootTraverse(T,PrintTElem);
printf("\n");
printf("构造好的树的深度为:%d\n\n",TreeorForestDepth(T));
BiTree X;
printf("以下先复制BiT得到X，后将树X的各结点的左右孩子互换:\n");
CopyBiTree(BiT,X);
ExchangeBiTree(X);
printf("互换完毕，以下进行结果测试：\n");
printf("X先序输出为：");
PreOrderTraverse(X,PrintTElem);
printf("\n");
printf("X中序输出为：");
InOrderTraverse(X,PrintTElem);
printf("\n");
printf("X后序输出为：");
PostOrderTraverse(X,PrintTElem);
printf("\n");
printf("X树深：%d\n",TreeDepth(X));
printf("X结点总数：%d\n",NodeCount(X));
printf("递归求得X叶子结点数为：%d\n",LeafCount(X));
printf("非递归第一种方法中序遍历树BiT得:");
InOrderTraverse_NonRecur_1(BiT,PrintElem);
printf("\n");
printf("非递归第二种方法中序遍历树BiT得:");
InOrderTraverse_NonRecur_2(BiT,PrintElem);
printf("\n\n");
DestroyBiTree(BiT);
printf("销毁后的树先序输出为：\n");
PreOrderTraverse(BiT,PrintTElem);
printf("销毁后树深%d\n",TreeDepth(BiT));
printf("递归求结点总数：%d\n",NodeCount(BiT));
count=0;
printf("基于先序遍历求二叉树BiT叶子结点数为:%d\n\n",PreOrder_LeafCount(BiT,count));
printf("销毁后叶结点数%d\n",LeafCount(BiT));
}
