二叉树的基本操作完整版-包含二叉树的所有操作-凡是你想要的都在里面--数据结构版

#includestdio.h#includestdlib.h#includestring.h#includemath.htypedefcharTElemType;//定义结点数据为字符型typedefintStatus;//定义函数类型为int型#defineERROR0#defineOK1typedefstructBiTNode{//定义结构体TElemTypedata;//结点数值structBiTNode*lchild;//左孩子指针structBiTNode*rchild;//右孩子指针structBiTNode*next;//下一结点指针}BiTNode,*BiTree;StatusNumJudge(charch[20]){//限制输入数据必须为大于零的整形charch1[20];intnum;while(1){scanf(%s,ch);num=atoi(ch);//将字符串转换为整型itoa(num,ch1,10);//将整型转换为字符串型if(strcmp(ch,ch1)==0&&num0)break;else{printf(请输入一个大于零的整数:);}}returnnum;}//NumJudgeStatusInitBiTree(BiTree&T){//构造空二叉树Tif(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);//若申请空间失败则退出T-next=NULL;printf(\n\t空二叉树构建成功!\n\n);returnOK;}//InitBiTreeStatusDestroyTree(BiTree&T,BiTreet){//销毁二叉树if(T){free(T);T=NULL;printf(\t二叉树销毁成功!\n);}if(t){DestroyTree(T,t-lchild);DestroyTree(T,t-rchild);free(t);}returnOK;}//DestroyTreeStatusClearBiTree(BiTree&T,intsum,int&i){//清空二叉树if(T){ClearBiTree(T-lchild,sum,i);ClearBiTree(T-rchild,sum,i);free(T);i++;}if(i==sum){printf(\t二叉树清空成功!\n);T=NULL;}returnOK;}//ClearBiTreeStatusCreateBiTree(BiTree&T,inti,intj,TElemTypech){//按先序次序输入二叉树中结点的值(一个字符),空格字符表示该结点为空//构造二叉链表示的二叉树TTElemTypech1;intk;charstr[20];if(i==0){printf(\n按先序顺序建立二叉树:请按提示输入相应的数据(一个字符)，若提示结点数值为空，\n请输入空格\n\n);printf(%5s请输入树根:,);}if(i!=0&&i=j){printf(%5s请输入%c的左孩子:,,ch);}if(j!=0&&ji){printf(%5s请输入%c的右孩子:,,ch);}while(1){//限制输入数据必须为字符型,否则重新输入fflush(stdin);for(k=0;k20;k++){str[k]=getchar();if(str[k]=='\n')break;}if(k==0)printf(%5s请输入一个字符后再按Enter键:,);if(k==1)break;if(k1)printf(%5s您只能输入一个字符:,);}ch1=str[0];//获取输入的准确字符型数据if(ch1==''){T=NULL;returnERROR;}//输入空格则为根结点为空if(ch1!=''){if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);T-data=ch1;//生成根结点ch=T-data;i++;CreateBiTree(T-lchild,i,j,ch);//构造左子树j=i;j++;CreateBiTree(T-rchild,i,j,ch);//构造右子树}i=0;j=0;returnOK;}//CreateBitreeStatusTreeDepth(BiTreeT,intl,int&h){//若二叉树存在,返回其深度if(T){l=l+1;if(lh)h=l;TreeDepth(T-lchild,l,h);TreeDepth(T-rchild,l,h);}returnh;}//TreeDepthStatusGetRootElem(BiTreeT){//获取根结点值printf(该二叉树的根结点值为:%c\n\n,T-data);returnOK;}//GetRootElemStatusSaveElem(BiTreeT,BiTree*Q,inti){//根据完全二叉树中，若本节点位置序号为i,则其左孩子结点为2i,右孩子为2i+1的方法//保存二叉树的有效结点至指针数组Q特定的位置if(T){Q[i]=T;SaveElem(T-lchild,Q,2*i);SaveElem(T-rchild,Q,2*i+1);}returnOK;}//SaveElemStatusLev_Traverse(BiTreeT,inth){//按层次从上到下,每层从左到右的顺序显示树状二叉树if(T==NULL){printf(\n\t\t二叉树目前为空树\n\n);returnERROR;}BiTree*Q;if(!(Q=(BiTree*)malloc(int(pow(2,h)+1)*sizeof(BiTNode))))exit(ERROR);inti,j,n=1,k=h;for(i=1;i=int(pow(2,h)+1);i++){Q[i]=NULL;}SaveElem(T,Q,n);//将目前有效结点按照满二叉树的序号存储printf(提示:规定下图中的有效结点的位置序号从1开始按从上到下,从左到右的顺序依次递增\n);for(i=1;i=(pow(2,h)+1);i++){//树形显示二叉树if(int(pow(2,h))%i==0){printf(\n);printf(\t\t);for(j=0;jpow(2,k-1)-1;j++){printf();}k--;}if(Q[i])printf(%c,Q[i]-data);if(!Q[i])printf();for(j=0;jpow(2,k+1)-1;j++){printf();}}printf(\n\n);i=0;j=0;returnOK;}//Lev_TraverseStatusFirstPrint(BiTreeT,inti){//按先序次序(递归)访问二叉树if(i==0)printf(\n先序(递归)遍历结果如下:\n);if(T){i++;printf(%-5c,T-data);//访问TFirstPrint(T-lchild,i);//递归遍历左子树FirstPrint(T-rchild,i);//递归遍历右子树}i=0;returnOK;}//FirstPrintBiTreeStatusMiddlePrint(BiTreeT,inti){//按中序次序(递归)访问二叉树if(i==0)printf(\n中序(递归)遍历结果如下:\n);if(T){i++;MiddlePrint(T-lchild,i);//递归遍历左子树printf(%-5c,T-data);//访问TMiddlePrint(T-rchild,i);//递归遍历右子树}i=0;returnOK;}//MiddlePrintStatusLastPrint(BiTreeT,inti){//按后序次序(递归)访问二叉树if(i==0)printf(\n后序(递归)遍历结果如下:\n);if(T){i++;LastPrint(T-lchild,i);//递归遍历左子树LastPrint(T-rchild,i);//递归遍历右子树printf(%-5c,T-data);//访问T}i=0;returnOK;}//LastPrintStatusPreOrderTraverse(BiTreeT){//按先序(非递归)遍历二叉树TBiTreep,S,q;intflag=0;if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S-next=NULL;//建立空栈Sp=T;printf(\n先序(非递归)遍历结果如下:\n);while(1){while(1){//遍历存储并访问左子树直到根结点左孩子不存在printf(%-5c,p-data);q=S-next;S-next=p;p-next=q;//当前结点进栈if(p-lchild)p=p-lchild;else{break;}}while(1){//栈顶指针出栈,如果当前栈顶指针的右孩子存在则跳出循环p=S-next;S-next=p-next;if(!S-next&&!p-rchild){flag=1;break;}//如果栈空并且当前结点右孩子不存在则遍历结束if(p-rchild){p=p-rchild;break;}}if(flag==1)break;}printf(\n\n);returnOK;}//PreOrderTraverseStatusInOrderTraverse(BiTreeT){//中序遍历(非递归)二叉树TBiTreep,S,q;if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S-next=NULL;//建立空栈Sp=T;printf(\n中序(非递归)遍历结果如下:\n);while(p||S-next){if(p){q=S-next;S-next=p;p-next=q;p=p-lchild;}//左孩子进栈else{p=S-next;S-next=p-next;if(p)printf(%-5c,p-data);//输出栈中元素else{returnERROR;}p=p-rchild;}}printf(\n\n);returnOK;}//InOrderTraverseStatusPostOrderTraverse(BiTreeT){//后序遍历(非递归)二叉树TBiTreep,S,q;if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S-next=NULL;//建立空栈Sp=T;printf(\n后序(非递归)遍历结果如下:\n);while(1){while(1){//遍历左子树,若当前结点左右孩子都不存在则跳出q=S-next;S-next=p;p-next=q;//当前结点进栈if(p-lchild)p=p-lchild;else{if(p-rchild)p=p-rchild;else{break;}}}while(S-next){p=S-next;S-next=p-next;//栈顶指针出栈并访问printf(%-5c,p-data);if(!S-next)break;//若栈空则跳出if(p==S-next-rchild)p=S-next;//若当前结点为栈顶指针的右孩子,则继续出栈else{if(S-next-rchild){//栈顶指针右孩存在,指针移至栈顶指针的右孩子后跳出循环p=S-next-rchild;break;}}}if(!S-next)break;//若栈空则跳出循环}printf(\n\n);returnOK;}//PostOrderTraverseStatusGetElem