《二叉树的基本操作,包含二叉树的所有操作,凡是你想要的都在里面--数据结构版》由会员分享，可在线阅读，更多相关《二叉树的基本操作,包含二叉树的所有操作,凡是你想要的都在里面--数据结构版（20页珍藏版）》请在金锄头文库上搜索。
1、. . 优选*include stdio.h *include stdlib.h *include string.h *include math.h typedef char TElemType; / 定义结点数据为字符型typedef int Status; / 定义函数类型为int 型*define ERROR 0 *define OK 1 typedef struct BiTNode / 定义构造体TElemType data; / 结点数值struct BiTNode *lchild; / 左孩子指针struct BiTNode *rchild; / 右孩子指针struct BiTNo
2、de *next; / 下一结点指针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; /NumJudge Status InitBiTree(BiTree &T) / 构造空二叉树T
3、if(!(T=(BiTree)malloc(sizeof(BiTNode)exit(ERROR); /假设申请空间失败那么退出T-next=NULL; printf(nt空二叉树构建成功!nn); return OK; /InitBiTree Status 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; /Destro
4、yTree Status ClearBiTree(BiTree &T,int sum,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; return OK; /ClearBiTree Status CreateBiTree(BiTree &T,int i,int j,TElemType ch) / 按先序次序输入二叉树中结点的值(一个字符 ),空格字符表示该结点为空/ 构造二叉链表示的二叉树
5、T TElemType ch1; int k; char str20; if(i=0)printf(n 按先序顺序建立二叉树:请按提示输入相应的数据(一个字符 )， 假设提示结点数值为空，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您只能输入一个字符: , );
6、 ch1=str0; / 获取输入的准确字符型数据if(ch1= )T=NULL;return ERROR; / 输入空格那么为根结点为空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; return OK; /CreateBitree Status Tre
7、eDepth(BiTree T,int l,int &h) / 假设二叉树存在,返回其深度if(T) l=l+1; if(lh)h=l; TreeDepth(T-lchild,l,h); TreeDepth(T-rchild,l,h); return h; /TreeDepth Status GetRootElem(BiTree T) / 获取根结点值printf( 该二叉树的根结点值为: %cnn,T-data); return OK; /GetRootElem Status SaveElem(BiTree T,BiTree *Q,int i) / 根据完全二叉树中，假设本节点位置序号为i,
8、那么其左孩子结点为2i,右孩子为2i+1的方法/ 保存二叉树的有效结点至指针数组Q 特定的位置if(T) Qi=T; SaveElem(T-lchild,Q,2*i); SaveElem(T-rchild,Q,2*i+1); return OK; /SaveElem Status 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) * sizeo
9、f(BiTNode)exit(ERROR); int i,j,n=1,k=h; for(i=1;i=int(pow(2,h)+1);i+) Qi=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(tt); for(j=0;jdata); if(!Qi)printf( ); for(j=0;j
10、data); / 访问 T FirstPrint(T-lchild,i); / 递归遍历左子树FirstPrint(T-rchild,i); / 递归遍历右子树 i=0; return OK; /FirstPrintBiTree Status MiddlePrint(BiTree T,int i) / 按中序次序 (递归 )访问二叉树if(i=0)printf(n中序 (递归 )遍历结果如下 :n); if(T) i+; MiddlePrint(T-lchild,i); / 递归遍历左子树printf(%-5c,T-data); / 访问 T MiddlePrint(T-rchild,i);
11、/ 递归遍历右子树 i=0; return OK; /MiddlePrint Status LastPrint(BiTree T,int i) / 按后序次序 (递归 )访问二叉树if(i=0)printf(n后序 (递归 )遍历结果如下 :n); if(T) i+; . . 优选LastPrint(T-lchild,i); / 递归遍历左子树LastPrint(T-rchild,i); / 递归遍历右子树printf(%-5c,T-data); / 访问 T i=0; return OK; /LastPrint Status PreOrderTraverse(BiTree T) / 按先序
12、(非递归 )遍历二叉树T BiTree p,S,q; int flag=0; if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR); S-next=NULL; / 建立空栈S p=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) / 栈顶指针出栈,如果当前栈
13、顶指针的右孩子存在那么跳出循环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(nn); return OK; /PreOrderTraverse Status InOrderTraverse(BiTree T) / 中序遍历 (非递归 )二叉树 T BiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR)
14、; S-next=NULL; / 建立空栈S p=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); / 输出栈中元素elsereturn ERROR; p=p-rchild; printf(nn); return OK; /InOrderTraverse Status PostOrderTraverse(BiTree T) /
15、后序遍历 (非递归 )二叉树 T BiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR); S-next=NULL; / 建立空栈S p=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; elsebreak; while(S-next) p=S-n
16、ext;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(nn); return OK; /PostOrderTraverse . . 优选Status GetElemSum(BiTree T) / 计算二叉树中总结点的个数BiTree p,*q; int l=0,h=0; if(!(q=(BiTree *)malloc(int(pow(2,TreeDepth(T,l,h)+1) * sizeof(BiTNode)exit(ERROR); int head=1,tail=2; q1=T; while(headlchild)qtail+=p-lchild; if(p
