《二叉树的基本操作与应用,完整版》由会员分享，可在线阅读，更多相关《二叉树的基本操作与应用,完整版（39页珍藏版）》请在金锄头文库上搜索。
1、#include stdio.h#include stdlib.h#include string.h#include math.htypedef char TElemType; /定义结点数据为字符型typedef int Status; /定义函数类型为 int 型#define ERROR 0#define OK 1typedef struct BiTNode /定义结构体TElemType data; /结点数值struct BiTNode *lchild; /左孩子指针struct BiTNode *rchild; /右孩子指针struct BiTNode *next; /下一结点指针
2、BiTNode, *BiTree;Status NumJudge(char ch20)/限制输入数据必须为大于零的整形char ch120;int num;while(1)scanf(%s,ch); num=atoi(ch); /将字符串转换为整型itoa(num,ch1,10); /将整型转换为字符串型if(strcmp(ch,ch1)=0&num0)break;elseprintf(请输入一个大于零的整数: );return num;/NumJudgeStatus InitBiTree(BiTree &T)/构造空二叉树 Tif(!(T=(BiTree)malloc(sizeof(BiTN
3、ode)exit(ERROR); /若申请空间失败则退出T-next=NULL;printf(nt 空二叉树构建成功!nn);return OK;/InitBiTreeStatus DestroyTree(BiTree &T,BiTree t)/销毁二叉树if(T)free(T);T=NULL;printf(t 二叉树销毁成功!n);if(t)DestroyTree(T,t-lchild); DestroyTree(T,t-rchild);free(t); return OK;/DestroyTreeStatus ClearBiTree(BiTree &T,int sum,int &i)/清空
4、二叉树if(T)ClearBiTree(T-lchild,sum,i);ClearBiTree(T-rchild,sum,i);free(T);i+; if(i=sum)printf(t 二叉树清空成功!n);T=NULL;return OK;/ClearBiTreeStatus CreateBiTree(BiTree &T,int i,int j,TElemType ch)/按先序次序输入二叉树中结点的值(一个字符),空格字符表示该结点为空/构造二叉链表示的二叉树 TTElemType ch1;int k;char str20;if(i=0)printf(n 按先序顺序建立二叉树:请按提示输
5、入相应的数据(一个字符)，若提示结点数值为空，n 请输入空格nn);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;k1)printf(%5s 您只能输入一个字符: , );ch1=str0; /获取输入的准确字符型数据if(ch1= )T=NULL;return ERROR; /输入空格则为根结点为空if(ch1!= )if(!(
6、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;return OK;/CreateBitreeStatus TreeDepth(BiTree T,int l,int &h) /若二叉树存在,返回其深度if(T)l=l+1; if(lh)h=l; TreeDepth(T-lchild,l,h); TreeDepth(T
7、-rchild,l,h);return h;/TreeDepthStatus GetRootElem(BiTree T)/获取根结点值printf(该二叉树的根结点值为: %cnn,T-data);return OK;/GetRootElemStatus SaveElem(BiTree T,BiTree *Q,int i)/根据完全二叉树中，若本节点位置序号为 i,则其左孩子结点为 2i,右孩子为 2i+1 的方法/保存二叉树的有效结点至指针数组 Q 特定的位置if(T)Qi=T;SaveElem(T-lchild,Q,2*i);SaveElem(T-rchild,Q,2*i+1);retur
8、n OK;/SaveElemStatus Lev_Traverse(BiTree T,int h)/按层次从上到下,每层从左到右的顺序显示树状二叉树if(T=NULL)printf(ntt 二叉树目前为空树nn);return ERROR;BiTree *Q;if(!(Q=(BiTree *)malloc(int(pow(2,h)+1) * sizeof(BiTNode)exit(ERROR);int i,j,n=1,k=h;for(i=1;idata);if(!Qi)printf( );for(j=0;jdata); /访问 TFirstPrint(T-lchild,i); /递归遍历左子树
9、FirstPrint(T-rchild,i); /递归遍历右子树i=0;return OK;/FirstPrintBiTreeStatus MiddlePrint(BiTree T,int i)/按中序次序( 递归) 访问二叉树if(i=0)printf(n 中序(递归)遍历结果如下:n);if(T)i+;MiddlePrint(T-lchild,i); /递归遍历左子树printf(%-5c,T-data); /访问 TMiddlePrint(T-rchild,i); /递归遍历右子树i=0;return OK;/MiddlePrintStatus LastPrint(BiTree T,in
10、t i)/按后序次序( 递归) 访问二叉树if(i=0)printf(n 后序(递归)遍历结果如下:n);if(T)i+;LastPrint(T-lchild,i); /递归遍历左子树LastPrint(T-rchild,i); /递归遍历右子树printf(%-5c,T-data); /访问 Ti=0;return OK;/LastPrintStatus PreOrderTraverse(BiTree T) /按先序(非递归 )遍历二叉树 TBiTree p,S,q;int flag=0;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S-n
11、ext=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;elsebreak;while(1) /栈顶指针出栈,如果当前栈顶指针的右孩子存在则跳出循环p=S-next;S-next=p-next; if(!S-next&!p-rchild)flag=1;break; /如果栈空并且当前结点右孩子不存在则遍历结束if(p-rch
12、ild)p=p-rchild;break;if(flag=1)break;printf(nn);return OK;/PreOrderTraverseStatus InOrderTraverse(BiTree T) / 中序遍历(非递归 )二叉树 TBiTree p,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; /左孩子
13、进栈elsep=S-next;S-next=p-next; if(p)printf(%-5c,p-data); /输出栈中元素elsereturn ERROR;p=p-rchild;printf(nn);return OK;/InOrderTraverseStatus PostOrderTraverse(BiTree T) /后序遍历(非递归 )二叉树 TBiTree p,S,q;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S-next=NULL; /建立空栈 Sp=T;printf(n 后序(非递归)遍历结果如下:n);while(1)w
14、hile(1) /遍历左子树 ,若当前结点左右孩子都不存在则跳出q=S-next;S-next=p;p-next=q; /当前结点进栈if(p-lchild)p=p-lchild; elseif(p-rchild)p=p-rchild;elsebreak;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; /若当前结点为栈顶指针的右孩子,则继续出栈elseif(S-next-rchild) /栈顶指针右孩存在, 指针移
